Algorithm for permutations of given characters with repetition with conditions C++

user_13518046 0
Viewed 102

So I need to make a program that lists all permutations.
There are 4 characters:
"1",
"2",
"R",
"T"
The conditions is that the "R" needs to have "1" before and after him so it sits like this 1-R-1
The "T" condition is that either "1" or "2" are after him so it sits like this T-1 or T-2

The max length should be 10

The output should be like this:

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

I have managed to figure out the permutations part but I just cannot make them work with the conditions

    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;
   }
permutation algorithm c++
2 Answers

You got your terms a little mixed up. You're not talking about permutations[1] but about combinations[2].

As far as I can tell you already have the algorithm (recursive backtracking) you're just not checking if your solution is valid, by filtering the solution space. So you're generating all solutions without taking into account any constraint and you print a solution when you reached the permutationLength. At this step you can also check if the solution is valid by checking if it abides by the conditions. If it is you print it, if not you discard it.

Strategy for this would be:

  1. Look for R and check if permutation[idx-1] is 1 and permutation[idx+1] is 1
  2. Look for T and check if permutation[idx+1] is either 1 or 2.

You only print the solution if these conditions are met!

...
if(curIndex == permutationLength){
    if (solutionValid()) {
          displayPermutation(permutation,permutationLength);
    }
}
...
  1. https://mathworld.wolfram.com/Permutation.html
  2. https://mathworld.wolfram.com/Combination.html
user_11927000

Do you mean a recursion like this?

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

user_20347870
Related