# Permutations without recursive function call

Requirement: Algorithm to generate all possible combinations of a set , without duplicates , or recursively calling function to return results.

The majority , if not all of the Answers provided at Permutations in JavaScript? recursively call a function from within a loop or other function to return results.

Example of recursive function call within loop

``````function p(a, b, res) {
var b = b || [], res = res || [], len = a.length;
if (!len)
res.push(b)
else
for (var i = 0; i < len
// recursive call to `p` here
; p(a.slice(0, i).concat(a.slice(i + 1, len)), b.concat(a[i]), res)
, i++
);
return res
}

p(["a", "b", "c"]);
``````

The current Question attempts to create the given permutation in a linear process , relying on the previous permutation.

For example , given an array

``````var arr = ["a", "b", "c"];
``````

to determine the total number of possible permutations

``````for (var len = 1, i = k = arr.length; len < i ; k *= len++);
``````

`k` should return `6` , or total number of possible permutations of `arr` `["a", "b", "c"]`

With the total number of individual permutations determined for a set , the resulting array which would contain all six permutations could be created and filled using `Array.prototype.slice()` , `Array.prototype.concat()` and `Array.prototype.reverse()`

``````var res = new Array(new Array(k));

res = arr;

res = res.slice(0,1).concat(res.slice(-2).reverse());

res = res.slice(-1).concat(res.slice(0,2));

res = res.slice(0,1).concat(res.slice(-2).reverse());

res = res.slice(-2).concat(res.slice(0,1));

res = res.slice(0,1).concat(res.slice(-2).reverse());
``````

Attempted to reproduce results based on the pattern displayed at the graph for An Ordered Lexicographic Permutation Algorithm based on one published in Practical Algorithms in C++ at Calculating Permutations and Job Interview Questions .

There appears to be a pattern that could be extended if the input set was , for example

`["a", "b", "c", "d", "e"]`

where 120 permutations would be expected.

An example of an attempt at filling array relying only on previous permutation

``````// returns duplicate entries at `j`
var arr = ["a", "b", "c", "d", "e"], j = [];
var i = k = arr.length;
arr.forEach(function(a, b, array) {
if (b > 1) {
k *= b;
if (b === i -1) {
for (var q = 0;j.length < k;q++) {
if (q === 0) {
j[q] = array;
} else {
j[q] = !(q % i)
? array.slice(q % i).reverse().concat(array.slice(0, q % i))
: array.slice(q % i).concat(array.slice(0, q % i));
}
}
}
}
})
``````

however have not yet been able to make the necessary adjustments at parameters for `.slice()` , `.concat()` , `.reverse()` at above `js` to step from one permutation to the next ; while only using the previous array entry within `res` to determine current permutation , without using recursive.

Noticed even , odd balance of calls and tried to use modulus `%` operator and input array `.length` to either call `.reverse()` or not at `["a", "b", "c", "d", "e"]` array , though did not produce results without duplicate entries.

The expected result is that the above pattern could be reduced to two lines called in succession for the duration of the process until all permutations completed, `res` filled ; one each for call to `.reverse()` , call without `.reverse()` ; e.g., after `res` filled

``````// odd , how to adjust `.slice()` , `.concat()` parameters
// for array of unknown `n` `.length` ?
res[i] = res[i - 1].slice(0,1).concat(res[i - 1].slice(-2).reverse());
// even
res[i] = res[1 - 1].slice(-1).concat(res[i - 1].slice(0,2));
``````

Question: What adjustments to above pattern are necessary , in particular parameters , or index , passed `.slice()` , `.concat()` to produce all possible permutations of a given set without using a recursive call to the currently processing function ?

``````var arr = ["a", "b", "c"];

for (var len = 1, i = k = arr.length; len < i; k *= len++);

var res = new Array(new Array(k));

res = arr;

res = res.slice(0, 1).concat(res.slice(-2).reverse());

res = res.slice(-1).concat(res.slice(0, 2));

