Permutation algorithm for array of integers in Java

Question

I have a working example to generate all char permutations in a String as below:

static ArrayList<String> permutations(String s) {
        if (s == null) {
            return null;
        }

        ArrayList<String> resultList = new ArrayList<String>();

        if (s.length() < 2) {
            resultList.add(s);

            return resultList;
        }

        int length = s.length();
        char currentChar;

        for (int i = 0; i < length; i++) {
            currentChar = s.charAt(i);

            String subString = s.substring(0, i) + s.substring(i + 1);

            ArrayList<String> subPermutations = permutations(subString);

            for (String item : subPermutations) {
                resultList.add(currentChar + item);
            }
        }

        return resultList;
    } 

I am trying to implement the same function, but to return ArrayList, and to get int[] as the parameter. I am doing this recursively as below:

static ArrayList<int[]> permutations(int[] arr) {
        ArrayList<int[]> resultList = new ArrayList<int[]>();

        if (arr.length < 2) {
            resultList.add(arr);

            return resultList;
        } 

        for (int i = 0; i < arr.length; i++) {
            int currentItem = arr[i];
            int[] newArr = new int[arr.length - 1];
            int[] newPermutation = new int[arr.length];
            int j;

//          System.arraycopy(arr, 0, newArr, 0, i);
//          System.arraycopy(arr, i + 1, newArr, i, arr.length - i - 1);

            for (j = 0; j < i; j++) {
                newArr[j] = arr[j];
            }

            for (j = i + 1; j < arr.length; j++) {
                newArr[j - 1] = arr[j];
            }

            ArrayList<int[]> subPermutations = permutations(newArr);

            newPermutation[0] = currentItem;

//          for (int i1 = 0; i1 < subPermutations.size(); i1++) {
//              for (j = 0; j < subPermutations.get(i1).length; j++) {
//                  newPermutation[j + 1] = subPermutations.get(i1)[j];
//              }
//              
//              resultList.add(newPermutation);
//          }

            for (int[] item : subPermutations) {
                for (j = 0; j < item.length; j++) {
                    newPermutation[j + 1] = item[j];
                }

                resultList.add(newPermutation);
            }

//          return resultList;
        }

        return resultList;
    }

When passing arrays of size 0, 1, and 2 as the parameter, everything is fine. For everything else greater than 2, I get the correct number of permutations, but they repeat themselves. Here is the result for size == 3, and passing { 1, 5, 4 }:

1 4 5 
1 4 5 
5 4 1 
5 4 1 
4 5 1 
4 5 1

Please give me some advice if you encountered these issues before.

Thanks in advance!

Answer 1

//Here is a recursive version that was not to hard to commit to human memory ! O(n!) permutations.

public static Set<Integer[]> getPermutationsRecursive(Integer[] num){
    if (num == null)
        return null;

    Set<Integer[]> perms = new HashSet<>();

    //base case
    if (num.length == 0){
        perms.add(new Integer[0]);
        return perms;
    }

    //shave off first int then get sub perms on remaining ints.
    //...then insert the first into each position of each sub perm..recurse

    int first = num[0];
    Integer[] remainder = Arrays.copyOfRange(num,1,num.length);
    Set<Integer[]> subPerms = getPermutationsRecursive(remainder);
    for (Integer[] subPerm: subPerms){
        for (int i=0; i <= subPerm.length; ++i){ // '<='   IMPORTANT !!!
            Integer[] newPerm = Arrays.copyOf(subPerm, subPerm.length+1);
            for (int j=newPerm.length-1; j>i; --j)
                newPerm[j] = newPerm[j-1];
            newPerm[i]=first;
            perms.add(newPerm);
        }
    }

    return perms;
}

Answer 2

Here is my solution (gist):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author Karol Krol
 */
public class Permutation {

    private Permutation() {
    }

    public static List<List<Integer>> permutation(final int[] numbers) {
        final PermutationCollector permutationCollector = new PermutationCollector();
        permutation(new int[0], numbers, permutationCollector);
        return permutationCollector.getResult();
    }

    private static void permutation(int[] prefix, int[] array, final Consumer<int[]> operation) {
        int length = array.length;
        if (length == 0) {
            operation.accept(prefix);
        } else {
            for (int i = 0; i < length; ++i) {
                final int[] newPrefix = append(prefix, array[i]);
                final int[] reducedArray = reduce(array, i);
                permutation(newPrefix, reducedArray, operation);
            }
        }
    }

    private static int[] append(int[] array, int element) {
        int newLength = array.length + 1;
        array = Arrays.copyOf(array, newLength);
        array[newLength - 1] = element;
        return array;
    }

