Вопрос по java, arrays, recursion, permutation – Перестановка массива с повторением в Java

9

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

Это домашнее задание, в котором у вас есть набор символов [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
Это просто означает, что после того, как персонаж используется, его можно использовать снова. Таким образом, число возможных выходов составляет 3 ^ 3, а не 3 !. user1788424
Что значит "с повторением значит здесь? seh

Ваш Ответ

4   ответа
1

(основная идея - количество перестановок строки длины '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);="" }="" <="" code=""></s.length;i++)></string></string></string>

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

<code>[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);
            }
        }
</code>
7

Если я правильно понимаю, вам дают набор символовc и желаемой длины.n

Технически, естьнет такой вещи как перестановка с повторением. Я предполагаю, что вы хотите, чтобы все строки длиныn с письмами от.c

Вы можете сделать это следующим образом:

to generate all strings of length N with letters from C
 -generate all strings of length N with letters from C
     that start with the empty string.

to generate all strings of length N with letters from C
   that start with a string S
 -if the length of S is N
  -print S
 -else for each c in C
  -generate all strings of length N with letters from C that start with S+c

В коде:

printAll(char[] c, int n, String start){
  if(start.length >= n){
    System.out.println(start)
  }else{
    for(char x in c){ // not a valid syntax in Java
      printAll(c, n, start+x);
    }
  }
}
Вы, сэр, не просто джентльмен и ученый. Вы принц, джентльмен и ученый. Некоторые другие люди онлайн предложили нечто подобное, за исключением использования массива, а не строки. Однако ваше объяснение было намного понятнее. user1788424
@JanDvorak Я знаю, что это старая проблема, но у меня была похожая проблема, которую я пытался решить, и я изменил ее, и она полностью сработала.Не понимаю, как работает ваш последний вызов printAll (c, n, start + x). Я распечатал это, и начало идет так для первых нескольких звонков (a, aa, aaa, aab, aac, ab, aba). Я нене понимаю, почему это не такт в конечном итоге (ABC, ABCABC, ABCABCABC). Я надеялся, что ты сможешь это объяснить. Я пытался отследить это, и я понимаю, что каждый раз, когда print all вызывает себя внутри цикла, он вызывает себя n раз. В любом случае, если бы вы могли, я хотел бы получить больше объяснений. MichelleJS
Большое спасибо. Я нарисовал все это на листе бумаги, чтобы понять. Теперь я должен сделать то же самое и без повторения. Я'Я не уверен, как изменить этот код, чтобы сделать это, но это было очень хорошее начало. MichelleJS
@MichelleJS один вариант будет удалитьx из списка кандидатов (если ваш язык достаточно хорош, то простоprintAll(c-x, n, start+x)). Другой будет проверить, еслиx уже естьstart перед повторением. Первый вариант может работать лучше, но второй вариант может быть проще реализовать в Java. John Dvorak
3

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
1

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

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

Если я правильно понимаю проблему, указывается требуемая длина перестановки John Dvorak

Похожие вопросы