res = res.slice(0, 1).concat(res.slice(-2).reverse());

res = res.slice(-2).concat(res.slice(0, 1));

res = res.slice(0, 1).concat(res.slice(-2).reverse());

console.log(res);``````

Edit, Update

Have found a process to utilize pattern described above to return permutations in lexicographic order for an input up to `.length` 4 , using a single `for` loop. Expected results are not returned for array with `.length` of `5`.

The pattern is based on the second chart at "Calculating Permutations and Job Interview Questions".

Would prefer not to use `.splice()` or `.sort()` to return results, though used here while attempting to adhere to last "rotate" requirement at each column. The variable `r` should reference the `index` of the first element of the next permutation, which it does.

The use of `.splice()` , `.sort()` could be included if their usage followed the pattern at the chart ; though at `js` below, they actually do not.

Not entirely certain that the issue with `js` below is only the statement following `if (i % (total / len) === reset)` , though that portion required the most investment of time; yet still does not return expected results.

Specifically, now referring to the chart, at rotating , for example `2` to index `0`, `1` to index `2`. Attempted to achieve this by using `r` , which is a negative index, to traverses from right to left to retrieve next item that should be positioned at `index` `0` of adjacent "column".

At next column, `2` would be placed at `index` `2` , `3` would be placed at `index` `0`. This is portion, as far as have been able to grasp or debug, so far, is the area where error is occurring.

Again, returns expected results for `[1,2,3,4]`, though not for `[1,2,3,4,5]`

``````var arr = [1, 2, 3, 4];
for (var l = 1, j = total = arr.length; l < j ; total *= l++);
for (var i = 1
, reset = 0
, idx = 0
, r = 0
, len = arr.length
, res = [arr]
; i < total; i++) {
// previous permutation
var prev = res[i - 1];
// if we are at permutation `6` here, or, completion of all
// permutations beginning with `1`;
// setting next "column", place `2` at `index` 0;
// following all permutations beginning with `2`, place `3` at
// `index` `0`; with same process for `3` to `4`
if (i % (total / len) === reset) {
r = --r % -(len);
var next = prev.slice(r);
if (r === -1) {
// first implementation used for setting item at index `-1`
// to `index` 0
// would prefer to use single process for all "rotations",
// instead of splitting into `if` , `else`, though not there, yet
res[i] = [next].concat(prev.slice(0, 1), prev.slice(1, len - 1)
.reverse());
} else {
// workaround for "rotation" at from `index` `r` to `index` `0`
// the chart does not actually use the previous permutation here,
// but rather, the first permutation of that particular "column";
// here, using `r` `,i`, `len`, would be
// `res[i - (i - 1) % (total / len)]`
var curr = prev.slice();
// this may be useful, to retrieve `r`,
// `prev` without item at `r` `index`
curr.splice(prev.indexOf(next), 1);
// this is not optiomal
curr.sort(function(a, b) {
return arr.indexOf(a) > arr.indexOf(b)
});
// place `next` at `index` `0`
// place remainder of sorted array at `index` `1` - n
curr.splice(0, 0, next)
res[i] = curr
}
idx = reset;
} else {
if (i % 2) {
// odd
res[i] = prev.slice(0, len - 2).concat(prev.slice(-2)
.reverse())
} else {
//  even
--idx
res[i] = prev.slice(0, len - (len - 1))
.concat(prev.slice(idx), prev.slice(1, len + (idx)))
}
}
}
// try with `arr` : `[1,2,3,4,5]` to return `res` that is not correct;
// how can above `js` be adjusted to return correct results for `[1,2,3,4,5]` ?
console.log(res, res.length)``````

Resources:

