给定字符与条件重复的组合算法 C++

Question

所以我需要做一个程序，列出所有的排列组合。有4个字符："1"，"2"，"R"，"T"。"1"、"2"、"R"、"T" 条件是 "R "前后都要有 "1"，所以是这样的 1 -R -1 "T "的条件是 "1 "或 "2 "在他后面，所以是这样的 T -1或T -2。

最大长度应为10

输出应该是这样的。

111
112
121
122
1R1
1T1
1T2
211
212
221
222
2T1
2T2
T11
T12
T21
T22

我已经搞清楚了排列组合的部分，但我不能让它们在条件下工作。

    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;
   }

Answer 1

你把你的术语搞混了。你说的不是permutations[1]而是combinations[2]。

据我所知，你已经有了算法（递归回溯），只是没有通过过滤解空间来检查你的解是否有效。所以你在不考虑任何约束条件的情况下生成了所有的解，当你到了 permutationLength. 在这一步，你还可以检查解决方案是否有效，检查它是否符合条件。如果是，就打印出来，如果不是，就丢弃它。

这方面的策略是

1. 寻找 R 并检查是否 permutation[idx-1] 是 1 和 permutation[idx+1] 是 1
2. 寻找 T 并检查是否 permutation[idx+1] 要么是 1 或 2.

只有在满足这些条件的情况下，你才能打印出解决方案!

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

1. https:/mathworld.wolfram.comPermutation.html。
2. https:/mathworld.wolfram.comCombination.html。

Answer 2

你是说这样的递归吗？

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));