Java 中数组的重复排列

Question

这个网站上有一些类似的问题，对我有些帮助，但是我还是无法解决这个问题，所以希望这不是重复的。

这是一个作业任务，你需要一个字符集数组 [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搜索结果，但我为自己无法解决这个看起来相当简单的问题感到懊恼。

- user1788424

---

这里的“with repetition”是什么意思？ - seh

这只是意味着一旦使用了一个字符，它可以再次使用。因此可能的输出数量为3^3，而不是3！。 - user1788424

Answer 1

如果我理解正确，您将得到一组字符c和所需的长度n。

从技术上讲，不存在带重复的排列。我假设您想要由c中的字母组成的所有长度为n的字符串。

您可以按照以下方式操作：

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);
    }
  }
}

- John Dvorak

---

先生，您不仅是一位绅士和学者，更是一位王子、绅士和学者。其他一些网友建议使用数组而非字符串，但是您的解释更加清晰易懂。 - user1788424

@JanDvorak 我知道这是旧的问题，但我有一个类似的问题要解决，我修改了这个代码，它完全起作用了。然而，我不明白你的最后一次调用printAll(c,n,start+x)是如何工作的。我打印出来，start在前几次调用时变成了这样(a, aa, aaa, aab, aac, ab, aba)。我真的不明白为什么它最终不会变成(abc, abcabc, abcabcabc)。我希望你能解释一下。我一直在尝试追踪它，我理解每次print all在循环内部调用自己时，它会再次调用n次。无论如何，如果您可以的话，我想要更多的解释。 - MichelleJS

@MichelleJS 为什么会是 abcabcabc？你是在 start 中添加一个字符，然后回溯并在同一位置添加另一个不同的字符。在第一次调用 (start == "") 中：start.length == 0，所以它进入了 else 分支。C 的第一个字符是 a，所以在第一次迭代中 x == 'a'。"" + 'a' == "a"，因此第一个递归调用是 printAll("abc", 3, "a")。如果你在循环内部执行 printAll(c, n, start+c)，那么你描述的行为就会发生 - 在这种情况下，x 最终将无法使用。 - John Dvorak

非常感谢。我在一张纸上把所有东西都画出来以便理解。现在，我需要做另一件事情，但不能重复。我不确定如何修改这段代码才能实现，但这已经是一个很好的开始了。 - MichelleJS

@MichelleJS 一个选项是从候选列表中删除 x（如果您的语言足够好，那么只需 printAll(c-x, n, start+x)）。另一个选项是在递归之前检查 x 是否已经是 start。第一个选项可能执行得更好，但第二个选项在Java中实现可能更容易。 - John Dvorak

Answer 2

我使用这个Java实现的重复排列。A~(n,m): n = 数组长度，m = k。m可以大于或小于n。

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

- Ilya

Answer 3

以下是生成带重复字符的字符串排列的C#版本：

（基本思路是 - 长度为“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);
            }
        }

- Dreamer

Answer 4

我有一个想法。如果你添加了一个隐藏字符（H代表隐藏）[A，B，C，H]，然后对其进行所有固定长度的排列（你说你知道如何做到这一点）。然后在读取时，在隐藏字符处停止，例如[B，A，H，C]将变为（B，A）。

嗯，缺点是你必须跟踪你创建的哪些排列，尽管[B，H，A，C]与[B，H，C，A]相同。

- Darren

---

如果我正确理解了这个问题，置换所需的长度已给定。 - John Dvorak