system
Given the following post, respond as if you're commenting on Reddit:
human
How could you recursively find all permutations of a list?

I'm trying to write a program that does this, but I'm having trouble thinking of how to solve this algorithmically. I've been trying to understand other people's solutions for hours and I'm just not getting it. Can someone please try to explain what algorithm you can use to recursively find all permutations of a list of any size?
gpt
Recursion is all about defining the simplest possible case and building up from there. How do you find all permutations of [1]? Easy. How about [1,2]? Still pretty easy. The pattern starts to reveal itself around length 3:

    [1,2,3]  [1, (permutate [2,3])]
    [1,3,2]  ...
    [2,1,3]  [2, (permutate [1,3])]
    [2,3,1]  ...
    [3,1,2]  [3, (permutate [1,2])]
    [3,2,1]  ...

See it? All the permutations of [2,3] start with 1. All perms of [1,3] start with 2. This is the basis for using recursion.

Here's some pseudo code:

    def permutations(list):
      if len(list) == 1:
        return [list]
      
      result = []
      for x of list:
        for p of permutations(listWithoutX):
          result.push([x, ...p])
      return result

Keep in mind that you want the index of x to efficiently grab the listWithoutX. In JS, you could do:

    listWithoutX = [...list.slice(0, i), ...list.slice(i + 1)]

Because `list.filter(v => v == x)`will iterate over the list instead of just chopping it up.

tl;dr perms of list with length 1 is itself, perms of any other list is perms of all lists 1 length less with whatever's missing in front.