    private static int[] reduce(int[] array, int index) {
        final int newLength = array.length - 1;
        if (index == 0) {
            return Arrays.copyOfRange(array, 1, array.length);
        } else {
            final int[] dest = new int[newLength];
            System.arraycopy(array, 0, dest, 0, index);
            System.arraycopy(array, index + 1, dest, index, newLength - index);
            return dest;
        }
    }

    public static class PermutationCollector implements Consumer<int[]> {

        private List<List<Integer>> result = new ArrayList<>();

        @Override
        public void accept(int[] ints) {
            result.add(IntStream.of(ints).boxed().collect(Collectors.toList()));
        }

        public List<List<Integer>> getResult() {
            return result;
        }
    }
}

Answer 3

/**
 * 
 * @param startIndex is the position of the suffix first element 
 * @param prefix is the prefix of the pattern 
 * @param suffix is the suffix of the pattern, will determine the complexity
 *  permute method.
 *
 * 
 * The block <code>if (suffix.length == 1)</code> will print
 * the only possible combination of suffix and return for computing next
 * combination.
 *
 *
 * The part after <code>if (suffix.length == 1)</code> is reached if suffix
 * length is not 1 that is there may be many possible combination of suffix
 * therefore make a <code>newSuffix</code> which will have suffix length
 * <code>(suffix.length - 1)</code> and recursively compute the possible
 * combination of this new suffix and also the original suffix prefix
 * positioned by <code>startIndex</code> will change by increasing its value
 * by one <code>(startIndex + 1) % suffix.length</code>
 * 
 * 
 * T(N) = N * T(N - 1) + N
 *      = N! + N!(1 + 1/N + 1/(N * (N - 1)) + ... + 1/N!)
 *      
 *
 */
public static void permute(int startIndex, int prefix[], int suffix[]) {
    if (suffix.length == 1) {
        for (int i = 0; i < prefix.length; i++) {
            System.out.print(prefix[i] + " ");
            }
        System.out.print(suffix[0]);
        System.out.println(" ");
        return;
    }

    for (int i = 0; i < suffix.length; i++) {
        counter++;
        int newPrefix[] = new int[prefix.length + 1];
        System.arraycopy(prefix, 0, newPrefix, 0, prefix.length);
        newPrefix[prefix.length] = suffix[startIndex];
        int newSuffix[] = new int[suffix.length - 1];
        for (int j = 1; j < suffix.length; j++) {
            newSuffix[j - 1] = suffix[(startIndex + j) % suffix.length];
        }
        permute((startIndex % newSuffix.length), newPrefix, newSuffix);
        startIndex = (startIndex + 1) % suffix.length;
    }
}

Answer 4

Here you go, the below sample code uses the recursive method to get the permutation. It is generic and you can specify the output location as you like. One bonus is you can specify delimiter as well.

