6
\$\begingroup\$

I have written this snippet to find r-permutations of n, i.e. if I have an array of n=3 {0,1,2}, then r=2 permutations will be {{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}}. Can somebody review it and help me optimize / reduce its complexity (I don't want to use recursive function):

"_getAllPermutation": function(input, allPermutations, usedIndices, r) {
    var index = 0,
        usedIndex = null;

    for (; index < input.length; index++) {
        usedIndex = input.splice(index, 1)[0];
        r--;
        usedIndices.push(usedIndex);
        if (input.length === 0 || r === 0) {
            allPermutations.push(usedIndices.slice());
        }
        if (r > 0) {
            this._getAllPermutation(input, allPermutations, usedIndices, r);
        }
        input.splice(index, 0, usedIndex);
        r++;
        usedIndices.pop();
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ You have to include either recursive calls or nested loops (and/or in-built functionalities performing this kind of actions). Just one suggestion: perhaps you should keep the nomenclature consistent to avoid misunderstandings (e.g., if you talk about k, include k in your code). Because this r is not too clear (mainly when it is being modified inside the function). \$\endgroup\$ Commented Nov 19, 2015 at 20:08

1 Answer 1

Reset to default
5
\$\begingroup\$

I know you asked for a non-recursive version, but recursion is a natural way to approach this problem. Here's a compact, though not high-performance, approach:

function nPr(xs, r) {
    if (!r) return [];
    return xs.reduce(function(memo, cur, i) {
        var others  = xs.slice(0,i).concat(xs.slice(i+1)),
            perms   = nPr(others, r-1),
            newElms = !perms.length ? [[cur]] :
                      perms.map(function(perm) { return [cur].concat(perm) });
        return memo.concat(newElms);
    }, []);
}

All we're doing is taking each element, and then appending it to the (r-1) permutations of all the other elements.

It is possible to do this using while and without recursion, though it will be hard to make that approach as terse. I'll try to take a shot at it later.

\$\endgroup\$
4
  • \$\begingroup\$ After our talk yesterday (and after having seen various questions on this front during the last days), I decided to go ahead and write a loops-based in the way I like. It is a code which can become handy at a later stage (not too straightforward to write). If you want to take a look, I uploaded it to my GitHub account; I guess that you prefer the C# version (also a VB.NET one): github.com/varocarbas/permutations/blob/master/permutations/… You shouldn't find too many problems to understand it as far as is mostly formed by parts which are very similar in JavaScript.... \$\endgroup\$ Commented Nov 20, 2015 at 20:51
  • \$\begingroup\$ ... I have also included the version with repetitions I mentioned yesterday (i.e., where the number of permutations results from the equation: elements_considered ^ size_permutation); you can enable/disable it with a simple flag (also you can see the required modifications + how easily I might change many other things; what I was telling you yesterday too). Logically, the whole point of this code is transmitting clearly the ideas (and easily allowing as many modifications as required) and is not over-optimised; but actually its performance seems equivalent to your code's one (even faster). \$\endgroup\$ Commented Nov 20, 2015 at 20:56
  • \$\begingroup\$ I replied in your github project. \$\endgroup\$ Commented Nov 20, 2015 at 21:11
  • \$\begingroup\$ And I re-replied there (I guess that we don't need to continue here :)). It seems that your repetitions are not right. \$\endgroup\$ Commented Nov 20, 2015 at 21:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.