重复生成所有排列 [英] Generating all permutations with repetition
本文介绍了重复生成所有排列的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我们如何生成 n (给定) r 个不同项目的所有可能排列,而每次项目都可以重复多次?
How could we generate all possible permutations of n (given) distinct items taken r at a time where any item can be repeated any number of times?
组合器告诉我会有 n ^ r 个,只是想知道如何使用C ++/python生成它们?
Combinatorics tell me that there will be n^r of them, just wondering how to generate them with C++/python?
推荐答案
以下是标准库函数std :: next_permutation
Here is a possible implementation in C++, along the lines of the standard library function std::next_permutation
//---------------------------------------------------------------------------
// Variations with repetition in lexicographic order
// k: length of alphabet (available symbols)
// n: number of places
// The number of possible variations (cardinality) is k^n (it's like counting)
// Sequence elements must be comparable and increaseable (operator<, operator++)
// The elements are associated to values 0÷(k-1), max=k-1
// The iterators are at least bidirectional and point to the type of 'max'
template <class Iter>
bool next_variation(Iter first, Iter last, const typename std::iterator_traits<Iter>::value_type max)
{
if(first == last) return false; // empty sequence (n==0)
Iter i(last); --i; // Point to the rightmost element
// Check if I can just increase it
if(*i < max) { ++(*i); return true; } // Increase this element and return
// Find the rightmost element to increase
while( i != first )
{
*i = 0; // reset the right-hand element
--i; // point to the left adjacent
if(*i < max) { ++(*i); return true; } // Increase this element and return
}
// If here all elements are the maximum symbol (max=k-1), so there are no more variations
//for(i=first; i!=last; ++i) *i = 0; // Should reset to the lowest sequence (0)?
return false;
} // 'next_variation'
这就是用法:
std::vector<int> b(4,0); // four places initialized to symbol 0
do{
for(std::vector<int>::const_iterator ib=b.begin(); ib!=b.end(); ++ib)
{
std::cout << std::to_string(*ib);
}
std::cout << '\n';
}
while( next_variation(b.begin(), b.end(), 2) ); // use just 0-1-2 symbols
这篇关于重复生成所有排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文