Partitioning a number into sum of positive real numbers

Hi,

I have a vector V = 0:0.1:M. I have 'w', 'x', 'y', and 'z', where w,x,y,z belongs to V. I want all w,x,y,z such that w+x+y+z = M. Also, and . I know exhaustive search method but I am interested in more efficient methods for this computation.

Answer 1

[Wan Ji]

Hi, friend! I have thought of a search method that saves much time.

Firstly, the problem can be converted to V = 1:1:M, there exist 'w', 'x', 'y', and 'z', where w,x,y,z belongs to V. Calculate all w<x<y<z such that w+x+y+z = M. because you can just let M=10*M, and x,y,z,w are all positive integers, you need only use [x,y,z,w] = 0.1*[x,y,z,w], as also mentioned by @the cyclist. Here I provide integer solution. I believe you can understand me.

The code speaks! So look at following code I wrote for this problem.

The search function is

function Result = searchPartition(M)
alpha = 1; A = 4*alpha;
R = zeros(M^3,4); % IF you have enough memory, time is not a problem
count = 0;
while (M-A>=6)
    beta = 1; B = 3*beta;
    while (M-A-B>=3)
        gamma = 1; C = 2*gamma;
        while (M-A-B-C>=1)
            delta = M-A-B-C;
            if(delta>=1)
                count = count + 1;
                R(count,:) = [alpha, beta, gamma, delta];
            else
                break;
            end
            gamma = gamma + 1;
            C = 2*gamma;
        end
        beta = beta + 1;
        B = 3*beta;
    end
    alpha = alpha + 1;
    A = 4*alpha;
end
R = R(1:count,:);
Result = cumsum(R,2);
end

To validate its correctness, here I perform a test

Result = searchPartition(20)

Then get the result as

Result =

     1     2     3    14
     1     2     4    13
     1     2     5    12
     1     2     6    11
     1     2     7    10
     1     2     8     9
     1     3     4    12
     1     3     5    11
     1     3     6    10
     1     3     7     9
     1     4     5    10
     1     4     6     9
     1     4     7     8
     1     5     6     8
     2     3     4    11
     2     3     5    10
     2     3     6     9
     2     3     7     8
     2     4     5     9
     2     4     6     8
     2     5     6     7
     3     4     5     8
     3     4     6     7

23 results were obtained, the columns from left to right are w,x,y,z accordingly.

Also, to verify its efficiency, here we choose M ranged from 200 to 1000 with interval 200, and calculate the cost time!

function main
M_array = 200:200:1000; % You can change M_array as you need
Time_array = zeros(size(M_array));
ResultSize_array = zeros(size(M_array));
for i = 1:1:numel(M_array)
tic % count the time
M  = M_array(i);
Result = searchPartition(M); % use my method
time = toc;
Time_array(i) = time;
ResultSize_array(i) = size(Result,1);
end
% plot figures
figure(100)
clf
subplot(1,2,1)
plot(M_array, Time_array,'r', 'linewidth',2)
xlabel('M value'); 
ylabel('Cost Time (s)');
title('Cost Time V.S. M')
subplot(1,2,2)
plot(M_array, ResultSize_array,'b', 'linewidth',2)
xlabel('M value'); 
ylabel('Result Size');
title('Result size V.S. M')
figure(200)
clf
loglog(ResultSize_array,Time_array, 'ro-', 'linewidth',2)
xlabel('Result Size'); 
ylabel('Time Cost');
title('Time cost V.S. Result size Loglog Plot')
end

It is found that when M = 1000, the time spent in my method is less than 2 seconds, while the result size reaches 7000,000, which is a quite large number! I hope you like it ovo

[the cyclist]

Fantastic

[VIVEK CHAUDHARY]

Hi Wan,

Thanks for the help. The code works fine for small M. However, my requirement is not restricted to 4 variables but it can blow upto 32 variables . In that case I would need a more robust code. If you can please refer me some resources on this problem that would be a great help.

Thanks.

[Wan Ji]

Hi VIVEK CHAUDHARY,

My idea conforms to this paper, Stirling numbers and integer partitions

You can read it and obtain the spirit to implement your thoughts.

[VIVEK CHAUDHARY]

Thanks a lot. Really appriciate the help.

Answer 2

[the cyclist]

This is equivalent to partitioning positive integers that sum to 10*M. Download @John D&#39;Errico's excellent partitioning code from the File Exchange. Then the following will do what you want.

% Desired sum
M = 20;

% Desired element count
N = 4;

% All partitions
p = partitions(M);

% Include only rows with no repeated values
p = p(all((p==1) | (p==0),2),:);

% Include only rows with the correct number of element
p = p(sum(p,2)==N,:);

% Show the results. Each row is a solution. In each row, there is a 1 in the
% nth column when n is a member of the set (w,x,y,z) that you want.
disp(p)

In this example, I am finding 4 integers that sum to 20. The solution in the first row of p is (3,4,6,7).

This is equivalent to (0.3,0.4,0.6,0.7) that sums to 2.

[the cyclist]

After looking at this a bit more, I realized that John's code has a more efficient calling syntax when you know how many elements you want:

% Desired sum
M = 20;

% Desired element count
N = 4;

% All partitions
p = partitions(M,[],[],N);

% Include only rows with no repeated values
p = p(all((p==1) | (p==0),2),:);

% Show the results. Each row is a solution. In each row, there is a 1 in the
% nth column when n is a member of the set (w,x,y,z) that you want.
disp(p)