我想知道CPP中是否已经有一个实现来查找重复长度为k(1,2,3,4等)的n个字符的所有排列.我希望有,但我找不到.
例如,如果string =(A,B,C,D)并且我想找到重复长度为k = 2的字符串的所有排列.
输出将是这样的:
AA
AB
AC
AD
.
.
.
DD
总排列数为16.
解决方法:
简单的递归解决方案,肯定会对你有用.
让我先重新编写您的规范:打印所有重复字符的排列
Given a string of length n, print all permutation of the given string.
Repetition of characters is allowed
对于大小为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/
更新:此更新正在写回答以下规范.
I need one more help!! as i am new to CPP programming. Suppose if
length = 3 how can i make it to get all permutations starting from
length = 1 to length = 3 together in an array. Means to get all the
permutations of length =1, length =2 and length = 3 together stored in
an array
#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();
}