image thumbnail

NextVector toolbox

version 1.1.0.0 (8.17 KB) by Ben Petschel
files for iterating over permutations, combinations, subsets and vectorized for/while loops

1.7K Downloads

Updated 11 Aug 2009

View License

The NextVector toolbox is a collection of files useful for doing iterations over all permutations, combinations, subsets and tuples.

This is useful when the results of perms or nchoosek are too large to hold in memory but the number of iterations is feasible.

nextperm - next permutation of a given vector
nextchoose - next combination of a given vector
nextsubs - next subset of a given vector
nextfor - next tuple in the vectorized for-loop.
nexttuple - next tuple in cartesian product AxB
nextwhile - next vector satisfying a general condition

Vectors are ordered according to number of elements and lex, i.e. if the length is the same, they are ordered according to the first element that differs. If the vector has no successor, next* returns [] (empty).

If the vectors have repeated elements (i.e. multisets) then next* returns the next distinct vector. Char inputs are allowed.

Examples (single iterations):

nextperm([1,2,3]) %returns [1,3,2].
nextperm([1,2,1]) %returns [2,1,1]
nextperm([3,2,1]) %returns []

nextchoose([1,2,3],4) % returns [1,2,4]
nextchoose([1,2,4],4) % returns [1,3,4]
nextchoose([1,3,4],4) % returns [2,3,4]
nextchoose([2,3,4],4) % returns []
nextchoose([1,2],[1,2,2,3]) % returns [1,3]
nextchoose([1,3],[1,2,2,3]) % returns [2,2]

nextfor([],[0,0],[1,1]) % returns [0,0]
nextfor([0,0],[0,0],[1,1]) % returns [0,1]
nextfor([0,1],[0,0],[1,1]) % returns [1,0]
nextfor([1,0],[0,0],[1,1]) % returns [1,1]
nextfor([1,1],[0,0],[1,1]) % returns []
nextfor([0,0],[0,1],[1,0],[1,-1]) % returns [1,1]

nextsubs([],1:4) % returns 1
nextsubs([1,2,3],1:4) % returns [1,2,4]
nextsubs([2,3,4],1:4) % returns 1:4
nextsubs(1:4,1:4) % returns []
nextsubs([1,2],[1,2,2,3]) % returns [1,3]
nextsubs([1,3],[1,2,2,3]) % returns [2,2]
nextsubs([2,3],[1,2,2,3]) % returns [1,2,2]

nexttuple([1,6],[1,2,3],[4,5,6]) % returns [2,4]

nextwhile([2,5],[1,1],@(x)prod(x)<=10) % returns [3,1]

Example (loops):

% count permutations of [1,2,3,3]
v0=[1,2,3,3];
k=0;
v=v0;
while ~isempty(v),
k=k+1;
v=nextperm(v);
end;
k % returns 12

% all 4-element subsets of 1:8
n=8;
k=4;
v=1:k;
M=zeros(nchoosek(n,k),k);
i=0;
while ~isempty(v),
i=i+1;
M(i,:)=v;
v=nextchoose(v,n);
end;
isequal(M,sortrows(nchoosek(1:n,k))) % =1

% all integer 4-vectors such that 1<=V<=10
n=4;
lo=ones(1,n);
hi=10*lo;
v=nextfor([],lo,hi);
M=zeros(prod(hi-lo+1),n);
i=0;
while ~isempty(v),
i=i+1;
M(i,:)=v;
v=nextfor(v,lo,hi);
end;
isequal(M,num2str((0:10^n-1)','%04d')-'0'+1) % 1

% iterate over all positive 4-vectors satisfying prod(x)<=10
cond=@(x)prod(x)<=10;
lo=ones(1,4);
v=nextwhile([],lo,cond);
M=[];
while ~isempty(v),
M=[M;v];
v=nextwhile(v,lo,cond);
end;
M % returns 89x4 array
all(prod(M,2)<=10) % 1

nextsubs requires nextchoose to run; all other functions work stand-alone.

As these functions are intended for many repeated calls, for efficiency minimal input checking is performed.

See the individual help files for more details.

Cite As

Ben Petschel (2021). NextVector toolbox (https://www.mathworks.com/matlabcentral/fileexchange/24757-nextvector-toolbox), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2009a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!