Generating all Permutations [non-recursive] (Attempt to port to from `C++` to `javascript` jsfiddle http://jsfiddle.net/tvvvjf3p/)

Calculating Permutation without Recursion - Part 2

permutations of a string using iteration

iterative-permutation

Permutations by swapping

Evaluation of permutation algorithms

Permutation algorithm without recursion? Java

Non-recursive algorithm for full permutation with repetitive elements?

String permutations in Java (non-recursive)

Generating permutations lazily

How to generate all permutations of a list in Python

Can all permutations of a set or string be generated in O(n log n) time?

Finding the nth lexicographic permutation of ‘0123456789’

Combinations and Permutations I think this post should help you. The algorithm should be easily translatable to JavaScript (I think it is more than 70% already JavaScript-compatible).

`slice` and `reverse` are bad calls to use if you are after efficiency. The algorithm described in the post is following the most efficient implementation of the next_permutation function, that is even integrated in some programming languages (like C++ e.g.)

EDIT

As I iterated over the algorithm once again I think you can just remove the types of the variables and you should be good to go in JavaScript.

EDIT

JavaScript version:

``````function nextPermutation(array) {
// Find non-increasing suffix
var i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i])
i--;
if (i <= 0)
return false;

// Find successor to pivot
var j = array.length - 1;
while (array[j] <= array[i - 1])
j--;
var temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;

// Reverse suffix
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return true;
}
`````` One method to create permutations is by adding each element in all of the spaces between elements in all of the results so far. This can be done without recursion using loops and a queue.

JavaScript code:

``````function ps(a){
var res = [[]];

for (var i=0; i<a.length; i++){
while(res[res.length-1].length == i){
var l = res.pop();
for (var j=0; j<=l.length; j++){
var copy = l.slice();
copy.splice(j,0,a[i]);
res.unshift(copy);
}
}
}
return res;
}

console.log(JSON.stringify(ps(['a','b','c','d'])));
`````` Here could be another solution, inspired from the Steinhaus-Johnson-Trotter algorithm:

``````function p(input) {
var i, j, k, temp, base, current, outputs = [[input]];
for (i = 1; i < input.length; i++) {
current = [];
for (j = 0; j < outputs.length; j++) {
base = outputs[j];
for (k = 0; k <= base.length; k++) {
temp = base.slice();
temp.splice(k, 0, input[i]);
current.push(temp);
}
}
outputs = current;
}
return outputs;
}

// call

var outputs = p(["a", "b", "c", "d"]);
for (var i = 0; i < outputs.length; i++) {
document.write(JSON.stringify(outputs[i]) + "<br />");
}`````` Here's a snippet for an approach that I came up with on my own, but naturally was also able to find it described elsewhere:

``````generatePermutations = function(arr) {
if (arr.length < 2) {
return arr.slice();
}
var factorial = ;
for (var i = 1; i <= arr.length; i++) {
factorial.push(factorial[factorial.length - 1] * i);
}

var allPerms = [];
for (var permNumber = 0; permNumber < factorial[factorial.length - 1]; permNumber++) {
var unused = arr.slice();
var nextPerm = [];
while (unused.length) {
var nextIndex = Math.floor((permNumber % factorial[unused.length]) / factorial[unused.length - 1]);
nextPerm.push(unused[nextIndex]);
unused.splice(nextIndex, 1);
}
allPerms.push(nextPerm);
}
return allPerms;
};``````
``````Enter comma-separated string (e.g. a,b,c):
<br/>
<input id="arrInput" type="text" />
<br/>
<button onclick="perms.innerHTML = generatePermutations(arrInput.value.split(',')).join('<br/>')">
Generate permutations
</button>
<br/>
<div id="perms"></div>``````

Explanation

Since there are `factorial(arr.length)` permutations for a given array `arr`, each number between `0` and `factorial(arr.length)-1` encodes a particular permutation. To unencode a permutation number, repeatedly remove elements from `arr` until there are no elements left. The exact index of which element to remove is given by the formula `(permNumber % factorial(arr.length)) / factorial(arr.length-1)`. Other formulas could be used to determine the index to remove, as long as it preserves the one-to-one mapping between number and permutation.

Example

The following is how all permutations would be generated for the array `(a,b,c,d)`:

