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

p5.js Coding Questions
1 
// 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
2

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 ith 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.

3

Hi @jackeddielove,

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 :slight_smile:
  • 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

4

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

5

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.

6

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.

7

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
8

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
9

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
10

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