CPP中有重复的n个字符的长度为k的所有置换

Question

我想知道在CPP中是否已经有一个实现，可以找到长度为k（1，2，3，4等）的n个字符的所有重复排列。我希望有，但我找不到。

例如，如果string=（A， B， C， D）并且我想找到string的所有排列，重复长度为k=2。

输出将类似于:

AA
AB
AC
AD
.
.
.
DD

总排列为16。

Answer 1

这不是一个排列，这可能解释了为什么你找不到答案。

你实际上问的是如何打印数字< code>0..k-1，使用数字< code>A、B、C、D。我将用熟悉的数字< code>0，1，2，3重写您的示例:

00
01
02
03
10
11
12
13
..
33

没有标准的C方法，但是现在你知道它的名字了，网上有很多代码。或者自己写。提示：i的最后一个数字具有值i%n。

Answer 2

你可以使用 std：：next_permutation（） 作为 πάντα ῥεῖ 说， 但是既然你想用重复来定义长度和字符， 你可以做一些容易实现它的事情， 如：

    std::string s = "aabbccdd";
    std::set<std::string> string_set;
    std::sort(s.begin(), s.end());
    do {
        string_set.insert(s.substr(0, 2));
    } while(std::next_permutation(s.begin(), s.end()));
    for(auto i = string_set.begin(); i != string_set.end(); ++i)
        std::cout << *i << std::endl;

Answer 3

简单的递归解决方案，肯定会对您有效。

让我首先重写您的规范：打印所有具有重复字符的排列

给定一个长度为n的字符串，打印给定字符串的所有排列。允许重复字符

对于给定的长度为n的字符串，将有长度为“length”的n^k可能字符串。这个想法是从一个空的输出字符串开始(在下面的代码中我们称之为前缀)。将所有字符逐个添加到前缀中。对于每个添加的字符，通过递归调用“length”等于“length”-1，打印所有可能的带有当前前缀的字符串。

#include <string>
#include <iostream>


void print_str(const char*,std::string,const int, const int);

int main()

{

    int lenght = 2;

    char str[] = {'A', 'B', 'C', 'D'};



    int n = sizeof str;

    print_str(str, "", n, lenght);  //Note: this function works on all cases and not just the case above

    return 0;

}

// The main recursive method to print all possible strings of length "length"
    void print_str(const char str[],std::string prefix,const int n, const int lenght)

    {

        if (lenght == 1)

            {

                for (int j = 0; j < n; j++)

                std::cout << prefix + str[j] << std::endl;

            }//Base case: lenght = 1, print the string "lenght" times + the remaining letter

        else

            {


               // One by one add all characters from "str" and recursively call for "lenght" equals to "lenght"-1
                for (int i = 0; i < n; i++)

                // Next character of input added
                print_str(str, prefix + str[i], n, lenght - 1);
                // "lenght" is decreased, because we have added a new character

            }

    }

下面是上面代码的执行：

引用：

http://www.geeksforgeeks.org/print-all-permutations-with-repetition-of-characters/

http://www.geeksforgeeks.org/print-all-combinations-of-given-length/

更新：此更新是根据以下规范编写的。

我需要更多的帮助！！因为我是CPP编程新手。假设长度=3，我如何将从长度=1到长度=3的所有排列组合在一个数组中。表示将长度为1、长度为2和长度为3的所有排列存储在一个数组中

#include <string>
#include <iostream>
#include <vector>

void print_str(const char*,std::string,const int, const int);
std::vector<std::string> permutations ;  // the vector permutations which will hold all the permutations, 
                                       //if you want you can use it for later use or you can use the array below which is nothing than a copy of this vector.

int NumberOfPermutations = 0; // this variable holds the number of permutations 



int main()

{

    int lenght = 3;

    char str[] = {'A', 'B', 'C', 'D'};

    int n = sizeof str;
//here we loop through all the possible lenghts 1, 2 and 3
    for (int k = 1; k <= lenght; k++)

               {

                   print_str(str, "", n, k);  //Note: this function works on all cases and not just the case above
                }


    std::string* permut_array =  new std::string[NumberOfPermutations]; // the array that we will use to store the permutations in

    std::copy(permutations.begin(), permutations.end(), permut_array); // here we copy the vector into the array 

    //if you want you can use your array to print the permutation as folow

    for (int k = 0; k < NumberOfPermutations; k++)

               {

                   std::cout << permut_array[k] << std::endl;
                }

    return 0;

}

// The main recursive method to print all possible strings of length "length"
    void print_str(const char str[],std::string prefix,const int n, const int lenght)

    {

        if (lenght == 1)

            {

                for (int j = 0; j < n; j++)

               {
                   // i commented this ligne so that if you want to use your array to print your permutations you will not get a screnn with permutations printed 2 times
                   //std::cout << prefix + str[j] << std::endl; 
                   permutations.push_back(prefix + str[j]); // the vector that we will use to store the permutations in
                }

            }//Base case: lenght = 1, print the string "lenght" times + the remaining letter

        else

            {


               // One by one add all characters from "str" and recursively call for "lenght" equals to "lenght"-1
                for (int i = 0; i < n; i++)

                // Next character of input added
                 print_str(str, prefix + str[i], n, lenght - 1);
                // "lenght" is decreased, because we have added a new character

            }
        NumberOfPermutations = permutations.size();
    }