java - 如何修改我的代码以删除(不生成)重复的排列

Question

我不知道如何识别我在递归调用中生成重复排列。假设我们在长度为 n 的字符串中重复了 2 个字母。然后我需要创建 n!/2!序列，而不是 n!序列。

如何修改我的代码以实现此目的？

public class GeneralPermutationGenerator{

    public static void main(String[] args) {

        String s = "AABC";
        perm(s);
    }

    public static void perm(String s){
        char cs[] = s.toCharArray();
        char result[] = new char[cs.length];
        rperm(cs, result, 0);
    }

    static int j = 1;
    private static void rperm(char[] cs, char[] result, int level){
        if(level == result.length){
            System.out.println(j++ + " " + new String(result));
            return;
        }

        for(int i = 0; i < cs.length; i++){
            if(cs[i] != 0){
                result[level] = cs[i];
                char temp = cs[i];
                cs[i] = 0;
                rperm(cs, result, ++level);
                cs[i] = temp;
                level--;
            }
        }
    }

}

Answer 1

可以通过始终从可用的第一个位置取一个出现多次的字母来强制执行唯一性。

也就是在每一层，选择一个字母的时候，可以回头看看它是否已经出现在cs数组中。如果之前确实出现过(也就是说还没有被选中，因为cs中的那个位置不为零)，那么应该不允许从这个位置开始选中它。

---

实现

一种可能的实现方式包括如下更改 rperm 代码(循环遍历前面的字符，查看是否已经遇到当前字符):

private static void rperm(char[] cs, char[] result, int level) {
    if (level == result.length) {
        System.out.println(j++ + " " + new String(result));
        return;
    }

    for (int i = 0; i < cs.length; i++) {
        if (cs[i] != 0) {
            // first, determine if the current char was already 
            // encountered among the available options
            boolean encountered = false;
            for (int j = 0; j < i; j++) {
                if (cs[j] == cs[i]) {
                    encountered = true;
                    break;
                }
            }

            if (!encountered) {
                result[level] = cs[i];
                char temp = cs[i];
                cs[i] = 0;
                rperm(cs, result, ++level);
                cs[i] = temp;
                level--;
            }
        }
    }
}

---

解释

要了解这是如何工作的，请再次考虑示例 AABC。

为了区分本次讨论中的两个 A，我们将它们表示为 A1 和 A2。

对于level = 0，我们应该选择一个字符放入result[0]:

• 我们可以选择A1;
• 我们不能选择A2，因为在这个级别的可用字符列表中已经遇到了一个A；
• 我们可以选择B;
• 我们可以选择C。

首先，算法会选择A1，然后进行下一级递归。

在level = 1。

现在，与A1 关联的位置已在ch 数组中标记为0。因此，对于要放入 result[1] 中的字符，我们有以下备选方案:

• 选择A2(因为现在没有可用的A，因为第一个已经在之前的递归级别被采用，并标记为0 )
• 选择B；
• 选择C。

它将首先选择 A2，到目前为止的部分排列将为 A1 A2，递归中还有两个层次。然而，没有重复的关键是对于同一个字符，它的索引总是以递增的顺序排列。该算法也无法生成以 A2 A1 开头的排列，原因很简单，因为如果 A1 仍然是，则不允许选择 A2可用的。