MATLAB Answers

Combination of choices - recursive function

7 views (last 30 days)
Artur Wszolek
Artur Wszolek on 11 Nov 2020
Edited: Bruno Luong on 19 Nov 2020
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

  3 Comments

Artur Wszolek
Artur Wszolek on 11 Nov 2020
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
Sourabh Kondapaka on 16 Nov 2020
Are negative values allowed ? If yes, then it could become an infinitely recursive program.

Sign in to comment.

Answers (3)

Sourabh Kondapaka
Sourabh Kondapaka on 19 Nov 2020
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]}

  0 Comments

Sign in to comment.


Bruno Luong
Bruno Luong on 19 Nov 2020
Edited: Bruno Luong on 19 Nov 2020
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

  0 Comments

Sign in to comment.


Bruno Luong
Bruno Luong on 19 Nov 2020
Edited: Bruno Luong on 19 Nov 2020
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

  0 Comments

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by