Combination of choices - recursive function

조회 수: 2 (최근 30일)
Artur Wszolek
Artur Wszolek 2020년 11월 11일
편집: Bruno Luong 2020년 11월 19일
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
Artur Wszolek
Artur Wszolek 2020년 11월 11일
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 2020년 11월 16일
Are negative values allowed ? If yes, then it could become an infinitely recursive program.

댓글을 달려면 로그인하십시오.

답변 (3개)

Sourabh Kondapaka
Sourabh Kondapaka 2020년 11월 19일
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]}

Bruno Luong
Bruno Luong 2020년 11월 19일
편집: Bruno Luong 2020년 11월 19일
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

Bruno Luong
Bruno Luong 2020년 11월 19일
편집: Bruno Luong 2020년 11월 19일
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

카테고리

Help CenterFile Exchange에서 Logical에 대해 자세히 알아보기

제품


릴리스

R2016a

Community Treasure Hunt

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

Start Hunting!

Translated by