在C ++中具有输出限制的排列

Question

我正在尝试对8个字符进行排列，但是我只对最多包含3个相同字符的输出感兴趣。因此，任何包含超过3个字符的字符的输出都应被跳过。字符集：a，b，c，d，e，f，g，G例：对输出不感兴趣，例如aaaaaaab，aabcdeaa，acdGGGGg，GGGGbbbb ...对输出感兴趣例如abcdefgG，aaabcdef，abacadGf ...

我试图编写一个代码，在其中我计算每个字符出现的每个周期数，如果出现三个以上相同字符，则跳至下一个循环。这是我的代码无法解决的问题。该程序仅执行以字符'a'开头的排列，并在aaabgGGG处停止，我无法管理它继续执行以b，c，d，e等开头的迭代。我想在周期中实现过滤，以避免发生不必要的周期=>尽可能快地进行处理。在#####行之间注释“ >> 3次出现过滤器”代码时，所有排列均得到正确处理。我的代码：

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

我的代码逻辑中的主要错误在哪里？

Answer 1

解决问题的方法非常简单。

您要做的是获取您的字符集：a，b，c，d，e，f，g，G

并构造一个“假”序列，每个字符一式三份。

std::vector<char> perm{'a', 'a', 'a', 'b', 'b', 'b', ...};

这里的主要见解是，您可以像往常一样使用std::next_permutation计算排列。您只需要从该排列中获取前8个元素，即可获得所需的结果。

[[编辑：显然会有重复项，如果不希望有这些重复项，可以使用Bloom筛选器将它们删除-在恒定的时间和内存中进行。]