Permutations with output limitation in C++

Question

I am trying to do the permutations of 8 characters, but I am only interested in output which contains maximum of 3 same characters. So any output which contains any character in more than 3 occurrences should be skipped.
Character set: a, b, c, d, e, f, g, G
Example:
Not interested in output e.g. aaaaaaab , aabcdeaa, acdGGGGg, GGGGbbbb ...
Interested in output e.g. abcdefgG, aaabcdef, abacadGf ...

I tried to write a code where I evaluate in each cycle number of occurrence of each character and skip (break/continue) to next loop if more than 3 same character occurrences are present.
Here is problem with my code which I can't solve. The program do only permutations starting with character 'a' and stops at aaabgGGG and I can't manage it to continue with iterations starting with b, c, d, e etc...
I want to achieve filtering during cycle to avoid unneeded cycles to occur => achieve as fast processing as possible.
When commenting the the ">3 occurrences filter" code between ##### lines, all permutations are processed correctly. My code:

#include <iostream>

// C++ program to print all  possible strings of length k 
using namespace std;

int procbreak = 0;

// The main recursive method to print all possible  strings of length k 
void printAllKLengthRec(char set[], int setn[], string prefix, int n, int k)
{
    // Base case: k is 0, print prefix 
    //cout << "03. In printAllKLengthRec function" << endl;
    if (k == 0)
    {
        //print table with characters and their count
        cout << (prefix) << endl;
        cout << " | ";
        for (size_t b = 0; b < 8; b++)
        {
            cout << set[b] << " | ";
        }
        cout << endl;
        cout << " | ";
        for (size_t c = 0; c < 8; c++)
        {
            cout << setn[c] << " | ";
        }
        cout << endl;

        return;
    }

    // One by one add all characters from set and recursively call for k equals to k-1 
    for (int i = 0; i < n; i++)
    {
        cout << "04. In for loop where one by one all chars are added. K = " << k << "; I = " << i << "; N = " << n << endl;

        string newPrefix;

        //update characters count table
        setn[i] += 1;
        if (i > 0)
        {
            setn[i - 1] -= 1;
        }
        else
        {
            if (setn[7] > 0)
            {
                setn[7] -= 1;
            }
        }

        //#############################################################################################
        //check if there is any character in a table with count more than 3, then break current cycle
        for (size_t d = 0; d < 8; d++)
        {
            if (setn[d] > 3)
            {
                procbreak = 1;
                break;          // enough to find one char with >3, then we don't need to continue and break operation
            }
        }

        if (procbreak == 1)
        {
            procbreak = 0;      // reset procbreak
            continue;           // skip to next cycle
        }
        //#############################################################################################

        // Next character of input added 
        newPrefix = prefix + set[i];

        // k is decreased, because  we have added a new character 
        printAllKLengthRec(set, setn, newPrefix, n, k - 1);
    }
}

void printAllKLength(char set[],int setn[], int k, int n)
{
    cout << "02. In printAllKLength function" << endl;
    printAllKLengthRec(set, setn, "", n, k);
}

// Main code 
int main()
{
    cout << "Start" << endl;
    char set1[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'G' };
    int setn[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    int k = 8;                                                  // string length
    printAllKLength(set1, setn, k, 8);                          // 8 = n => number of characters in the set1
}

Where is main mistake in my code logic?

Answer 1

The solution to your problem is pretty simple.

What you want to do is to take your character set: a, b, c, d, e, f, g, G

and construct a "fake" sequence with each character triplicated.

std::string perm{"GGGaaabbbcccdddeeefffggg"};

The key insight here is that you can compute your permutations as usual, e.g., using std::next_permutation. You just need to take the first 8 elements from that permutation to have the result that you need.

[Edit: In order to avoid computing permutations for the rightmost 16 values, since these will always yield duplicates for the leftmost 8 values, after each step set the rightmost 16 values to the last permutation. The next call to std::next_permutation will permute the first 8 values.]

[Edit2: Working example

#include <algorithm>
#include <chrono>
#include <iostream>

int main()
{
  // Initial state
  std::string perm{"GGGaaabbbcccdddeeefffggg"};

  using clock = std::chrono::steady_clock;
  auto start = clock::now();
  do
  {
    // Output permutation
    std::cout << perm.substr(0, 8) << "\n";

    // Now reverse the last 16 values, so that the call to the next_permutation would change the top 8
    std::reverse(std::next(perm.begin(), 8), perm.end());

  } while (std::next_permutation(perm.begin(), perm.end()));

  std::clog << "Elapsed: " << std::chrono::duration_cast<std::chrono::milliseconds>(clock::now() - start).count() << "ms\n";
  return 0;
}

]

Answer 2

I have found where the problem with filtering was...
The whole permutation is done by running cycles within cycles, in other words the function is calling itself.

When passing from right hand character (right most) to the left hand character (one step to the left), function is doing empty 'k' cycles (1 empty 'k' cycle when going from position 8 to 7 .... up to 7 empty 'k' cycles when going from position 2 to 1).

<-----------|
12345678

My initial code was evaluating the count of each character during each of these empty 'k' cycles.
And that was the issue.

During the empty 'k' cycles, the count of each character is changing and when the empty cycle finishes, the count of the character is real and exactly as it should be.

So the solution is, to do the evaluation of count of each character and if any of the chars is in count >3, break only the last cycle when k = 1. I was breaking the loop in very first empty cycle, where the count of the characters in string were incorrect.

01. In for loop where one by one all chars are added. K = 1; I = 7; N = 8   <--- OK, loop when the last G was added to form string aaaaabGG
table in for loop
 | a | b | c | d | e | f | g | G |
 | 5 | 1 | 0 | 0 | 0 | 0 | 0 | 2 |
aaaaabGG                                    <--- aaaaabGG was formed
table in base                                   <--- aaaaabGG shown in the final output
 | a | b | c | d | e | f | g | G |
 | 5 | 1 | 0 | 0 | 0 | 0 | 0 | 2 |
02. In for loop where one by one all chars are added. K = 3; I = 2; N = 8   <--- going one character UP, next string after aaaaabGG should be aaaaacaa  
table in for loop
 | a | b | c | d | e | f | g | G |
 | 5 | 0 | 1 | 0 | 0 | 0 | 0 | 2 |                      <--- but as we can see, during the K = 3 empty loop, the string is aaaaacGG (updates only 3rd char from left)                       
03. In for loop where one by one all chars are added. K = 2; I = 0; N = 8   <--- second empty loop K = 2
table in for loop
 | a | b | c | d | e | f | g | G |
 | 6 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |                      <--- as we can see, during the K = 2 empty loop, the string is updating and is now aaaaacaG (now updates only 2nd char from left, 3rd is OK from previous empty loop)
04. In for loop where one by one all chars are added. K = 1; I = 0; N = 8   <--- Last loop K = 1 (string is updated 1st character in the left only, 2nd and 3rd were updated in previous empty loops respectively)
table in for loop
 | a | b | c | d | e | f | g | G |
 | 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
aaaaacaa                                    <--- we can see that now the string is as it should be aaaaacaa
table in base                                   <--- aaaaacaa shown in the final output
 | a | b | c | d | e | f | g | G |
 | 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |