Print out all permutations of an Array

Question

I am working on a program, and I have a function that swaps the positions in an Array of length that is input by a user. However, I am trying to figure out how to print out this function call N! times, which would list all the permutations in the function.

My code for the permutation function is:

static void nextPerm(int[] A){
    for( int i = (n-1); i > 0; i-- ){
        if( A[i] < A[i+1] ){
            A[i] = pivot;
            continue;
        }
        if( A[i] >= A[i+1] ){
            reverseArray(A);
            return;
        }
    }

    for( int i = n; i > 0; i--){
        if( A[i] > pivot ){
            A[i] = successor;
            continue;
        }
    }

    Swap(pivot, successor);

    int[] B = new int[pivot+1];
    reverseArray(B);

    return;
}

Should I write a loop in function main, that will print this out n! times?

Solution 1

Creating (or printing) the permutations of an array is much easier done as a combination of recursively and iteratively than purely iteratively. There are surely iterative ways to do it, but it is particularly simple with a combination. Specifically, note that there are by definition N! permutations of a length N array - N choices for the first slot, N-1 choices for the 2nd, etc etc. So, we can break an algorithm down into two steps for each index i in the array.

1. Select an element in the sub-array arr[i....end] to be the ith element of the array. Swap that element with the element currently at arr[i].
2. Recursively permute arr[i+1...end].

We note that this will run in O(N!), as on the 1st call N sub calls will be made, each of which will make N-1 sub calls, etc etc. Moreover, every element will end up being in every position, and so long as only swaps are made no element will ever be duplicated.

public static void permute(int[] arr){
    permuteHelper(arr, 0);
}

private static void permuteHelper(int[] arr, int index){
    if(index >= arr.length - 1){ //If we are at the last element - nothing left to permute
        //System.out.println(Arrays.toString(arr));
        //Print the array
        System.out.print("[");
        for(int i = 0; i < arr.length - 1; i++){
            System.out.print(arr[i] + ", ");
        }
        if(arr.length > 0) 
            System.out.print(arr[arr.length - 1]);
        System.out.println("]");
        return;
    }

    for(int i = index; i < arr.length; i++){ //For each index in the sub array arr[index...end]

        //Swap the elements at indices index and i
        int t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;

        //Recurse on the sub array arr[index+1...end]
        permuteHelper(arr, index+1);

        //Swap the elements back
        t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;
    }
}

Sample input, output:

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

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

Solution 2

I have followed this method most of the time .. (it's given by the Robert Sedgewick and Kevin Wayne. ).

public class Permutations {

    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s) { perm1("", s); }
    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0) System.out.println(prefix);
        else {
            for (int i = 0; i < N; i++)
               perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s) {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n) {
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j) {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

However There is also an easier way to do this. May be you can work also around this

class PermutingArray {
    static void permutingArray(java.util.List<Integer> arrayList, int element) {
        for (int i = element; i < arrayList.size(); i++) {
            java.util.Collections.swap(arrayList, i, element);
            permutingArray(arrayList, element + 1);
            java.util.Collections.swap(arrayList, element, i);
        }
        if (element == arrayList.size() - 1) {
            System.out.println(java.util.Arrays.toString(arrayList.toArray()));
        }
    }

    public static void main(String[] args) {
        PermutingArray
                .permutingArray(java.util.Arrays.asList(9, 8, 7, 6, 4), 0);
    }
}

Working Example here .. IDeone Link

Solution 3

The trick is to return a special value (false in the code below) from nextPerm when it was the last permutation (i.e. when array become sorted in descending order):

import java.util.*;

public class Main {
    public static boolean nextPerm(List<Integer> a) {
        int i = a.size() - 2;
        while (i >= 0 && a.get(i) >= a.get(i + 1))
            i--;

        if (i < 0)
            return false;

        int j = a.size() - 1;
        while (a.get(i) >= a.get(j))
            j--;

        Collections.swap(a, i, j);
        Collections.reverse(a.subList(i + 1, a.size()));
        return true;
    }
    ...

Then you can use the loop (note that the array required be sorted in ascending order initially):

    ...
    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(new Integer[] {1, 2, 3, 4});
        do {
            System.out.println(a);
        } while (nextPerm(a));
    }
}

You can try this code here: http://ideone.com/URDFsc

Comments

[Admin]

I'm trying to do this without using the package java.utl.Arrays

[Zizouz212]

It doesn't use util.arrays...

[Admin]

My function can only have parameters Int[] A

[Mshnik]

1) Replaced Arrays.toString(..) with the by-hand version. It's literally the same thing, just doing it out. 2) The permute function does only have parameter a single parameter of type int[]. Is creating helper functions off limits?

[droidnoob]

This is an amazing answer! Thank you so much

[Hungry Coder]

The second solution is so compact! Shows how good you are at Java API usage.