给定字符的带限制重复排列算法（C++）

Question

给定字符的带限制重复排列算法（C++）

3

我需要制作一个程序来列出所有的排列组合。
有4个字符：
"1",
"2",
"R",
"T"
条件是，"R" 需要在它的前后有 "1"，就像这样： 1-R-1
"T" 的条件是，它的后面必须是 "1" 或 "2"，就像这样： T-1 或 T-2。

长度最多可以达到10

输出应该像这样：

我已经成功解决了排列问题，但是我无法让它们与条件配合使用。

    void displayPermutation(string permutation[], int length){
        int i;
        for (i=0;i<length;i++){
            cout<<permutation[i];
        }
        cout << endl;
    }

    void getPermutations(string operatorBank[], int operatorCount, 
            string permutation[],int permutationLength, int curIndex){
        int i;
        //stop recursion condition
        if(curIndex == permutationLength){
            displayPermutation(permutation,permutationLength);
        }
        else{
            for(i = 0; i < operatorCount; i++){
                permutation[curIndex] = operatorBank[i];
                getPermutations(operatorBank,operatorCount,permutation,
                    permutationLength,curIndex+1);
            }
        }
    }

    int main ()
   {
       int operatorCount = 4;
       int permutationLength = 3;
       string operatorBank[] = {"1","2","R","T"};
       string permutation[] = {"","","",""}; //empty string
       int curIndex = 0;
       getPermutations(operatorBank,operatorCount,permutation,
                                   permutationLength,curIndex);
       return 0;
   }

- user13518046

可能与std::next_permutation有关。 - Jesper Juhl

遗憾的是，next_permutation不能处理重复字符。 - user13518046

1

很遗憾，next_permutation不能处理重复字符。-- 创建一个索引数组，从0到n-1，并对其进行排列。然后这些索引指示要选择哪个字符。 - PaulMcKenzie

@jebotekurac 所以 permutationCount 不仅是要选择的项目数量，还包括字符的潜在“重复计数”？我问这个问题的原因是你说的第一项有效的是 111，即使 1 在 operatorBank 数组中只出现了一次。 - PaulMcKenzie

所以基本上，如果你的字符串长度为4，则会扩展为“111222RRRTTT”，并且你想要选择3个字符，允许重复。是这样吗？如果是这样，那么可以使用STL算法和容器来解决问题。 - PaulMcKenzie

显示剩余2条评论

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Answer 1

你是指像这样的递归吗？

function f(n, str=""){
  if (!n)
    return [str];
    
  let result = [];
  
  if (n >= 3)
    result = result.concat(f(n - 3, str + "1R1"));
    
  if (n >= 2)
    result = result
      .concat(f(n - 2, str + "T1"))
      .concat(f(n - 2, str + "T2"));
    
  return result
    .concat(f(n - 1, str + "1"))
    .concat(f(n - 1, str + "2"));
}

console.log(f(3));

- Cristian Bidea · Answer 2

你把术语搞混了。你说的不是排列[1]，而是组合[2]。

据我所知，你已经有了算法（递归回溯），只是没有检查你的解决方案是否有效，通过过滤解空间来筛选。因此，你正在生成所有解决方案，而不考虑任何约束条件，并在达到permutationLength时打印一个解决方案。在这一步，您还可以通过检查解决方案是否符合条件来检查其是否有效。如果是，则打印它，否则将其丢弃。

这个策略是：

查找R并检查permutation[idx-1]是否为1，permutation[idx+1]是否为1
查找T并检查permutation[idx+1]是否为1或2。

只有满足这些条件才会打印解决方案！

...
if(curIndex == permutationLength){
    if (solutionValid()) {
          displayPermutation(permutation,permutationLength);
    }
}
...