View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
permn(V, N, K)

4.8 | 32 ratings Rate this file 173 Downloads (last 30 days) File Size: 5.94 KB File ID: #7147 Version: 6.1

permn(V, N, K)


Jos (10584) (view profile)


15 Mar 2005 (Updated )

Permutations with repetition, all or a subset

| Watch this File

File Information

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 = permn(V,N,K) returns only the K-ths
    permutations. The output is the same as M = permn(V,N) ; M = M(K,:),
    but it avoids memory issues that may occur when there are too many
    combinations. This is particulary useful when you only need a few
    permutations at a given time. If V or K is empty, or N is zero, 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).
      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!' 'hello!'
              '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:
      % 11 11 12
      % 15 15 14
      % 11 15 11
      % 14 15 14
      % which are the 2nd, 124th, 21st and 99th permutations
      % Check with permn using two inputs
      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, as in
      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


This file inspired De Bruijn Sequence Generator, Kautz Sequence Generator, V Choose Kro, N Permute K, and Permnsub(V,N, Ix).

MATLAB release MATLAB 7 (R14)
MATLAB Search Path
Other requirements Should work in most ML releases
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (45)
17 Nov 2016 Farrukh Pervez

A very quick algorithm to find the permutations. A great work

Comment only
01 Oct 2016 Ceyhun KIRIMLI

or as a full function as follows;

function result=seqrep(V,N)
for i=1:N

Comment only
01 Oct 2016 Ceyhun KIRIMLI

i guess this can be done using only 1 for loop as shown below;

for i=1:n

where n= number of elements (as N here) and
l= length of V

Comment only
17 Aug 2016 Mohsen Mansouryar

14 Jun 2016 GALO ALBUJA

12 May 2016 guglielmo fortuni

01 Nov 2015 Triveni

Please help me to solve it

A=[30 30 30 30 30 30 60 60 60 60 60 60 60 60 30 30 30 30 30 30];

[c,b] = hist(A,unique(A));
N= length(A);
x = permn(b,N); %function permn

I have matrix A. i want to sort x. i need c(1,1) no of angle of 30. and c(1,2) no of angle of 60. means i need 12 nos of 30 and 8 nos of 60 in every permutations. How can i do it...please help me. Just like perm command works. but it's limited to 10. i need 20.

I also have another program but it's only works with 0 and 1.

A=[1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1];

n2 = numel(A);

b2 = nnz(A);

M2 = 0:ones(1,n2)*pow2(n2-1:-1:0)';

z2 = rem(floor(M2(:)*pow2(1-n2:0)),2);

out = z2(sum(z2,2) == b2,:);

18 May 2015 Jos (10584)

Jos (10584) (view profile)

On second thoughts, I change the name as well. Thanks!

Comment only
18 May 2015 Jos (10584)

Jos (10584) (view profile)

I know, Stephen. I decided to keep the original name for backward compatibility. Note that this function is more than 10 years old and still regularly downloaded.
I will update the description though!

Comment only
12 May 2015 Stephen Cobeldick

This submission is misnamed:

* If the order doesn't matter, it is a Combination.

* If the order does matter it is a Permutation.

It is clear from the example that this submission generates what is sometimes called "permutations with repetitions":

If this submission truly calculated the combinations then the sets {0,0,1}, {0,1,0}, and {1,0,0} are all equivalent, and would not all appear in the output shown in the example.

or for a simpler introduction:

Comment only
25 Feb 2013 Qi An

Qi An (view profile)

saved me sometime!

03 Jan 2013 ted p teng

ted p teng (view profile)

04 Jun 2012 Patrizio Manganiello

Thank you very much!

03 Jun 2012 mya

mya (view profile)

verry useful, thank you

04 Apr 2012 Han

Han (view profile)

Repetitive combination, great!

25 Mar 2012 Jos (10584)

Jos (10584) (view profile)

@Marc, thanks for your interest and suggestions for improvement. Yet, for code compatibility (and fairness) you need to implement to inverse order step as well :-)

Comment only
23 Mar 2012 Marc Lalancette

Nice code, thanks! Just for fun, slight to medium speed improvement (sorry my k = your N):

%instead of:
%[Y{k:-1:1}] = ndgrid(X) ;
%Y = reshape(cat(k+1,Y{:}),[],k) ;
%fill Y directly:
nX = numel(X);
Y(nX^k, k) = X(1); % Initialize to give shape and data type.
s(1:k-1) = {ones(1, nX)};
for i = 1:k
Y( ((i-1)*nX^k + 1) : (i*nX^k) ) = X(s{1:i-1}, :, s{i:k-1});
X = permute(X, [1:i-1, i+1, i]);
% This has inverse order for the combinations as you had, easy to change.

Comment only
09 Aug 2011 Jos (10584)

Jos (10584) (view profile)

@ Talaria, this is impossible as it would require a memory of (at least) 150*(2^150) bits which is about 2700000000000000000000000000000000 Terabyte ...

