来自 n 个字符的长度为 k 的所有排列，在 CPP 中有重复
All permutations of length k from n characters with repetition in CPP
我想知道 CPP 中是否已经有一个实现来查找长度为 k（1,2,3,4 等）的 n 个字符的所有排列并重复。我希望有，但我找不到。
例如，如果 string= (A,B,C,D) 并且我想找到 string 的所有排列，重复长度为 k =2。
输出将类似于：
AA
AB
AC
AD
.
.
.
DD
16 的总排列。
你可以用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;
这不是一个排列，这可能解释了为什么你找不到答案。
您实际上要问的是如何使用数字 A,B,C,D 打印基数 n 中的数字 0..k-1。我将用熟悉的数字重写您的示例 0,1,2,3 :
00
01
02
03
10
11
12
13
..
33
没有用于此的标准 C++ 方法，但现在您知道它的名称了，网络上有大量代码。或者自己写。提示：i 的最后一位的值为 i % n。
肯定适合您的简单递归解决方案。
让我先重写您的规范：打印所有重复字符的排列
Given a string of length n, print all permutation of the given string.
Repetition of characters is allowed
对于给定的大小为 n 的字符串，将有 n^k 种可能的长度为 "length" 的字符串。这个想法是从一个空的输出字符串开始（我们在下面的代码中称之为前缀）。将所有字符一一添加到前缀中。对于添加的每个字符，通过递归调用 "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();
}
此解决方案适用于所有标准容器和静态数组。我认为这也可以用于 类 和结构
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <list>
#include <iterator>
template<typename InputIt, typename T>
bool nextPermutationWithRepetition(InputIt begin, InputIt end, T from_value, T to_value) {
auto it = std::find_if_not(std::make_reverse_iterator(end),
std::make_reverse_iterator(begin),
[&to_value](auto current) { return to_value == current; });
if (it == std::make_reverse_iterator(begin))
return false;
auto bound_element_iterator = std::prev(it.base());
(*bound_element_iterator)++;
std::fill(std::next(bound_element_iterator), end, from_value);
return true;
}
int main() {
std::list<int> vec(3, 0);
do {
std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
} while (nextPermutationWithRepetition(vec.begin(), vec.end(), 0, 2));
return 0;
}
我想知道 CPP 中是否已经有一个实现来查找长度为 k（1,2,3,4 等）的 n 个字符的所有排列并重复。我希望有，但我找不到。
例如，如果 string= (A,B,C,D) 并且我想找到 string 的所有排列，重复长度为 k =2。
输出将类似于：
AA
AB
AC
AD
.
.
.
DD
16 的总排列。
你可以用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;
这不是一个排列，这可能解释了为什么你找不到答案。
您实际上要问的是如何使用数字 A,B,C,D 打印基数 n 中的数字 0..k-1。我将用熟悉的数字重写您的示例 0,1,2,3 :
00
01
02
03
10
11
12
13
..
33
没有用于此的标准 C++ 方法，但现在您知道它的名称了，网络上有大量代码。或者自己写。提示：i 的最后一位的值为 i % n。
肯定适合您的简单递归解决方案。
让我先重写您的规范：打印所有重复字符的排列
Given a string of length n, print all permutation of the given string. Repetition of characters is allowed
对于给定的大小为 n 的字符串，将有 n^k 种可能的长度为 "length" 的字符串。这个想法是从一个空的输出字符串开始（我们在下面的代码中称之为前缀）。将所有字符一一添加到前缀中。对于添加的每个字符，通过递归调用 "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();
}
此解决方案适用于所有标准容器和静态数组。我认为这也可以用于 类 和结构
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <list>
#include <iterator>
template<typename InputIt, typename T>
bool nextPermutationWithRepetition(InputIt begin, InputIt end, T from_value, T to_value) {
auto it = std::find_if_not(std::make_reverse_iterator(end),
std::make_reverse_iterator(begin),
[&to_value](auto current) { return to_value == current; });
if (it == std::make_reverse_iterator(begin))
return false;
auto bound_element_iterator = std::prev(it.base());
(*bound_element_iterator)++;
std::fill(std::next(bound_element_iterator), end, from_value);
return true;
}
int main() {
std::list<int> vec(3, 0);
do {
std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
} while (nextPermutationWithRepetition(vec.begin(), vec.end(), 0, 2));
return 0;
}