如何修改我的代码以删除（不生成）重复的排列

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。

对于级别= 0，应该选择一个字符被放入结果[0]：

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

首先，该算法将选择A1，并继续在下一级递归。

在level = 1。

现在，与A1关联的位置已在ch阵列中标记为0。 因此，我们已为字符以下的替代品放在结果[1]：

• 选择A2（因为现在没有以前可用的A，作为第一个在前面的递归级别已经采取，并标记为0）
• 选择B;
• 选择C。

它会首先选择A2，以及部分置换迄今将A1 A2，有两个层面的递归去。然而，没有重复的关键在于，对于同一个字符，其索引将始终处于升序。该算法将不能生成从A2 A1开始的排列，仅仅是因为如果A1仍然可用，则不允许选择A2。

Answer 2

有查找序列的字典序下一置换一个简单的非递归算法：从序列结束

1. 扫描向后直到找到小于以下的元素是（严格）一。如果没有一个，那么这个序列是字典上最大可能的排列。
2. 颠倒你找到的元素后面的元素子序列。
3. 将您在步骤1中找到的元素与第一个以下元素（严格来说）大于它相交换。

我不是一个真正的Java程序员，所以这里的简化C++，实现用较少的标准库函数比我想象中的希望通常用它更易于理解：

template<typename V> 
bool nextPerm(V& v) { 
    for (auto i = v.size(); i > 1; --i) 
    if (v[i-2] < v[i-1]) { 
     std::reverse(v.begin() + i - 1, v.end()); 
     for (auto j = i - 1; j < v.size(); ++j) 
     if (v[i-2] < v[j]) { std::swap(v[i-2], v[j]); break; } 
     return true; 
    } 
    return false; 
}