``````#    Perm      1st El        2nd El      3rd El    4th El
0    abcd   (a,b,c,d)   (b,c,d)   (c,d)   (d)
1    abdc   (a,b,c,d)   (b,c,d)   (c,d)   (c)
2    acbd   (a,b,c,d)   (b,c,d)   (b,d)   (d)
3    acdb   (a,b,c,d)   (b,c,d)   (b,d)   (b)
4    adbc   (a,b,c,d)   (b,c,d)   (b,c)   (c)
5    adcb   (a,b,c,d)   (b,c,d)   (b,c)   (b)
6    bacd   (a,b,c,d)   (a,c,d)   (c,d)   (d)
7    badc   (a,b,c,d)   (a,c,d)   (c,d)   (c)
8    bcad   (a,b,c,d)   (a,c,d)   (a,d)   (d)
9    bcda   (a,b,c,d)   (a,c,d)   (a,d)   (a)
10   bdac   (a,b,c,d)   (a,c,d)   (a,c)   (c)
11   bdca   (a,b,c,d)   (a,c,d)   (a,c)   (a)
12   cabd   (a,b,c,d)   (a,b,d)   (b,d)   (d)
13   cadb   (a,b,c,d)   (a,b,d)   (b,d)   (b)
14   cbad   (a,b,c,d)   (a,b,d)   (a,d)   (d)
15   cbda   (a,b,c,d)   (a,b,d)   (a,d)   (a)
16   cdab   (a,b,c,d)   (a,b,d)   (a,b)   (b)
17   cdba   (a,b,c,d)   (a,b,d)   (a,b)   (a)
18   dabc   (a,b,c,d)   (a,b,c)   (b,c)   (c)
19   dacb   (a,b,c,d)   (a,b,c)   (b,c)   (b)
20   dbac   (a,b,c,d)   (a,b,c)   (a,c)   (c)
21   dbca   (a,b,c,d)   (a,b,c)   (a,c)   (a)
22   dcab   (a,b,c,d)   (a,b,c)   (a,b)   (b)
23   dcba   (a,b,c,d)   (a,b,c)   (a,b)   (a)
``````

Note that each permutation # is of the form:

``````(firstElIndex * 3!) + (secondElIndex * 2!) + (thirdElIndex * 1!) + (fourthElIndex * 0!)
``````

which is basically the reverse process of the formula given in the explanation. I dare to add another answer, aiming at answering you question regarding `slice`, `concat`, `reverse`.

The answer is it is possible (almost), but it would not be quite effective. What you are doing in your algorithm is the following:

• Find the first inversion in the permutation array, right-to-left (inversion in this case defined as `i` and `j` where `i` < `j` and `perm[i]` > `perm[j]`, indices given left-to-right)
• place the bigger number of the inversion
• concatenate the processed numbers in reversed order, which will be the same as sorted order, as no inversions were observed.
• concatenate the second number of the inversion (still sorted in accordsnce with the previos number, as no inversions were observed)

This is mainly, what my first answer does, but in a bit more optimal manner.

Example

Consider the permutation 9,10, 11, 8, 7, 6, 5, 4 ,3,2,1 The first inversion right-to-left is 10, 11. And really the next permutation is: 9,11,1,2,3,4,5,6,7,8,9,10=9concat(11)concat(rev(8,7,6,5,4,3,2,1))concat(10)

Source code Here I include the source code as I envision it:

``````var nextPermutation = function(arr) {
for (var i = arr.length - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
return arr.slice(0, i).concat([arr[i + 1]]).concat(arr.slice(i + 2).reverse()).concat([arr[i]]);
}
}
// return again the first permutation if calling next permutation on last.
return arr.reverse();
}

