Code covered by the BSD License

# NEXTPERMPOS

### Jos (10584) (view profile)

the next combination of values in specific positions (extension of PERMPOS)

nextpermpos(C)
```function [Cout, TFflag] = nextpermpos(C)
% NEXTPERMPOS - the next combination of values in specific positions
%
% This function is an extension of PERMPOS,  for large cases.
% A = PERMPOS(M,N) returns a matrix A in which each row contains a unique
% permutation of M trues and (N-M) falses over N columns.
% When the first input to PERMPOS is a vector V with M elements, each row
% of A contains the M values in order, but uniquely distributed over the N
% columns of A. See PERMPOS for examples.
%
% The number of rows increases quite rapidly with increasing M and N, in
% which case the use of NEXTPERMPOS may be used to avoid memory issues.
%
% CN = NEXTPERMPOS(C) returns a single permutation permutation. The input C
% is a vector with N elements, having M non-zero (or true) elements. CN
% contains the next permutation of these M values over N positions.
% CN has the same size as C.
%
% Examples:
%     nextpermpos([1 0 0 1 0]) % -> [1 0 0 0 1]
%     nextpermpos([1 0 1 1 1 0 1]) % -> [1 0 1 1 0 1 1]
%     nextpermpos([99 0 23]) % -> [0 99 23]
%     isequal(nextpermpos([1 zeros(1,999) 2 0]), [1 zeros(1,1000) 2])
%
%     A = permpos(3,6)
%     for k = 1:size(A,1)-1
%        C1 = A(k,:) ;
%        CN = nextpermpos(C1) ;
%        if ~isequal(A(k+1,:),CN), disp('This should not happen.') ; end
%        disp(CN) ;
%     end
%
% [C2, TF] = NEXTPERMPOS(C) returns a flag that is true if C2 is really the
% next permutation. If C is the last possible permutation, C2 will be the
% first permutation. Examples:
%      [c2, tf] = nextpermpos ([0 1 0]) % c2 = [0 0 1], tf = true
%      [c3, tf] = nextpermpos (c2) % c3 = [1 0 0], tf = false
%

% tested in MatLab 2011b
% version 1.0 (sep 2012)
% (c) Jos van der Geest
% email: jos@jasen.nl

% History:
% 1.0 sep 2012 - created, per suggestion of Yiannis C.

if ~(isnumeric(C) || islogical(C)) || ndims(C) ~= 2 || ~any(size(C)==1)
error ('Input should be numeric or logical vector.')
end

% C is a vector with N elements that looks like this
% [ ... V(1) ... V(2) ... V(K) ...]

N = numel(C) ;
POS = find(C) ;
K = numel(POS) ;

% pre-allocation
if islogical(C)
Cout = false(size(C)) ;
V = true ;
else
Cout = zeros(size(C),class(C)) ;
V = C(POS) ;
end

% Assume C is the last permutation
TFflag = false ;
if K > 0,
% find the last item that can be moved to the right
J = find(POS < ((N-K+1):N), 1, 'last') ;
if isempty(J),
% all elements are already at the most right of the vector,
% so, there is no next permutation of positions
% We will return the first permutation
Cout(1:K) = V ;
else
% There is an element that can move to the right. All subsequent
% elements will be put on the right from that one
k = find((1:N)== POS(J), 1, 'last') ;
POS(J:K) = (1:(K-J+1)) + k ;
Cout(POS) = V ;
TFflag = true ; % a true next permutation
end
end
```