Go through all permutations of an array recursively

Question

I am trying to write a recursive function to produce all permutations of an array.

static int permus[] = new int[] { 1, 2, 3, 4, 5 };


static void testPermu(int start)
{
    // Print it
    System.out.println(Arrays.toString(permus));

    int k;
    for (int i = start + 1; i < permus.length; i++) {
        // swap
        k = permus[start];
        permus[start] = permus[i];
        permus[i] = k;

        testPermu(i);

        // unswap
        k = permus[start];
        permus[start] = permus[i];
        permus[i] = k;
    }
}

It's invoked as testPermu(0) and should produce all permutations, however that does not work. How can I fix it?

It needs to be recursive, each time the function is invoked, it should get a fresh permutation.

output now is

[1, 2, 3, 4, 5]
[2, 1, 3, 4, 5]
[2, 3, 1, 4, 5]
[2, 3, 4, 1, 5]
[2, 3, 4, 5, 1]
[2, 3, 5, 4, 1]
[2, 4, 3, 1, 5]
[2, 4, 3, 5, 1]
[2, 5, 3, 4, 1]
[3, 2, 1, 4, 5]
[3, 2, 4, 1, 5]
[3, 2, 4, 5, 1]
[3, 2, 5, 4, 1]
[4, 2, 3, 1, 5]
[4, 2, 3, 5, 1]
[5, 2, 3, 4, 1]

You can see that many of the permutations are missing.

I'm writing it in Java but I'll understand example in C, javascript or anything else as long as it's not using some library tricks not available in Java.

See [here](http://stackoverflow.com/a/20906510/2206044). I would try to model my code after that. I'm not sure, but I think your problems could be stemming from using a single static array. — Azar, Mar 01 '15 at 14:00
I'm quite certain the example you linked also uses the same array everywhere, it's passed by reference. I'll try copy that approach (seems largely the same as mine :D) — MightyPork, Mar 01 '15 at 14:03
@MightyPork In that case, your question should be marked as a duplicate. — Chetan Kinger, Mar 01 '15 at 14:06

score 4 · Answer 1 · answered Mar 01 '15 at 14:28

4

Three corrections are needed in order to work:

print only if (start == permus.length-1), otherwise you'll see duplicates
start the for loop from i = start, not i = start + 1
recursively call testPermu(start + 1); instead of testPermu(i);

answered Mar 01 '15 at 14:28

Miljen Mikic

14,765
8
58
66

Eric · Accepted Answer · 2015-03-01T17:22:50.393

Here is a full example:

package eric.math;

import java.util.Arrays;

public class Permute {
    // swap 2 elements of an array,
    void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    /**
     * print permutations of array
     * @param arr
     *            original int array,
     */
    void permute(int[] arr) {
        permute(arr, 0, arr.length - 1);
    }

    /**
     * print permutations of array
     * 
     * @param arr
     *            original int array,
     * @param i
     *            start index
     * @param n
     *            end index
     */
    void permute(int[] arr, int i, int n) {
        int j;
        if (i == n)
            System.out.println(Arrays.toString(arr));
        else {
            for (j = i; j <= n; j++) {
                swap(arr, i, j);
                permute(arr, i + 1, n);
                swap(arr, i, j); // backtrack
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3 };
        new Permute().permute(arr);
    }
}

score 3 · Answer 3 · answered Jul 26 '16 at 07:28

@Enric solution is nice, but using solution below we can avoid 80 swaps and perform only 24 swaps.

static void permutation(int[] a, int i, int j) {
    for (; j < a.length && i < a.length; j++) {
        int[] temp = null;
        if (i != j) {
            temp =  swap(a, i, j);
            System.out.println(Arrays.toString(temp));
        }else{
            temp = a;
        }
        permutation(temp, i + 1, i + 1);
    }
}

public static void main(String[] args) {
    int[] a = { 0, 1, 2, 3 };
    permutation(a, 0, 0);
}

score 1 · Answer 4 · answered Mar 01 '15 at 14:24

Another approach:

static ArrayList<ArrayList<Integer>> getPermutation(ArrayList<Integer> ints) {
    if (ints.size() == 1) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        list.add(ints);
        return list;
    } else {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (Integer i: ints) {
            ArrayList<Integer> subList = new ArrayList<>(ints);
            subList.remove(i);
            ArrayList<ArrayList<Integer>> subListNew = getPermutation(subList);
            for (ArrayList<Integer> _list: subListNew) {
                ArrayList<Integer> local = new ArrayList<>();
                local.add(i);
                local.addAll(_list);
                list.add(local);
            }
        }
        return list;
    }
}

This method first selects an element, removes it and obtains a sub-list, then produces a permutation of the sub-list until the list size becomes 1.

The underlying principle is actually same, but using ArrayList is much more convenience. You may also look at System.arraycopy if you want to implement the method in simple array, or do the conversion using Arrays.asList() and list's toArray() method — tonychow0929, Mar 01 '15 at 14:30

score 1 · Answer 5 · answered Jun 21 '17 at 20:48

I like @tony200910041 approach but maybe someone would like a cleaner and more generic version of it:

public static <T> List<List<T>> getPermutations(List<T> list) {
  if (list.size() == 1)
    return Collections.singletonList(list);

  List<List<T>> perms = new ArrayList<>();
  for (T element: list) {
    List<T> subList = new ArrayList<>(list);
    subList.remove(element);
    List<List<T>> subPerms = getPermutations(subList);
    for (List<T> subPerm: subPerms) {
      List<T> perm = new ArrayList<>();
      perm.add(element);
      perm.addAll(subPerm);
      perms.add(perm);
    }
  }
  return perms;
}

Sort the list before passing it to the getPermutations() function if you want your permutations in ascending order.

score 0 · Answer 6 · answered Mar 01 '15 at 14:12

0

Try with

testPermu(start + 1);

answered Mar 01 '15 at 14:12

Luka Rahne

10,336
3
34
56

Darren · Answer 7 · 2015-03-01T16:30:48.550

You can do it simply without recursion

public static Integer[] permutate(int i)
{
    int length = permus.length;
    Integer[] result = new Integer[length];

    List<Integer> chosen = new ArrayList<Integer>(Arrays.asList(permus));

    int divider = 1;
    for (int j=2; j<length; j++)
    {
        divider *= j;
    }

    for (int j=length; j>1; j--)
    {
        int index = i/divider;
        result[length - j] = chosen.remove(index);
        i = i - divider * (i/divider);
        divider = divider / (j-1);
    }
    result[length -1] = chosen.remove(0);

    return result;      
}

score -2 · Answer 8 · answered Mar 01 '15 at 14:04

How about the following algorithm (given in pseudocode)

iterate over elements:
   pick one of the element at random 
   call function again on the remaining elements
   if elements.size == 1 
       return or print

This should produce a valid permutation at each run. If you want all possible permutations, just accumulate as you iterate, then you should have all permutations.

Go through all permutations of an array recursively

8 Answers8

Linked