guest271314 - 1 year ago 222
Javascript Question

# 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[0] = arr;

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

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

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

res[4] = res[3].slice(-2).concat(res[3].slice(0,1));

res[5] = res[4].slice(0,1).concat(res[4].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[0]`
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[0] = arr;

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

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

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

res[4] = res[3].slice(-2).concat(res[3].slice(0, 1));

res[5] = res[4].slice(0, 1).concat(res[4].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"[0].

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`

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[0]].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[0]), 1);
// this is not optiomal
curr.sort(function(a, b) {
return arr.indexOf(a) > arr.indexOf(b)
});
// place `next[0]` at `index` `0`
// place remainder of sorted array at `index` `1` - n
curr.splice(0, 0, next[0])
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 Permutation with Javascript

(Countdown) QuickPerm Head Lexicography:
(Formally Example_03 ~ Palindromes)

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

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) {
// start with the empty set, loop for len elements
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)[0]);
// 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)[0]);
n = i;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download