CODEWITHSUNDEEP
algorithmrecursionpermutation
Brian
Brian

Reputation: 197

Algorithm to solve nPr (permutations). For dummies

Yes, I've RTFM. Or, in this case, RTFSO. If it showed up in the search results for "npr" or "permutation", I read it. And while I have implemented Heap's algorithm, I can't make the leap from there (all permutations), to nPr (all permutations of length r, out of a larger set n).

An actual algorithm (pseudo-code is fine) is preferred to a long-winded explanation that doesn't include actual code. If you want to school me on the theory, fine, I'll be happy to learn from it, but I'd also like the accompanying code. If you can put in terms of Heap's, great; otherwise, I'll muddle through.

I don't have any code to show you (unless you want to see Heap's implemented in VBScript (which is all I have to work with at work)) because, as I said, I don't know where to go from there to get every r-length subset of set n.

In case my description of nPr is lacking, here is a very simple example of what I'm looking to do:

Given the set...

A, B, C

...I want to find every two-character permutation, like so:

A B
A C
B C

That example is overly simplistic, as what I am really trying to derive is a generalized solution that takes a set (array), and the number of items that should be in each permutation, as calling parameters.

Hmmm...now that I've written all this out, it seems to me that I only really need to know how to derive all subsets of length r from set n, since I can then find the permutations of those subsets using Heap's.

FYI: I'll be 50 this year; this isn't homework.

Upvotes: 2

Views: 932

Answers (1)

Stefan Haustein
Stefan Haustein

Reputation: 18803

Relatively straightforward with recursion:

  • For each element in the set, use it or not.
  • Recurse with the rest of the set for both variants.
  • Stop when the result is complete or the remaining set is empty.
  • For performance, avoid actual set operation using start / position indices.

In JavaScript: 

function nPr(set, n) {
  nPrImpl(set, 0, new Array(n), 0);
}

function nPrImpl(set, pos, result, resultPos) {

  // result complete
  if (resultPos == result.length) {
    window.console.log(result);
    return;
  } 

  // No more characters available
  if (pos >= set.length) {
    return;
  }

  // With set[pos]
  result[resultPos] = set[pos];
  nPrImpl(set, pos + 1, result, resultPos + 1);

  // Without
  nPrImpl(set, pos + 1, result, resultPos);
}

// Test:
nPr(['A', 'B', 'C'], 2);

Output:

["A", "B"]
["A", "C"]
["B", "C"]

Demo: https://tidejnet.appspot.com/v3/#id=8ht8adf3rlyi

Upvotes: 2

Related Questions