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

**URL:** <https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163>\
**Category:** Coding Questions\
**Created:** [June 7, 2023, 7:40pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163 "2023-06-07T19:40:15Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![jackeddielove](https://avatars.discourse-cdn.com/v4/letter/j/dc4da7/32.png) [@jackeddielove](https://discourse.processing.org/u/jackeddielove)\
**Post date:** [June 7, 2023, 7:40pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/1 "2023-06-07T19:40:16Z")

</div>

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

```

---

<div class="post-metadata">

**Author:** ![scudly](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/scudly/32/5597_2.png) [@scudly](https://discourse.processing.org/u/scudly)\
**Post date:** [June 8, 2023, 5:55am UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/2 "2023-06-08T05:55:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mnse](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/mnse/32/16520_2.png) [@mnse](https://discourse.processing.org/u/mnse)\
**Post date:** [June 8, 2023, 5:57am UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/3 "2023-06-08T05:57:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jackeddielove](https://avatars.discourse-cdn.com/v4/letter/j/dc4da7/32.png) [@jackeddielove](https://discourse.processing.org/u/jackeddielove)\
**Post date:** [June 8, 2023, 7:19pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/4 "2023-06-08T19:19:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jackeddielove](https://avatars.discourse-cdn.com/v4/letter/j/dc4da7/32.png) [@jackeddielove](https://discourse.processing.org/u/jackeddielove)\
**Post date:** [June 8, 2023, 7:20pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/5 "2023-06-08T19:20:40Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jackeddielove](https://avatars.discourse-cdn.com/v4/letter/j/dc4da7/32.png) [@jackeddielove](https://discourse.processing.org/u/jackeddielove)\
**Post date:** [June 8, 2023, 8:09pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/6 "2023-06-08T20:09:34Z")

</div>

followup question @scudly  
The code

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

---

<div class="post-metadata">

**Author:** ![scudly](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/scudly/32/5597_2.png) [@scudly](https://discourse.processing.org/u/scudly)\
**Post date:** [June 8, 2023, 8:53pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/7 "2023-06-08T20:53:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jackeddielove](https://avatars.discourse-cdn.com/v4/letter/j/dc4da7/32.png) [@jackeddielove](https://discourse.processing.org/u/jackeddielove)\
**Post date:** [June 8, 2023, 10:50pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/8 "2023-06-08T22:50:22Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![scudly](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/scudly/32/5597_2.png) [@scudly](https://discourse.processing.org/u/scudly)\
**Post date:** [June 9, 2023, 11:29pm UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/9 "2023-06-09T23:29:04Z")

</div>

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.

```auto
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();
}

```

---

<div class="post-metadata">

**Author:** ![scudly](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/scudly/32/5597_2.png) [@scudly](https://discourse.processing.org/u/scudly)\
**Post date:** [June 10, 2023, 1:55am UTC](https://discourse.processing.org/t/recursive-function-for-generating-permutations-of-0-n/42163/10 "2023-06-10T01:55:57Z")

</div>

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:

```auto
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() );
}

```