# Recursive function for generating permutations of [0, ..., n]

``````// trying to write a recursive function that returns all the permutations of [0, ..., n], for example:
// perms(0) = [[0]]
// perms(1) = [[0, 1], [1, 0]]
// perms(2) = [[0, 1, 2], [0, 2, 1], [2, 0, 1], [1, 0, 2], [1, 2, 0], [2, 1, 0]]
// the idea is to build perms(n) by taking each element of perms(n-1) and creating n+1 new elements
// by putting n in each possible slot. In the example above, the first three entries of perms(2) are
// generated by taking the first entry in perms(1) and sticking a 2 in there at the end, middle, or beginning.
// my function works fine if I explicitly define perms(n-1) and call perms(n) --
// meaning, if I define perms(2), my code will produce perms(3) no problem.
// but the recursion is not working past that... what's going on?

function perms(n) {
if (n == 0) {
return [[0]];
}

list = [];
for (i = 0; i <= perms(n - 1).length - 1; i++) {
for (j = n; j >= 0; j--) {
perm = [];

for (k = 0; k <= n; k++) {
if (k < j) {
append(perm, perms(n - 1)[i][k]);
}
if (k == j) {
append(perm, n);
}
if (k > j) {
append(perm, perms(n - 1)[i][k - 1]);
}
}
append(list, perm);
}
}
return list;
}
}
``````
1 Like

Your function calls `perms(n-1)` every time you test the loop variable `i`. That is a huge number of executions that are all returning the exact same list and will cause your program to take an absurd amount of time to run. Instead, call `perms(n-1)` just once and store the result in a local variable before your loops and only refer to the smaller permutations from that list.

Likewise, inside the `for( i ... )` loop, use a local variable to store the `i`th permutation out of your list. That both makes it simpler for you to keep track of the indexing and makes it run faster.

It seems to me that your algorithm should only have two loops. The outer loop chooses each one of the smaller (1 â€¦ n-1) permutations. The inner loop generates `n` new permutations by putting the number `n` in each of the `n` possible positions between the smaller permutationâ€™s numbers. Oh, I guess youâ€™re building up the array using the 3rd loop. Try using the javascript function `slice()` instead â€“ `perm` is the slice the first j numbers, append `n`, append the slice of the `j` to `n-1` numbers, maybe with a special case for the first or last case.

As this looks like a homework just a few suggestionsâ€¦

• Donâ€™t call `perms(n-1)` multiple times. Just assign it once to a variable before the for first loop.
• ` i <= some.length -1` is the same as `i < some.length` in your for loop
• I would use `perms.push(...)` instead of `append(perms,...)` but doesnâ€™t matter
• To check if the amount of list results are plausible you can calc it by `n!`, but keep in mind, as you are including 0 n means `(n+1)!` in your caseâ€¦

Beside that your code seems plausible and should work!

Cheers
â€” mnse

Thank you thank you, super helpful. I will try this.

Thank you, this is helpful. Not a homework, just part of a personal project, but I could imagine this being a good homework problem. Thank you again.

followup question @scudly
The code

``````  A = [0];
B = A;
splice(B, 1, 1);
``````

Makes B equal to [0,1] as expected, but also makes A equal to [0,1]. Why is that? I need to keep one list untouched so I can make a bunch of copies with different splices.

Use `slice()`, not `splice()` to read out a copy of part of an array.

And if you say `B = A` on an array, then both `B` and `A` will point to the same array. `A` and `B` are really just the memory address of where the array values are stored in computer memory.

2 Likes

i see, so anytime you change one of them, the other changes as well. Thanks, slice is what i need since it doesnâ€™t alter the originalâ€“got it!

1 Like

Here is some simpler code to generate all the permutations without having to store them all. Itâ€™s in Java Processing, but should be trivial to convert to javascript. Rather than creating a full list of all of the permutations, it instead shuffles the order of a single array through all of its permutations and then lets you do something with each ordering. If you really want a full list, have `do_something()` copy `v` to a new array and append the copy to your list.

The permutation works by swapping the kth element with each of the 0 through k elements and then permuting the 0 through k-1 elements before swapping them back.

``````void setup() {
char[] v = { 'a', 'b', 'c', 'd' };
permute( v, v.length );
}

void permute( char[] v, int k ) {
if( k > 1 ) {
k--;
char vk = v[k];
for( int i=k; i>=0; i-- ) {
v[k] = v[i];
v[i] = vk;
permute( v, k );
v[i] = v[k];
}
v[k] = vk;
} else
do_something( v );
}

void do_something( char[] v ) {
for( int i=0; i<v.length; i++ )
print( v[i], " " );
println();
}
``````
1 Like

So, I donâ€™t normally use javascript, but it looks like it lets you swap array elements in place. Hereâ€™s the even more compact javascript version of the permutations using p5:

``````function setup() {
let v = [ 'a', 'b', 'c', 'd' ];
permute( v, v.length, show_perm );
}

function permute( v, k, fn ) {
if( k > 1 ) {
k--;
for( let i=k; i>=0; i-- ) {
[ v[i], v[k] ] = [ v[k], v[i] ];
permute( v, k, fn );
[ v[i], v[k] ] = [ v[k], v[i] ];
}
} else {
fn( v );
}
}

function show_perm( v ) {
createP( v.toString() );
}

``````
1 Like