console.log(nextPermutation([9, 10, 11, 8, 7, 6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([1, 2, 3, 4, 5, 6]));
``````

The code is avaiable for jsfiddle here. A fairly simple C++ code without recursion.

``````#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>

// Integer data
void print_all_permutations(std::vector<int> &data) {
std::stable_sort(std::begin(data), std::end(data));
do {
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << '\n';
} while (std::next_permutation(std::begin(data), std::end(data)));
}

// Character data (string)
void print_all_permutations(std::string &data) {
std::stable_sort(std::begin(data), std::end(data));
do {
std::copy(data.begin(), data.end(), std::ostream_iterator<char>(std::cout, " ")), std::cout << '\n';
} while (std::next_permutation(std::begin(data), std::end(data)));
}

int main()
{
std::vector<int> v({1,2,3,4});
print_all_permutations(v);

std::string s("abcd");
print_all_permutations(s);

return 0;
}
``````

We can find next permutation of a sequence in linear time. Here is a simple solution to compute the nth permutation of a string:

``````function string_nth_permutation(str, n) {
var len = str.length, i, f, res;

for (f = i = 1; i <= len; i++)
f *= i;

if (n >= 0 && n < f) {
for (res = ""; len > 0; len--) {
f /= len;
i = Math.floor(n / f);
n %= f;
res += str.charAt(i);
str = str.substring(0, i) + str.substring(i + 1);
}
}
return res;
}
``````

The algorithm follows these simple steps:

• first compute `f = len!`, there are `factorial(len)` total permutations of a set of `len` different elements.
• as the first element, divide the permutation number by `(len-1)!` and chose the element at the resulting offset. There are `(len-1)!` different permutations that have any given element as their first element.
• remove the chosen element from the set and use the remainder of the division as the permutation number to keep going.
• perform these steps with the rest of the set, whose length is reduced by one.

This algorithm is very simple and has interesting properties:

• It computes the n-th permutation directly.
• If the set is ordered, the permutations are generated in lexicographical order.
• It works even if set elements cannot be compared to one another, such as objects, arrays, functions...
• Permutation number `0` is the set in the order given.
• Permutation number `factorial(a.length)-1` is the last one: the set `a` in reverse order.
• Permutations outside this range are returned as undefined.

It can easily be converted to handle a set stored as an array:

``````function array_nth_permutation(a, n) {
var b = a.slice();  // copy of the set
var len = a.length; // length of the set
var res;            // return value, undefined
var i, f;

// compute f = factorial(len)
for (f = i = 1; i <= len; i++)
f *= i;

// if the permutation number is within range
if (n >= 0 && n < f) {
for (res = []; len > 0; len--) {
// determine the next element:
// there are f/len subsets for each possible element,
f /= len;
// a simple division gives the leading element index
i = Math.floor(n / f);
// alternately: i = (n - n % f) / f;
res.push(b.splice(i, 1));
// reduce n for the remaining subset:
// compute the remainder of the above division
n %= f;
// extract the i-th element from b and push it at the end of res
}
}
// return the permutated set or undefined if n is out of range
return res;
}
``````

clarification:

• `f` is first computed as `factorial(len)`.
• For each step, `f` is divided by `len`, giving exacty the previous factorial.
• `n` divided by this new value of `f` gives the slot number among the `len` slots that have the same initial element. Javascript does not have integral division, we could use `(n / f) ... 0)` to convert the result of the division to its integral part but it introduces a limitation to sets of 12 elements. `Math.floor(n / f)` allows for sets of up to 18 elements. We could also use `(n - n % f) / f`, probably more efficient too.
• `n` must be reduced to the permutation number within this slot, that is the remainder of the division `n / f`.

We could use `i` differently in the second loop, storing the division remainder, avoiding `Math.floor()` and the extra `%` operator. Here is an alternative for this loop that may be even less readable:

``````        // start with the empty set, loop for len elements
for (res = []; len > 0; len--) {
i = n % (f /= len);
res.push(b.splice((n - i) / f, 1));
n = i;
}
`````` Here is an answer from @le_m. It might be of help.

The following very efficient algorithm uses Heap's method to generate all permutations of N elements with runtime complexity in O(N!):

``````function permute(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;

while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}

console.log(JSON.stringify(permute([1, 2, 3, 4])));``````