Генерация комбинации символов в строке не работает полностью, почему?

Question

Я пытаюсь сгенерировать все комбинации символов в строке. Таким образом, первый параметр - это заданная строка, а второй параметр - количество букв. Так что combinations("ab",2) должно дать мне aa, ab, ba, bb, а combinations("abc",2) должно дать мне aa, ab, ac, ba, bb, bc, ca, cb, cc и т. Д.

В первом случае мой текущий код дает мне aa, ab, bb (поэтому он пропускает ba). Это мой код:

        public static void combinations(String s, int n)
        {
            combinations(s,"",n);
        }


        public static void combinations(String s, String prfx, int n)
        {
            if(n == 0)
            {
                System.out.println(prfx);
            }

            else
            {
                for(int i = 0; i < s.length(); i++)
                {
                    combinations(s.substring(i), prfx + s.charAt(i), n-1);

                }
            }
        }

Что я делаю не так? Я был бы признателен, если бы вы не просто дали мне правильный ответ, но и дали мне некоторое объяснение, чтобы я мог извлечь из этого урок, потому что я не так хорош в рекурсии. Спасибо.

Answer 1

Это работает:

public static void combinations(String s, int n) {
    combinations(s, "", n);
}

public static void combinations(String s, String prfx, int n) {
    if (n == 0) {
        System.out.println(prfx);
    }

    else {
        for (int i = 0; i < s.length(); i++) {
            combinations(s, prfx + s.charAt(i), n - 1);
        }
    }
}

Answer 2

Корень вашей проблемы здесь:

  combinations(s.substring(i), prfx + s.charAt(i), n-1);
               ^^^^^^^^^^^^^^

Вы хотите перебрать символы в строке и использовать каждый символ по очереди в качестве префикса, а затем сделать рекурсивный вызов для создания комбинаций дляостальная часть строки.Однако, если вы передадите только подстроку исходной строки в рекурсивный вызов, она не сгенерирует все возможные перестановки.В вышеприведенном случае, как вы заметили, он пропускает «ba», потому что когда цикл достигает 2-го символа строки «ab» (когда счетчик цикла i равен 1), выполняется этот рекурсивный вызов: combinations("b", "" + "b", 1),Который может генерировать только "bb", а не "ba".Если бы вместо этого было combinations("ab", "" + "b", 1), вы бы получили обе ожидаемые комбинации "ba" и "bb".

Так что вам нужно передать всю строку в каждый рекурсивный вызов:

  combinations(s, prfx + s.charAt(i), n-1);