Permutation Algorithmus für Integer-array in Java

//Hier eine rekursive version, die war nicht schwer zu Begehen, um das menschliche Gedächtnis ! O(n!) Permutationen.

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

InformationsquelleAutor Bob Sheehan

Dieser code wird auf String-Elemente, aber kann mir modifiziert, um die Arbeit für ganze zahlen:

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

InformationsquelleAutor Kushtrim

/**
 * 
 * @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;
    }
}

InformationsquelleAutor YashM

Durch hinzufügen eines TreeSet entfernt Duplikate und sortiert die Permutationen.

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

InformationsquelleAutor 9 Digit Dev

Hier ist meine Lösung (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;
        }
    }
}

InformationsquelleAutor Karol Król