However, it is unlikely that you need all those combinations at once; perhaps you can think of another approach to your problem, for instance, by drawing a few random combinations at a time?

Comment only
05 Aug 2011 Talaria

works great, but is there a way to beat the limitation? for example i want to be able to return the following:
M = COMBN([0 1],150)
is this possible?

Comment only
22 Jul 2011 Owen Brimijoin

The core of this function is a lovely little computational gem. Thank you.

29 May 2011 Manu

Manu (view profile)

Excellent and fast!

25 May 2011 Brad Ridder

Excellent, just what I needed. Thanks!

11 Apr 2011 Fabio

Fabio (view profile)

Does anyone have an idea on how to create a function like "combn" but where the generated matrix contains only monotone rows? I could do it manually by removing non-monotone rows after having built the matrix, but when the size of the matrix becomes large i got out of memory error. Any idea?

Comment only
21 Dec 2010 John D'Errico

John D'Errico (view profile)

21 Jan 2010 Oleg Komarov

Oleg Komarov (view profile)

Can't find a better suited H1-line. Neat help, simple example, history (maybe more details on the dates...) and past algorithms too.
I don't use combinatorics very much but I always wonder why matlab doesn't cover it esplicitly. A must have.


16 Jan 2010 Jan Simon

Jan Simon (view profile)

Nice and comapct program! H1-line, help, history, comments in the code, efficient. Thanks!

But can be made still a little bit faster:
X = repmat({X},1,N) ;
[X{1:N}] = ndgrid(X{:}) ;
X = fliplr(reshape(cat(N+1,X{:}),[],N)) ;
1. If X is filled in reverse order with [X{N:-1:1}], FLIPLR can be omitted => 25% faster for COMBN(1:10, 5) (see my comment for ALLCOMB)
2. Inside NDGRID the same operations are performed for each input, but all inputs are equal. Inlining and simplyfying NDGRID leads to (REPMAT can be omitted then):
C = cell(1, N);
X = X(:);
L = length(X);
s(1:N - 1) = L;
X = reshape(X(:, ones(1, prod(s))), [L, s]);
C{N} = X;
for iC = 2:N
C{N - iC + 1} = permute(X, [2:iC, 1, iC + 1:N]);
X = reshape(cat(N+1, C{:}), [], N);
=> 40-50% faster.
To my surprise it is *slower* to create the output array at once and insert the permuted subarrays directly.

14 Dec 2009 Philip L

23 Mar 2009 Carlos Baiz


06 May 2008 jose caceres

any idea of how to get the combinations without repetition of previous combinations, and without re-using the elements in a a selection?

09 Apr 2008 Riccardo Bevilacqua

Exactly what I was looking for!

15 Jan 2008 Antonio Silva

Thanks a million!

24 Aug 2007 Ohad N

Does the job...

08 May 2007 Jos the author

Roger Stafford pointed out that, due to the IEEE 754 standard, the floor of a floating point (as used in COMBN's algorithm) may lead to faulty results for very specific inputs.
The update incorporates his excellent solution to this potential problem. Thanks Roger!
The update (COMBN version 3.2) should be up soon ...

Comment only
03 Apr 2007 Kaijun Wang

It is very useful, thanks !

21 Feb 2007 Wolfgang Zieroth

Fast and (almost) exactly what I needed!

... I only need those combinations which sum to (say) one. I can, of course, first create all combinations with this program and then find(m*ones(N,1)==1). Yet I bounce very quickly against maximum variable size for Matlab. Any Suggestions?

16 Jan 2007 ShenKae Wu

Thanks a lot

01 Nov 2006 Vangelis R

I am very surprised this is not a build in function. You saved my day thanks a lot!

25 Jul 2006 B E

Thanks! Exactly what I needed.

11 Jul 2006 Peter Navé

What I needed!

17 Jun 2006 Jürgen Womser-Schütz

Very fast! Very helpful to solve my actual problem.

21 Jan 2006 David Torres

Great tool. Easy to use.

28 Oct 2005 Richard Vance

Easy to use, fast, and suitable for incorporating into other programs. Good documentation well organized. It really helped me solve some problems.

18 Oct 2005 yakir gagnon

25 May 2005 Jos vdG

Jamie, use COMBN(UNIQUE(V),N)

Comment only
23 May 2005 Jamie Baier

Does what it says, but there really should be an option to treat elements as non-unique.

11 May 2006

new faster algorithm

31 Aug 2006

new (very fast) algorithm

08 May 2007

arggg updated with older version ...

18 Jan 2010 1.1

modified slightly based on suggestions by Jan Simon (thanks!)

04 Apr 2011 1.2

corrected to give column vector output for N=1. (error pointed out by Wilson via email).

09 Apr 2013 1.3

Reference to COMBNSUB for large combinatorial problems.

19 May 2015 5.1

Renamed file into PERMN, fixed small bug, extended help section

20 May 2015 6.1

Incorporated the functionality of permnsub, allowing for returning a subset rather than all permutations as well.

14 May 2016 6.1

spelling corrections

Contact us