How would you make these for loops dynamically recursive?
3 views (last 30 days)
Show older comments
Cameron Bruscino
on 20 Oct 2022
% Value that each row will sum up to in final matrix
qualmax=8;
% Almost unused var that I'd like to use to cut down on code
iters=8;
% Determine number of rows in the answer
syms s
a=sym2poly(symprod(s+qualmax,s,1,iters)/factorial(iters));
% Initialization Values
c=1;
n=zeros(a,9);
% a(1) is used to remove a sum of n_ values
for n1=0:qualmax
a1(1)=(qualmax-n1);
for n2=0:a1(1)
a1(2)=(a1(1)-n2);
for n3=0:a1(2)
a1(3)=(a1(2)-n3);
for n4=0:a1(3)
a1(4)=(a1(3)-n4);
for n5=0:a1(4)
a1(5)=(a1(4)-n5);
for n6=0:a1(5)
a1(6)=(a1(5)-n6);
for n7=0:a1(6)
a1(7)=(a1(6)-n7);
for n8=0:a1(7)
% Here is where we question what's left to get to qual max
a1(8)=(a1(7)-n8);
% Setting values
n(c,9)=n1;
n(c,8)=n2;
n(c,8)=n2;
n(c,7)=n3;
n(c,6)=n4;
n(c,5)=n5;
n(c,4)=n6;
n(c,3)=n7;
n(c,2)=n8;
n(c,1)=a1(8);
% Increment the index
c=c+1;
end
end
end
end
end
end
end
end
4 Comments
Bjorn Gustavsson
on 20 Oct 2022
It might help further if you explain your problem for smaller dimensions, (1) 2 or 3, just for illustration.
Accepted Answer
Walter Roberson
on 20 Oct 2022
For the case of integers, then what you are asking for looks to be what is known as Integer Partitions. You can use https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer from the File Exchange; @John D'Errico
More Answers (2)
Bruno Luong
on 21 Oct 2022
It will return 6435 solutions
c=allVL1(8,8)
5 Comments
Bruno Luong
on 21 Oct 2022
OP does not have list of number as input and I'm not counting the number of diophantin (linear) equation as John's code.
Also the order of elements in V by AllVL1 matters, whereas it is NOT in partition problem in general and John's code in particular.
I consider my solution is closer to wha OP's ask, not partition solver such as as John's code.
Torsten
on 20 Oct 2022
Edited: Torsten
on 20 Oct 2022
Code available under
It's brute-force - thus caution: quite memory-intensive.
I don't know if it's faster than the nested loop. At least it's more general.
iters = 8;
qualmax = 8;
v = 0:qualmax;
C = permn(v,iters+1);
size(C)
I = sum(C,2)==qualmax;
C = C(I,:);
size(C)
function [M, I] = permn(V, N, K)
% PERMN - permutations with repetition
% Using two input variables V and N, M = PERMN(V,N) returns all
% permutations of N elements taken from the vector V, with repetitions.
% V can be any type of array (numbers, cells etc.) and M will be of the
% same type as V. If V is empty or N is 0, M will be empty. M has the
% size numel(V).^N-by-N.
%
% When only a subset of these permutations is needed, you can call PERMN
% with 3 input variables: M = PERMN(V,N,K) returns only the K-ths
% permutations. The output is the same as M = PERMN(V,N) ; M = M(K,:),
% but it avoids memory issues that may occur when there are too many
% combinations. This is particulary useful when you only need a few
% permutations at a given time. If V or K is empty, or N is zero, M will
% be empty. M has the size numel(K)-by-N.
%
% [M, I] = PERMN(...) also returns an index matrix I so that M = V(I).
%
% Examples:
% M = permn([1 2 3],2) % returns the 9-by-2 matrix:
% 1 1
% 1 2
% 1 3
% 2 1
% 2 2
% 2 3
% 3 1
% 3 2
% 3 3
%
% M = permn([99 7],4) % returns the 16-by-4 matrix:
% 99 99 99 99
% 99 99 99 7
% 99 99 7 99
% 99 99 7 7
% ...
% 7 7 7 99
% 7 7 7 7
%
% M = permn({'hello!' 1:3},2) % returns the 4-by-2 cell array
% 'hello!' 'hello!'
% 'hello!' [1x3 double]
% [1x3 double] 'hello!'
% [1x3 double] [1x3 double]
%
% V = 11:15, N = 3, K = [2 124 21 99]
% M = permn(V, N, K) % returns the 4-by-3 matrix:
% % 11 11 12
% % 15 15 14
% % 11 15 11
% % 14 15 14
% % which are the 2nd, 124th, 21st and 99th permutations
% % Check with PERMN using two inputs
% M2 = permn(V,N) ; isequal(M2(K,:),M)
% % Note that M2 is a 125-by-3 matrix
%
% % PERMN can be used generate a binary table, as in
% B = permn([0 1],5)
%
% NB Matrix sizes increases exponentially at rate (n^N)*N.
%
% See also PERMS, NCHOOSEK
% ALLCOMB, PERMPOS, NEXTPERM, NCHOOSE2 on the File Exchange
% tested in Matlab 2018a
% version 6.2 (jan 2019)
% (c) Jos van der Geest
% Matlab File Exchange Author ID: 10584
% email: samelinoa@gmail.com
% History
% 1.1 updated help text
% 2.0 new faster algorithm
% 3.0 (aug 2006) implemented very fast algorithm
% 3.1 (may 2007) Improved algorithm Roger Stafford pointed out that for some values, the floor
% operation on floating points, according to the IEEE 754 standard, could return
% erroneous values. His excellent solution was to add (1/2) to the values
% of A.
% 3.2 (may 2007) changed help and error messages slightly
% 4.0 (may 2008) again a faster implementation, based on ALLCOMB, suggested on the
% newsgroup comp.soft-sys.matlab on May 7th 2008 by "Helper". It was
% pointed out that COMBN(V,N) equals ALLCOMB(V,V,V...) (V repeated N
% times), ALLCMOB being faster. Actually version 4 is an improvement
% over version 1 ...
% 4.1 (jan 2010) removed call to FLIPLR, using refered indexing N:-1:1
% (is faster, suggestion of Jan Simon, jan 2010), removed REPMAT, and
% let NDGRID handle this
% 4.2 (apr 2011) corrrectly return a column vector for N = 1 (error pointed
% out by Wilson).
% 4.3 (apr 2013) make a reference to COMBNSUB
% 5.0 (may 2015) NAME CHANGED (COMBN -> PERMN) and updated description,
% following comment by Stephen Obeldick that this function is misnamed
% as it produces permutations with repetitions rather then combinations.
% 5.1 (may 2015) always calculate M via indices
% 6.0 (may 2015) merged the functionaly of permnsub (aka combnsub) and this
% function
% 6.1 (may 2016) fixed spelling errors
% 6.2 (jan 2019) fixed some coding style warnings
narginchk(2, 3) ;
if fix(N) ~= N || N < 0 || numel(N) ~= 1
error('permn:negativeN','Second argument should be a positive integer') ;
end
nV = numel(V) ;
if nargin==2
%% PERMN(V,N) - return all permutations
if nV == 0 || N == 0
M = zeros(nV, N) ;
I = zeros(nV, N) ;
elseif N == 1
% return column vectors
M = V(:) ;
I = (1:nV).' ;
else
% this is faster than the math trick used with 3 inputs below
[Y{N:-1:1}] = ndgrid(1:nV) ;
I = reshape(cat(N+1, Y{:}), [], N) ;
M = V(I) ;
end
else
%% PERMN(V,N,K) - return a subset of all permutations
nK = numel(K) ;
if nV == 0 || N == 0 || nK == 0
M = zeros(numel(K), N) ;
I = zeros(numel(K), N) ;
elseif nK < 1 || any(K<1) || any(K ~= fix(K))
error('permn:InvalidIndex','Third argument should contain positive integers.') ;
else
V = reshape(V, 1, []) ; % v1.1 make input a row vector
nV = numel(V) ;
Npos = nV^N ;
if any(K > Npos)
warning('permn:IndexOverflow', ...
'Values of K exceeding the total number of combinations are saturated.')
K = min(K, Npos) ;
end
% The engine is based on version 3.2 with the correction
% suggested by Roger Stafford. This approach uses a single matrix
% multiplication.
B = nV.^(1-N:0) ;
I = ((K(:)-.5) * B) ; % matrix multiplication
I = rem(floor(I), nV) + 1 ;
M = V(I) ;
end
end
% Algorithm using for-loops
% which can be implemented in C or VB
%
% nv = length(V) ;
% C = zeros(nv^N,N) ; % declaration
% for ii=1:N,
% cc = 1 ;
% for jj=1:(nv^(ii-1)),
% for kk=1:nv,
% for mm=1:(nv^(N-ii)),
% C(cc,ii) = V(kk) ;
% cc = cc + 1 ;
% end
% end
% end
% end
end
0 Comments
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!