Combination of choices - recursive function
4 views (last 30 days)
Show older comments
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.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/410848/image.png)
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
Sourabh Kondapaka
on 16 Nov 2020
Are negative values allowed ? If yes, then it could become an infinitely recursive program.
Answers (3)
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
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
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
See Also
Categories
Find more on Logical in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!