c++ - 用条件 C++ 重复给定字符排列的算法

Question

所以我需要制作一个列出所有排列的程序。
有4个字符:
"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

您的条款有点困惑。您不是在谈论排列[1]，而是在谈论组合[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.com/Permutation.html
2. https://mathworld.wolfram.com/Combination.html