Enumerating the List of nPr (n Permute r) objects [closed]

I have been using MATLAB for a particular project, and have seemed to find a function that may or may not exist. This question isn't MATLAB specific, more algorithm specific.

I have a list of 12 items, indexed from 1 to 12. I want to be able to create a list of all possible permutations of these 12 items where I only want to select 6 of them per entry.

Here is a reference to what nPr is for those unfamiliar.

In MATLAB, there is a function called perms(A) such that it calculates nPn where n = A.length. However what I am looking for is nPr where n = 12 and r = 6. Is there a way to either

1. Exploit the perms function such that it does nPn such that n = 6, but in a way that it actually calculates nPr where n = 12 and r = 6.

2. Write a recursive algorithm to replace the perms(A) function and create a perms(A,r) function?

Any pointers or tips would be much appreciated and helpful.

• Given the answer, it seems that the question should be migrated elsewhere. – Yuval Filmus Feb 1 '17 at 14:37

This is more of a MATLAB specific answer

arrayfun(perms,nchoosek(A,r))

*Think of this as conceptual answer, because I have have been away from MATLAB and can't test it right now.

In other words,

1. get unordered combinations of elements in A, taken r at a time. using nchoosek.
2. get ordered combinations (with perms) of each unordered combinations. Applying a function to each element of a list can be done via arrayfun.
• previous answer I gave was actually giving unordered combinations (nchoosek itself). Sorry, I misunderstood the definition. – Apiwat Chantawibul Feb 1 '17 at 14:25
• I could continue from that by defining yet again my own perms(A), but I figured you won't really want that. – Apiwat Chantawibul Feb 1 '17 at 14:32

Here is pseudocode for the function Generate($k$, $A$), which generates all ordered $k$-tuples of distinct elements from the set $A$:

Generate($k$, $A$)

• If $k = 0$, output the empty tuple.

• Otherwise, for each element $x \in A$ and for each $(k-1)$-tuple $\alpha$ in Generate($k-1$, $A \setminus \{x\}$), output $x,\alpha$.

More efficient algorithms exist, see Volume 4A of Knuth's Art of Computer Programming.

• I had the same definition in mind and thought the computation and keeping track of $A \setminus \{x\}$ is inefficient. Is the algorithm in Knuth's have this inefficiency 'fixed', or is it another aspect? – Apiwat Chantawibul Feb 1 '17 at 15:57
• Knuth's algorithm (not necessarily due to him) is probably more efficient, but unfortunately I don't have the book with me to check. – Yuval Filmus Feb 1 '17 at 15:59