Перебора всех перестановок каждого подмножества


У меня эта ведьма кода, который я использую для перебора всех перестановок каждого подмножества в массив ведьма держит целых чисел.

Одна большая проблема-это эффективность, конечно, еще одна проблема заключается в том, что если у меня есть некоторые сходные значения он имеет только один из них (Исх. [100,5,3,5] проводится [100,5,3]).

Любая помощь в улучшении это признательны :D

public int findSolution(){

    for(int i = 1; i <= values.length; i++){
        orders.add(values[i-1]);
    }
    for(int i = 1; i <= values.length; i++){
        List<Set<Integer>> listSet = getSubsets(orders, i);
        for(Set<Integer> set : listSet){
            int[] currSetAsArray = new int[i];
            int index = 0;
            for(Integer x : set){
                currSetAsArray[index++] = x;
            }
            System.out.println("Current Set: ");
            System.out.println(set);
            System.out.println("All Permutations: ");
            permute(currSetAsArray, 0);
        }
        System.out.println(i);
        //System.out.println(listSet.get(0));
    }

    System.out.println("Total permutations: " + permutations);
    return 0;
}

//Function that finds every subset
private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
    //successful stop clause
    if (current.size() == k) {
        solution.add(new HashSet<>(current));
        return;
    }
    //unseccessful stop clause
    if (idx == superSet.size()) return;
    Integer x = superSet.get(idx);
    current.add(x);
    //"guess" x is in the subset
    getSubsets(superSet, k, idx+1, current, solution);
    current.remove(x);
    //"guess" x is not in the subset
    getSubsets(superSet, k, idx+1, current, solution);
}

public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
    List<Set<Integer>> res = new ArrayList<>();
    getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
    return res;
}

//Function that finds every permutation
private void permute(int[] a, int k)
{
    if (k == a.length)
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.print(" [" + a[i] + "] ");
        }
        System.out.println();
        permutations++;
    }
    else
    {
        for (int i = k; i < a.length; i++)
        {
            int temp = a[k];
            a[k] = a[i];
            a[i] = temp;

            permute(a, k + 1);

            temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }
}


114
2
задан 23 февраля 2018 в 08:02 Источник Поделиться
Комментарии