c++ - 通过重复生成所有排列

Question

我们如何才能生成 n(给定)在 r 中任意项目可以重复任意次数的不同项目的所有可能排列？

组合学告诉我会有 n^r 个，只是想知道如何用 C++/python 生成它们？

Answer 1

这里有一个可能的 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