在任何项目可以重复任意次数的时候,我们如何生成 n (给定)不同项目的所有可能排列?
组合学告诉我会有n^r个,只是想知道如何用 C++/python 生成它们?
在任何项目可以重复任意次数的时候,我们如何生成 n (给定)不同项目的所有可能排列?
组合学告诉我会有n^r个,只是想知道如何用 C++/python 生成它们?
这是 C++ 中的一个可能实现,沿用标准库函数 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
将您的排列视为基于n的数值系统中的r数字。从 000...0 开始,并将“数字”加一:0000, 0001, 0002, 000(r-1), 0010, 0011, ...
代码非常简单。
这是@Inspired 方法的示例,其中 n 作为字母表的前三个字母并且 r = 3:
alphabet = [ 'a', 'b', 'c' ]
def symbolic_increment( symbol, alphabet ):
## increment our "symbolic" number by 1
symbol = list(symbol)
## we reverse the symbol to maintain the convention of having the LSD on the "right"
symbol.reverse()
place = 0;
while place < len(symbol):
if (alphabet.index(symbol[place])+1) < len(alphabet):
symbol[place] = alphabet[alphabet.index(symbol[place])+1]
break
else:
symbol[place] = alphabet[0];
place+=1
symbol.reverse()
return ''.join(symbol)
permutations=[]
r=3
start_symbol = alphabet[0] * (r)
temp_symbol = alphabet[0] * (r)
while 1:
## keep incrementing the "symbolic number" until we get back to where we started
permutations.append(temp_symbol)
temp_symbol = symbolic_increment( temp_symbol, alphabet)
if( temp_symbol == start_symbol ): break
您也可以使用 itertools 来完成:
from itertools import product
r=3
for i in xrange(r-1):
if (i==0):
permutations = list(product(alphabet, alphabet))
else:
permutations = list(product(permutations, alphabet))
permutations = [ ''.join(item) for item in permutations ]