File Exchange

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 Download

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 (2020). NextVector toolbox (https://www.mathworks.com/matlabcentral/fileexchange/24757-nextvector-toolbox), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (1)

Derek O'Connor

Just discovered this very useful toolbox. Used it to generate all Boolean matrices of a given size n.

Updates

1.1.0.0

added nexttuple.m and nextwhile.m

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