0

我想一次生成一组 n 件事情的所有可能团队，例如 "abcd" = ab,ac,ad... 没有重复。我已经写了这个，但它会生成一个字符串的所有排列。我写了一个方法来检查两个字符串是否有相同的字符，但我不知道这是否是正确的方法。

package recursion;

import java.util.Arrays;

public class Permutations2 {

    public static void main(String[] args) {
        perm1("", "abcd");
        System.out.println(sameChars("kostas","kstosa"));
    }


    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0){
            System.out.println(prefix);
        }
        else {
            for (int i = 0; i < N; i++) {
                perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
            }
        }
    }

    private static boolean sameChars(String firstStr, String secondStr) {
        char[] first = firstStr.toCharArray();
        char[] second = secondStr.toCharArray();
        Arrays.sort(first);
        Arrays.sort(second);
        return Arrays.equals(first, second);
    }
}
4

3 回答 3

3

您正在描述一个电源组。

Guava 有一个实现。

于 2013-06-04T21:24:25.557 回答
0

这应该在没有递归的情况下工作：

private static void perm(String s) {
   char[] arr = s.toCharArray();     
   for (int i = 0; i < s.length() - 1; i++) {
      for(int j = i + 1; j < s.length(); j++) {
         System.out.println(String.valueOf(arr[i]) + String.valueOf(arr[j]));
      }
   }
}

它是 O(n**2)。

于 2013-06-04T21:59:31.290 回答
0

愿你想要枚举 k-combinations。

private static void combinate(String s, String prefix, int k) {
    if (s.length() < k) {
        return;
    } else if (k == 0) {
        System.out.println(prefix);
    } else {
        combinate(s.substring(1), prefix + s.charAt(0), k - 1);
        combinate(s.substring(1), prefix, k);
    }
}

public static void main(String[] args) {
    combinate("abcd", "", 2);
}

输出：

ab
ac
ad
bc
bd
cd

请参阅Java 编程简介 - 递归 - Robert Sedgewick 和 Kevin Wayne

于 2013-06-04T21:41:54.710 回答