更好的方法來實現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？

回答

相關問題