1
$\begingroup$

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.

$\endgroup$

closed as off-topic by David Richerby, Evil, Yuval Filmus, Juho, Nicholas Mancuso Feb 9 '17 at 17:26

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, Evil, Yuval Filmus, Juho, Nicholas Mancuso
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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.
$\endgroup$
  • 1
    $\begingroup$ previous answer I gave was actually giving unordered combinations (nchoosek itself). Sorry, I misunderstood the definition. $\endgroup$ – Billiska Feb 1 '17 at 14:25
  • 1
    $\begingroup$ I could continue from that by defining yet again my own perms(A), but I figured you won't really want that. $\endgroup$ – Billiska Feb 1 '17 at 14:32
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Billiska Feb 1 '17 at 15:57
  • $\begingroup$ Knuth's algorithm (not necessarily due to him) is probably more efficient, but unfortunately I don't have the book with me to check. $\endgroup$ – Yuval Filmus Feb 1 '17 at 15:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.