guest271314 - 6 months ago 41

Javascript Question

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`

`6`

`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()`

`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

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()`

`js`

`res`

Noticed even , odd balance of calls and tried to use modulus

`%`

`.length`

`.reverse()`

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

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`

`.reverse()`

`.reverse()`

`res[0]`

`// 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()`

`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`

`for`

`.length`

`5`

The pattern is based on the second chart at

Would prefer not to use

`.splice()`

`.sort()`

`r`

`index`

The use of

`.splice()`

`.sort()`

`js`

Not entirely certain that the issue with

`js`

`if (i % (total / len) === reset)`

Specifically, now referring to the chart, at rotating , for example

`2`

`0`

`1`

`2`

`r`

`index`

`0`

At next column,

`2`

`index`

`2`

`3`

`index`

`0`

Again, returns expected results for

`[1,2,3,4]`

`[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++`

`javascript`

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

Answer

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;
}
```