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
%     
% See also PERMPOS (Matlab File Exchange), NCHOOSEK

% tested in MatLab 2011b
% version 1.0 (sep 2012)
% (c) Jos van der Geest
% email: [e-mail]

% 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