更好的方法来实现count_permutations？

我需要一个函数count_permutations（），它返回给定范围的排列数。 假设范围内允许进行修改，并在第一置换开始，我天真地实现这个作为重复调用next_permutation（）如下：更好的方法来实现count_permutations？

template<class Ret, class Iter> 
Ret count_permutations(Iter first, Iter last) 
{ 
    Ret ret = 0; 
    do { 
     ++ret; 
    } while (next_permutation(first, last)); 
    return ret; 
}

有那并不是一个更快的方法你需要迭代所有的排列来找到答案？它仍然可以假定输入可以被修改，并且从第一个排列开始，但是显然如果可以在没有这些推断的情况下实现，它也会很好。

来源

2008-11-09 Greg Rogers

所有元素都是唯一的范围的排列数是n！其中n是范围的长度。

如果有重复的元素，您可以使用n！/（n_0！）...（n_m！），其中n_0 ... n_m是重复范围的长度。

因此，例如[1,2,3]有3！ = 6排列，而[1,2,2]排列3！/ 2！ = 3个排列。

编辑：一个更好的例子是[1,2,2,3,3,3]它有6！/ 2！3！ = 60个排列。

来源

2008-11-09 16:25:54

好吧，那么如果范围排序，它将需要通过范围一遍查找所有大小的重复范围。谢谢。 – 2008-11-09 16:38:58

对于C++来说，是的，如果范围是排序的，会更容易。对于像Python这样的动态类型语言，即使是未排序的列表也可以。即使您必须对范围进行排序，时间复杂度将为O（n log n + n）= O（n log n），而不会考虑阶乘计算。 – 2008-11-09 16:46:56

在数学中，函数factorial！n表示n个元素的排列数。正如坎格和格雷格所指出的那样，如果一组中有重复的元素，要考虑它们，我们必须将因子除以每个不可区分组（由相同元素组成的组）的排列数。

以下实现计算[first，end）范围内元素的排列数。范围不需要排序。

// generic factorial implementation... 

int factorial(int number) { 
    int temp; 
    if(number <= 1) return 1; 
    temp = number * factorial(number - 1); 
    return temp; 
} 

template<class Ret, class Iter> 
Ret count_permutations(Iter first, Iter end) 
{ 
    std::map<typename Iter::value_type, int> counter; 
    Iter it = first; 
    for(; it != end; ++it) { 
     counter[*it]++; 
    } 

    int n = 0; 
    typename std::map<typename Iter::value_type, int>::iterator mi = counter.begin(); 
    for(; mi != counter.end() ; mi++) 
     if (mi->second > 1) 
      n += factorial(mi->second); 

    return factorial(std::distance(first,end))/n; 
}

来源

2008-11-09 16:31:06

更好的方法来实现count_permutations？

回答

相关问题