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. 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
– Azar, Commented Mar 1, 2015 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
– MightyPork, Commented Mar 1, 2015 at 14:03
@MightyPork In that case, your question should be marked as a duplicate. — Chetan Kinger
– Chetan Kinger, Commented Mar 1, 2015 at 14:06

Miljen Mikic · Accepted Answer · 2015-03-01 14:28:39Z

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 1, 2015 at 14:28

Miljen Mikic

15.3k8 gold badges64 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Eric · Accepted Answer · 2015-03-01 17:22:50Z

3

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);
    }
}

edited Mar 1, 2015 at 17:22

answered Mar 1, 2015 at 15:50

Eric

25.8k26 gold badges168 silver badges232 bronze badges

1 Comment

geobudex Over a year ago

Why backtrack? @Eric

Ankush G · Accepted Answer · 2016-07-26 07:28:11Z

3

@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);
}

answered Jul 26, 2016 at 7:28

Ankush G

1,09111 silver badges17 bronze badges

Comments

tonychow0929 · Accepted Answer · 2015-03-01 14:24:53Z

1

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.

answered Mar 1, 2015 at 14:24

tonychow0929

4664 silver badges11 bronze badges

1 Comment

tonychow0929 Over a year ago

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

Oneiros · Accepted Answer · 2017-06-21 20:48:26Z

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.

Luka Rahne · Accepted Answer · 2015-03-01 14:12:26Z

0

Try with

testPermu(start + 1);

answered Mar 1, 2015 at 14:12

Luka Rahne

10.6k4 gold badges38 silver badges60 bronze badges

Comments

Darren · Accepted Answer · 2015-03-01 16:30:48Z

-1

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;      
}

edited Mar 1, 2015 at 16:30

answered Mar 1, 2015 at 15:17

Darren

7827 silver badges13 bronze badges

Comments

posdef · Accepted Answer · 2015-03-01 14:04:25Z

-2

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.

answered Mar 1, 2015 at 14:04

posdef

6,58211 gold badges50 silver badges97 bronze badges

Collectives™ on Stack Overflow

Go through all permutations of an array recursively

8 Answers 8

Comments

1 Comment

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

Comments

1 Comment

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related