Algorithm to generate all possible permutations of

Question

Say I have a list of n elements, I know there are n! possible ways to order these elements. What is an algorithm to generate all possible orderings of this list? Example, I have list [a, b, c]. The algorithm would return [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].

I'm reading this here http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

But Wikipedia has never been good at explaining. I don't understand much of it.

Answer 1

I know this a very very old and even off-topic in today's stackoverflow but I still wanted to contribute a friendly javascript answer for the simple reason that it runs in your browser.

I've also added the debugger directive breakpoint so you can step through the code (chrome required) to see how this algorithm works. Open up your dev console in chrome (F12 in windows or CMD + OPTION + I on mac) and then click "Run code snippet". This implements the same exact algorithm that @WhirlWind presented in his answer.

Your browser should pause execution at the debugger directive. Use F8 to continue code execution.

Step through the code and see how it works!

function permute(rest, prefix = []) {
  if (rest.length === 0) {
    return [prefix];
  }
  return (rest
    .map((x, index) => {
      const oldRest = rest;
      const oldPrefix = prefix;
      // the `...` destructures the array into single values flattening it
      const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
      const newPrefix = [...prefix, x];
      debugger;

      const result = permute(newRest, newPrefix);
      return result;
    })
    // this step flattens the array of arrays returned by calling permute
    .reduce((flattened, arr) => [...flattened, ...arr], [])
  );
}
console.log(permute([1, 2, 3]));

Answer 2

This is a recursive code for java, the idea is to have a prefix that add the rest of the characters:

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str);
    }
}

Example:

Input = "ABC"; Output:

ABC ACB BAC BCA CAB CBA

Answer 3

Here is an algorithm in R, in case anyone needs to avoid loading additional libraries like I had to.

permutations <- function(n){
    if(n==1){
        return(matrix(1))
    } else {
        sp <- permutations(n-1)
        p <- nrow(sp)
        A <- matrix(nrow=n*p,ncol=n)
        for(i in 1:n){
            A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
        }
        return(A)
    }
}

Example usage:

> matrix(letters[permutations(3)],ncol=3)
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a" 

Answer 4

void permutate(char[] x, int i, int n){
    x=x.clone();
    if (i==n){
        System.out.print(x);
        System.out.print(" ");
        counter++;}
    else
    {
        for (int j=i; j<=n;j++){
     //   System.out.print(temp); System.out.print(" ");    //Debugger
        swap (x,i,j);
      //  System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger
        permutate(x,i+1,n);
    //    swap (temp,i,j);
    }
    }
}

void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}

I created this one. based on research too permutate(qwe, 0, qwe.length-1); Just so you know, you can do it with or without backtrack

Answer 5

Here is the code in Python to print all possible permutations of a list:

def next_perm(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    print arr
    return True

def all_perm(arr):
    a = next_perm(arr)
    while a:
        a = next_perm(arr)
    arr = raw_input()
    arr.split(' ')
    arr = map(int, arr)
    arr.sort()
    print arr
    all_perm(arr)

I have used a lexicographic order algorithm to get all possible permutations, but a recursive algorithm is more efficient. You can find the code for recursive algorithm here: Python recursion permutations

Answer 6

Bourne shell solution - in a total of four lines (without test for no param case):

test $# -eq 1 && echo "$1" && exit
for i in $*; do
  $0 `echo "$*" | sed -e "s/$i//"` | sed -e "s/^/$i /"
done