NextVector toolbox

files for iterating over permutations, combinations, subsets and vectorized for/while loops

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.