import java.io.FileNotFoundException;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Permutation {
    //The entry of the permutation method
    public static <T> List<T[]> permute(T[] arr){
        List<T[]> result = new ArrayList<T[]>();
        permute(new ArrayList<T>(), Arrays.asList(arr), result);
        return result;
    }

    //This is the actual method doing the permutation
    private static <T> void permute(List<T> pre, List<T> cur, List<T[]> out){
        int size = cur.size();

        if(size == 0){
            out.add((T[])pre.toArray());
        } else {
            for(int i=0; i<size; ++i){
                List<T> tmpPre = new ArrayList<T>(pre);
                List<T> tmpCur = new ArrayList<T>(cur);
                tmpPre.add(cur.get(i));
                tmpCur.remove((T)cur.get(i));

                permute(tmpPre, tmpCur, out);       
            }
        }
    }

    //Print each row of the permutated values
    private static <T> void print(List<T[]> list, OutputStream out, char delim){
        try{
            for(T[] i : list){
                int count = 0;
                for(T t : i){
                    if(++count == i.length){
                        out.write((t.toString()).getBytes());
                    } else{
                        out.write((t.toString()+delim).getBytes());
                    }
                }
                out.write("\n".getBytes());
            }
        } catch (Exception ex){
            ex.printStackTrace();
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        Integer[] ints = new Integer[] {1, 2, 3, 4};
        Permutation.print(Permutation.permute(ints), System.out, ',');

        Character[] chars = {'a', 'b', 'c', 'd', 'e'};
        Permutation.print(Permutation.permute(chars), new PrintStream("permute.txt"), ' ');

        String[] strs = {"abc", "123"};
        Permutation.print(Permutation.permute(strs), System.err, ' ');
    }
}

Answer 5

Below is a class containing a solution using generics. The API is a bit different then what you specified but far more flexible. Easiest to see with examples. Note that the inputs probably have more constraints than what I'm checking here!

public static final class Permutations {
    private Permutations() {}

    public static <T> List<T[]> get(Class<T> itemClass, T... itemsPool) {
        return get(itemsPool.length, itemClass, itemsPool);
    }

    public static <T> List<T[]> get(int size, Class<T> itemClass, T... itemsPool) {
        if (size < 1) {
            return new ArrayList<T[]>();
        }

        int itemsPoolCount = itemsPool.length;

        List<T[]> permutations = new ArrayList<T[]>();
        for (int i = 0; i < Math.pow(itemsPoolCount, size); i++) {
            T[] permutation = (T[]) Array.newInstance(itemClass, size);
            for (int j = 0; j < size; j++) {
                // Pick the appropriate item from the item pool given j and i
                int itemPoolIndex = (int) Math.floor((double) (i % (int) Math.pow(itemsPoolCount, j + 1)) / (int) Math.pow(itemsPoolCount, j));
                permutation[j] = itemsPool[itemPoolIndex];
            }
            permutations.add(permutation);
        }

        return permutations;
    }
}

Example Usage

Calling Permutations.get(2, Integer.class, 1, 0, -1); will return the following list of integer arrays:

[ 1,  1]
[ 0,  1]
[-1,  1]
[ 1,  0]
[ 0,  0]
[-1,  0]
[ 1, -1]
[ 0, -1]
[-1, -1]

Calling Permutations.get(3, Integer.class, 1, 0, -1); will return the following list of integer arrays. Note that this example is identical to the first except for the first argument which is now 3:

[ 1,  1,  1]
[ 0,  1,  1]
[-1,  1,  1]
[ 1,  0,  1]
[ 0,  0,  1]
[-1,  0,  1]
[ 1, -1,  1]
[ 0, -1,  1]
[-1, -1,  1]
[ 1,  1,  0]
[ 0,  1,  0]
[-1,  1,  0]
[ 1,  0,  0]
[ 0,  0,  0]
[-1,  0,  0]
[ 1, -1,  0]
[ 0, -1,  0]
[-1, -1,  0]
[ 1,  1, -1]
[ 0,  1, -1]
[-1,  1, -1]
[ 1,  0, -1]
[ 0,  0, -1]
[-1,  0, -1]
[ 1, -1, -1]
[ 0, -1, -1]
[-1, -1, -1]

Answer 6

By adding a TreeSet it removes duplicates and sorts the permutations.

---

package permutations;

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;


public class Permutations {


public static void main(String args[])
{
    Scanner scanner = new Scanner(new InputStreamReader(System.in));
    System.out.println("This application accepts input of a string and creates a list of all     possible permutations\n\r");

    System.out.println("Please Enter a string of characters");
    String input = scanner.nextLine();

    String[] elements = input.split("");
    Permutations g = new Permutations();

    ArrayList<String> permutations = g.generatePermutations(elements);

    TreeSet ts = new TreeSet();
    for ( String s : permutations)
    {
        //System.out.println(s);
        ts.add(s);
    }
    System.out.println("List of all possible permutations");
    System.out.println(ts);

}

private ArrayList<String> generatePermutations( String[] elements )
{
    ArrayList<String> permutations = new ArrayList<String>();
    if ( elements.length == 2 )
    {

        String x1 = elements[0]  + elements[1]; 
        String x2 = elements[1]  + elements[0];  
        permutations.add(x1);
        permutations.add(x2);

    }
    else {
        for (  int i = 0 ; i < elements.length  ; i++)
        {
            String[] elements2 = new String[elements.length -1];
            int kalo = 0;
            for( int j =0 ; j< elements2.length ; j++ )
            {
                if( i == j)
                {
                    kalo = 1;
                }
                elements2[j] = elements[j+kalo];
            }
            ArrayList<String> k2 = generatePermutations(elements2);
            for( String x : k2 )
            {
                String s = elements[i]+x;
                permutations.add(s);
            }
        }
    }

    return permutations;
    }
}

Answer 7

This code takes String elements, but can me modified to work for integers:

import java.util.*;
/**
 * Write a description of class GeneratePermutations here.
 * 
 * @author Kushtrim 
 * @version 1.01
 */
public class GeneratePermutations

{
    public static void main(String args[])
    {
        GeneratePermutations g = new GeneratePermutations();
        String[] elements = {"a","b","c",};
        ArrayList<String> permutations = g.generatePermutations(elements);

        for ( String s : permutations)
        {
            System.out.println(s);
        }
        //System.out.println(permutations.get(999999));
    }

    private ArrayList<String> generatePermutations( String[] elements )
    {
        ArrayList<String> permutations = new ArrayList<String>();
        if ( elements.length == 2 )
        {

            String x1 = elements[0]  + elements[1]; 
            String x2 = elements[1]  + elements[0];  
            permutations.add(x1);
            permutations.add(x2);

        }
        else {
            for (  int i = 0 ; i < elements.length  ; i++)
            {
                String[] elements2 = new String[elements.length -1];
                int kalo = 0;
                for( int j =0 ; j< elements2.length ; j++ )
                {
                    if( i == j)
                    {
                        kalo = 1;
                    }
                    elements2[j] = elements[j+kalo];
                }
                ArrayList<String> k2 = generatePermutations(elements2);
                for( String x : k2 )
                {
                    String s = elements[i]+x;
                    permutations.add(s);
                }
            }
        }

        return permutations;
    }
}

Answer 8

import java.util.ArrayList;
import java.util.Arrays;

public class Answer {
    static <E> String arrayToString( E[] arr ) {
        final StringBuffer str = new StringBuffer();
        for ( E e : arr )
            str.append( e.toString() );
        return str.toString();
    }

    static <E> ArrayList<E[]> permutations(E[] arr) {
        final ArrayList<E[]> resultList = new ArrayList<E[]>();
        final int l = arr.length;
        if ( l == 0 ) return resultList;
        if ( l == 1 )
        {
            resultList.add( arr );
            return resultList;
        }

        E[] subClone = Arrays.copyOf( arr, l - 1);
        System.arraycopy( arr, 1, subClone, 0, l - 1 );

        for ( int i = 0; i < l; ++i ){
            E e = arr[i];
            if ( i > 0 ) subClone[i-1] = arr[0];
            final ArrayList<E[]> subPermutations = permutations( subClone );
            for ( E[] sc : subPermutations )
            {
                E[] clone = Arrays.copyOf( arr, l );
                clone[0] = e;
                System.arraycopy( sc, 0, clone, 1, l - 1 );
                resultList.add( clone );
            }
            if ( i > 0 ) subClone[i-1] = e;
        }
        return resultList;
    }

    static ArrayList<String> permutations(String arr) {
        final Character[] c = new Character[ arr.length() ];
        for ( int i = 0; i < arr.length(); ++i )
            c[i] = arr.charAt( i );

        final ArrayList<Character[]> perms = permutations(c);
        final ArrayList<String> resultList = new ArrayList<String>( perms.size() );

        for ( Character[] p : perms )
        {
            resultList.add( arrayToString( p ) );
        }
        return resultList;
    }

    public static void main(String[] args) {
        ArrayList<String> str_perms = permutations( "abc" );
        for ( String p : str_perms ) System.out.println( p );

        ArrayList<Integer[]> int_perms = permutations( new Integer[]{ 1, 2, 3, 4 } );
        for ( Integer[] p : int_perms ) System.out.println( arrayToString( p ) );

    }
}

Answer 9

I've written that code some time ago, and edited a bit to match your requests. I hope it works.

static ArrayList<String> permutations(String s) {
    ArrayList<String> ret = new ArrayList<String>();
    permutation(s.toCharArray(), 0, ret);
    return ret;
}

public static void permutation(char[] arr, int pos, ArrayList<String> list){
    if(arr.length - pos == 1)
        list.add(new String(arr));
    else
        for(int i = pos; i < arr.length; i++){
            swap(arr, pos, i);
            permutation(arr, pos+1, list);
            swap(arr, pos, i);
        }
}

public static void swap(char[] arr, int pos1, int pos2){
    char h = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = h;
}

UPDATE
I just tried it on ideone.com. It seems to work. You're welcome. :)

UPDATE 2
It should basically be the same code with arrays of int's:

static ArrayList<int[]> permutations(int[] a) {
    ArrayList<int[]> ret = new ArrayList<int[]>();
    permutation(a, 0, ret);
    return ret;
}

public static void permutation(int[] arr, int pos, ArrayList<int[]> list){
    if(arr.length - pos == 1)
        list.add(arr.clone());
    else
        for(int i = pos; i < arr.length; i++){
            swap(arr, pos, i);
            permutation(arr, pos+1, list);
            swap(arr, pos, i);
        }
}

public static void swap(int[] arr, int pos1, int pos2){
    int h = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = h;
}

UPDATE 3
Works with int's too: http://ideone.com/jLpZow