Combination of choices - recursive function

Hi

I have to create a program that lists all possible combinations. The operation of this program is described below.

For example, I start with five and in the next step I can choose 4, 5 or 6. If I choose 4 I can choose 3, 4 or 5. If I choose 3 I can choose 2, 3 or 4 etc.

Similarly, if I choose 6 in the first step, I can choose 5, 6 or 7.

I would like the resulting matrix to look something like this:

5, 5, 5, 4 ...

5, 5, 5, 5 ...

5, 5, 5, 6 ...

5, 5, 4, 3 ...

5, 5, 4, 4 ...

5, 5, 4, 5 ...

...

and so on...

The picture below shows what it looks like.

The values ​​limiting the number of steps that the algorithm must perform will be a sum. So, for example, if we take the sum equal to 30, then the sum of all the numbers in the previous steps must be less than 30.

Another limitation will be the values. For example, the upper limit might be 8 and the lower limit might be 2. So I can choose 8, but then I can only choose 8 or 7. Same for the bottom. If I go to 2, I can only choose 2 or 3 later.

I thought about recursive algorithms, but never did one in MATLAB. I will be grateful for any tips and help.

Arthur

[Image Analyst]

What's the use case? Homework?

[Artur Wszolek]

No, it's not homework. It will be a program for financial and investment issues. This is my idea, but I need some support.

[Sourabh Kondapaka]

Hi Artur Wszolek,

Are negative values allowed ? If yes, then it could become an infinitely recursive program.

Answer 1

[Sourabh Kondapaka]

Hi Artur Wszolek,

I'm assuming negative values are not allowed. The below is a sample code which can help in achieving what you wanted:

You can tweak it as per your need.

You can create a file called recursive.m file and copy paste the below code.

function  recursive(startNumber,maxSum)
%RECURSIVE Summary of this function goes here
%   Detailed explanation goes here   
    currentArr = (startNumber);
    matrix = recursiveHelper(startNumber, maxSum, 0, currentArr, [1 0 -1], {});
    disp('combinations are');
    disp(matrix);
end

function combinationMatrix = recursiveHelper(startNumber, maxSum, currentSum, currentArr, possibleChanges, combinationMatrix)
      
    if startNumber < 1
        return;
    end 
    
    currentSum = currentSum + startNumber;    
    
    if currentSum + startNumber - 1 > maxSum
        combinationMatrix{end + 1} = currentArr;
        return;
    end
    
    
    for i = 1:length(possibleChanges)
        newNumber = startNumber + possibleChanges(i);
        if newNumber < 1
            continue;
        end
        currentArr = [currentArr newNumber];
        
        if currentSum + newNumber < maxSum
            combinationMatrix = recursiveHelper(newNumber, maxSum, currentSum, currentArr, possibleChanges, combinationMatrix);        
        end
        
        currentArr = currentArr(1:end-1);
    end   
    
end

The way to call this function is:

>> recursive(5,16);
combinations are
    {[5 5 5]}    {[5 5 4]}    {[5 4 5]}    {[5 4 3 3]}

Answer 2

[Bruno Luong]

This is non-recusive approach (recursive is perhaps more scalable)

maxsum=16
lo=1;   % 2
up=Inf; % 8
start=5;

% estimate the maximum length of the path
s=sum(lo+1:start);
d=max(maxsum-s,0);
maxlgt=ceil(d/lo)+start-lo;
if maxlgt >= 18
    error('probably too large pb to handle')
end

A=dec2base(0:3^(maxlgt-1)-1,3)-'0'-1;
A=[start+zeros(size(A,1),1) A];
A=cumsum(A,2);
% filter out
A(A<lo | A>up)=Inf;
bsum = ~(cumsum(A,2)<=maxsum);
A(bsum) = Inf;
% 
A(isinf(A))=-Inf;
A=unique(A,'rows');
% Remove duplicate shorter path
rm=false(1,size(A,1));
for i=1:size(A,1)-1
    j=1:find(isfinite(A(i,:)),1,'last');
    rm(i) = all(A(i,j)==A(i+1,j));
end
A(rm,:)=[];
% replace -Inf by NaN
A(isinf(A))=NaN;
A

Result

     5     4     3     2     1     1
     5     4     3     2     2   NaN
     5     4     3     3   NaN   NaN
     5     4     3     4   NaN   NaN
     5     4     4     3   NaN   NaN
     5     4     5   NaN   NaN   NaN
     5     5     4   NaN   NaN   NaN
     5     5     5   NaN   NaN   NaN
     5     5     6   NaN   NaN   NaN
     5     6     5   NaN   NaN   NaN

Answer 3

[Bruno Luong]

Recursive method

maxsum=16
lo=1;
up=Inf;
start=5;

[~,A] = price(start, lo, up, maxsum)

%%
function [p, A] = price(start, lo, up, maxsum)
p = price_recurse(start, start, lo, up, maxsum);
% Put cell of all combination into matrix (optional)
if nargout >= 2
    maxlength = max(cellfun('length',p));
    A = cellfun(@(p) [p nan(1,maxlength-length(p))], p, 'unif', 0);
    A = cell2mat(A);
end
end

%% Recursive engine
function p = price_recurse(k1, k2, lo, up, maxsum)
k1 = max([k1,lo]);
k2 = min([k2,up,maxsum]);
if k1 > k2
    p = {[]};
else
    p = {};
    for k=k1:k2
        p = [p; cellfun(@(p) [k p], ...
                         price_recurse(k-1, k+1, lo, up, maxsum-k), ...
                         'unif', 0)];
    end
end
end

Result

A =

     5     4     3     2     1     1
     5     4     3     2     2   NaN
     5     4     3     3   NaN   NaN
     5     4     3     4   NaN   NaN
     5     4     4     3   NaN   NaN
     5     4     5   NaN   NaN   NaN
     5     5     4   NaN   NaN   NaN
     5     5     5   NaN   NaN   NaN
     5     5     6   NaN   NaN   NaN
     5     6     5   NaN   NaN   NaN