Перестановка массива с повторением в Java

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

Это домашнее задание, в котором у вас есть набор символов [A, B, C], и вы должны использовать рекурсию для получения всех перестановок (с повторением). Код, который у меня есть, делает это:

char[] c = {'A', 'B' , 'C'};

public void printAll(char[] c, int n, int k) {
    if (k == n) {
      System.out.print(c);
      return;
    }
    else {   
      for (int j = 0; j<n; j++) {
        for (int m = 0; m<n; m++) {
           System.out.print(c[k]); 
           System.out.print(c[j]); 
           System.out.print(c[m] + "\r\n");
        }
      }
    }        
    printAll(c, n, k+1);    
}

Однако параметр n должен определять длину вывода, поэтому, хотя эта функция печатает все перестановки длины 3, она не может делать их длины 2. Я перепробовал все, что мог придумать, и изучил результаты поиска Google, и я раздражен тем, что не смог решить то, что кажется довольно простой проблемой.

 seh31 окт. 2012 г., 15:14
Что значит «с повторением» здесь?
 user178842431 окт. 2012 г., 22:40
Это просто означает, что после того, как персонаж используется, его можно использовать снова. Таким образом, число возможных выходов составляет 3 ^ 3, а не 3 !.

Ответы на вопрос(3)

(Основная идея такова - количество перестановок строки длины 'n' с повторениями равно n ^ n).

string[] GetPermutationsWithRepetition(string s)
        {
            s.ThrowIfNullOrWhiteSpace("s");
            List<string> permutations = new List<string>();
            this.GetPermutationsWithRepetitionRecursive(s, "",
                permutations);
            return permutations.ToArray();
        }
        void GetPermutationsWithRepetitionRecursive(string s, string permutation, List<string> permutations)
        {
            if(permutation.Length == s.Length)
            {
                permutations.Add(permutation);
                return;
            }
            for(int i =0;i<s.Length;i++)
            {
                this.GetPermutationsWithRepetitionRecursive(s, permutation + s[i], permutations);
            }
        }

Ниже приведены соответствующие юнит-тесты:

[TestMethod]
        public void PermutationsWithRepetitionTests()
        {
            string s = "";
            int[] output = { 1, 4, 27, 256, 3125 };
            for(int i = 1; i<=5;i++)
            {
                s += i;
                var p = this.GetPermutationsWithRepetition(s);
                Assert.AreEqual(output[i - 1], p.Length);
            }
        }

я скрытого) [A, B, C, H], а затем сделали все перестановки фиксированной длины (вы сказали, что знаете, как это сделать). Затем, когда вы читаете его, вы останавливаетесь на скрытом персонаже, например [B, A, H, C] станет (B, A).

Хм, недостатком является то, что вам придется отслеживать, какие из них вы создали, хотя [B, H, A, C] совпадает с [B, H, C, A]

 John Dvorak31 окт. 2012 г., 13:20
Если я правильно понимаю проблему, указывается требуемая длина перестановки

n, m): n = длина массива, m = k. м может быть больше или меньше, чем п.

public class Permutations {


    static void permute(Object[] a, int k, PermuteCallback callback) {
        int n = a.length;

        int[] indexes = new int[k];
        int total = (int) Math.pow(n, k);

        Object[] snapshot = new Object[k];
        while (total-- > 0) {
            for (int i = 0; i < k; i++){
                snapshot[i] = a[indexes[i]];
            }
            callback.handle(snapshot);

            for (int i = 0; i < k; i++) {
                if (indexes[i] >= n - 1) {
                    indexes[i] = 0;
                } else {
                    indexes[i]++;
                    break;
                }
            }
        }
    }

    public static interface PermuteCallback{
        public void handle(Object[] snapshot);
    };

    public static void main(String[] args) {
        Object[] chars = { 'a', 'b', 'c', 'd' };
        PermuteCallback callback = new PermuteCallback() {

            @Override
            public void handle(Object[] snapshot) {
                for(int i = 0; i < snapshot.length; i ++){
                    System.out.print(snapshot[i]);
                }
                System.out.println();
            }
        };
        permute(chars, 8, callback);
    }

}

Пример вывода

aaaaaaaa
baaaaaaa
caaaaaaa
daaaaaaa
abaaaaaa
bbaaaaaa
...
bcdddddd
ccdddddd
dcdddddd
addddddd
bddddddd
cddddddd
dddddddd

Ваш ответ на вопрос