10

网站上有一些类似的问题有所帮助，但我不能完全确定这个问题，所以我希望这不是重复的。

这是一个家庭作业，您有一组字符 [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 的排列。我已经尝试了所有我能想到的，并仔细研究了谷歌搜索结果，我对自己无法解决看似相当简单的问题感到恼火。

4

4 回答 4

9

如果我理解正确，您将获得一组字符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);
    }
  }
}
于 2012-10-31T12:42:13.843 回答
3

我使用这种带有重复排列的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
于 2016-10-18T06:49:35.407 回答
1

我只是有个主意。如果您添加一个隐藏字符（H 表示隐藏）[A, B, C, H]，然后对其进行所有固定长度排列（您说您知道如何做到这一点）会怎样。然后当你读完它时，你会在隐藏字符处停下来，例如 [B,A,H,C] 会变成 (B,A)。

嗯，缺点是您必须跟踪您创建的那些，尽管 [B,H,A,C] 与 [B,H,C,A] 相同

于 2012-10-31T12:17:20.803 回答
1

这是用于生成具有重复的给定字符串的排列的 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);
            }
        }
于 2014-08-08T11:42:53.477 回答