کد:
function [M, I] = Permn(V, N, K)
% PERMN - permutations with repetition
% Using two input variables V and N, M = PERMN(V,N) returns all
% permutations of N elements taken from the vector V, with repetitions.
% V can be any type of array (numbers, cells etc.) and M will be of the
% same type as V. If V is empty or N is 0, M will be empty. M has the
% size numel(V).^N-by-N.
%
% When only a subset of these permutations is needed, you can call PERMN
% with 3 input variables: M = PERMNSUB(V,N,K).
% M will return only the K-ths permutations. The output is the same as M
% = PERMN(V,N), followed by M = M(K,:), but it avoids memory issues by
% generating all possible combinations first. This is particulary useful
% when you only need one, or a small subset of all permutations at a
% given time. If V or K is empty, or N is zerp, M will be empty. M has
% the size numel(K)-by-N.
%
% [M, I] = PERMN(...) also returns an index matrix I so that M = V(I).
%
% Examples:
% M = permn([1 2 3],2) % returns the 9-by-2 matrix:
% 1 1
% 1 2
% 1 3
% 2 1
% 2 2
% 2 3
% 3 1
% 3 2
% 3 3
%
% M = permn([99 7],4) % returns the 16-by-4 matrix:
% 99 99 99 99
% 99 99 99 7
% 99 99 7 99
% 99 99 7 7
% ...
% 7 7 7 99
% 7 7 7 7
%
% M = permn({'hello!' 1:3},2) % returns the 4-by-2 cell array
% 'hello!' 'Ahello!'
% 'hello!' [1x3 double]
% [1x3 double] 'hello!'
% [1x3 double] [1x3 double]
%
% V = 11:15, N = 3, K = [2 124 21 99]
% M = permn(V, N, K) % returns the 4-by-3 matrix:
% % 1 1 2
% % 5 5 4
% % 1 5 1
% % 4 5 4
% % which are the 2nd, 124th, 21st and 99th combinations
% % Check with PERMN
% M2 = permn(V,N) ; isequal(M2(K,:),M)
% % Note that M2 is a 125-by-3 matrix
%
% % PERMN can be used generate a binary table
% B = permn([0 1],5)
%
% NB Matrix sizes increases exponentially at rate (n^N)*N.
%
% See also PERMS, NCHOOSEK
% ALLCOMB, PERMPOS on the File Exchange
% tested in Matlab R13, R14, 2010b, 2014a
% version 6.0 (may 2015)
% (c) Jos van der Geest
% Matlab File Exchange Author ID: 10584
% email: samelinoa@gmail.com
% History
% 1.1 updated help text
% 2.0 new faster algorithm
% 3.0 (aug 2006) implemented very fast algorithm
% 3.1 (may 2007) Improved algorithm Roger Stafford pointed out that for some values, the floor
% operation on floating points, according to the IEEE 754 standard, could return
% erroneous values. His excellent solution was to add (1/2) to the values
% of A.
% 3.2 (may 2007) changed help and error messages slightly
% 4.0 (may 2008) again a faster implementation, based on ALLCOMB, suggested on the
% newsgroup comp.soft-sys.matlab on May 7th 2008 by "Helper". It was
% pointed out that COMBN(V,N) equals ALLCOMB(V,V,V...) (V repeated N
% times), ALLCMOB being faster. Actually version 4 is an improvement
% over version 1 ...
% 4.1 (jan 2010) removed call to FLIPLR, using refered indexing N:-1:1
% (is faster, suggestion of Jan Simon, jan 2010), removed REPMAT, and
% let NDGRID handle this
% 4.2 (apr 2011) corrrectly return a column vector for N = 1 (error pointed
% out by Wilson).
% 4.3 (apr 2013) make a reference to COMBNSUB
% 5.0 (may 2015) NAME CHANGED (COMBN -> PERMN) and updated description,
% following comment by Stephen Obeldick that this function is misnamed
% as it produces permutations with repetitions rather then combinations.
% 5.1 (may 2015) always calculate M via indices
% 6.0 (may 2015) merged the functionaly of permnsub (aka combnsub) and this
% function
narginchk(2,3) ;
if fix(N) ~= N || N < 0 || numel(N) ~= 1 ;
error('permn:negativeN','Second argument should be a positive integer') ;
end
nV = numel(V) ;
if nargin==2, % PERMN(V,N) - return all permutations
if nV==0 || N == 0,
M = zeros(nV,N) ;
I = zeros(nV,N) ;
elseif N == 1,
% return column vectors
M = V(:) ;
I = (1:nV).' ;
else
% this is faster than the math trick used for the call with three
% arguments.
[Y{N:-1:1}] = ndgrid(1:nV) ;
I = reshape(cat(N+1,Y{:}),[],N) ;
% I = local_allcomb(1:nV, N) ;
M = V(I) ;
end
else % PERMN(V,N,K) - return a subset of all permutations
nK = numel(K) ;
if nV == 0 || N == 0 || nK == 0
M = zeros(numel(K), N) ;
I = zeros(numel(K), N) ;
elseif nK < 1 || any(K<1) || any(K ~= fix(K))
error('permn:InvalidIndex','Third argument should contain positive integers.') ;
else
V = reshape(V,1,[]) ; % v1.1 make input a row vector
nV = numel(V) ;
Npos = nV^N ;
if any(K > Npos)
warning('permn:IndexOverflow', ...
'Values of K exceeding the total number of combinations are saturated.')
K = min(K, Npos) ;
end
% The engine is based on version 3.2 of COMBN with the correction
% suggested by Roger Stafford. This approaches uses a single matrix
% multiplication.
B = nV.^(1-N:0) ;
I = ((K(:)-.5) * B) ; % matrix multiplication
I = rem(floor(I),nV) + 1 ;
M = V(I) ;
end
end
% Algorithm using for-loops
% which can be implemented in C or VB
%
% nv = length(V) ;
% C = zeros(nv^N,N) ; % declaration
% for ii=1:N,
% cc = 1 ;
% for jj=1:(nv^(ii-1)),
% for kk=1:nv,
% for mm=1:(nv^(N-ii)),
% C(cc,ii) = V(kk) ;
% cc = cc + 1 ;
% end
% end
% end
% end