создание различных различных перестановок фиксированной длины (L)

Я пишу программу для создания различных перестановок массива с фиксированной длиной 3. Основная проблема, с которой я сталкиваюсь, заключается в том, что она всегда генерирует повторяющиеся перестановки. Как я могу это исправить, не используя набор Java‹>.

public class generatingCombination {

    public static void main(String[] args) {
        String s="ABCDEF";
            printArray(s,0,new char[3], new boolean[s.length()]);

    }

    static void printArray(String s,int x,char []arr, boolean [] used){
        if(x==3){
            System.out.println(Arrays.toString(arr));
            return;
        }
        else
        {
            for( int i=0;i<s.length();i++){
                if(used[i]) continue;

                arr[x]=s.charAt(i);
                used[i]=true;
                printArray(s, x+1, arr,used);
                used[i]=false;
                printArray(s, x+1, arr,used);

            }
        }

    }
}

java algorithm
person dead programmer    schedule 07.08.2016    source источник
comment
Вы получаете дубликаты, потому что дважды выполняете рекурсивный вызов. Зачем ты это делаешь? В чем смысл массива used, если вы вызываете себя без установки значения (второй рекурсивный вызов)?   -  person Andreas    schedule 07.08.2016
comment
@YS. - Приведите пример ожидаемого результата.   -  person Matan Lachmish    schedule 07.08.2016
comment
Второй вызов printArray просто распечатает то же самое, что и первый.   -  person tim4242    schedule 07.08.2016
comment
Есть несколько действительно хороших нерекурсивных алгоритмов перестановки, которые естественным образом и легко избегают создания дубликатов. Возможно, вы захотите изучить алгоритм C++ std::next_permutation.   -  person templatetypedef    schedule 07.08.2016

Ответы (1)


arrow_upward
0
arrow_downward

Если вас интересуют только перестановки длины 3, то почему бы просто не:

public static void main(String[] args) {
    String s = "ABCDEF";
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < s.length(); j++) {
            if (j == i) {
                continue;
            }
            for (int k = 0; k < s.length(); k++) {
                if (k == i || k == j) {
                    continue;
                }
                System.out.println(Arrays.toString(new char[] { s.charAt(i), s.charAt(j), s.charAt(k)}));
            }
        }
    }
}
person korolar    schedule 07.08.2016