Best way to implement count_permutations?
I need a count_permutations () function that returns the number of permutations of a given range. Assuming the range is changeable and starts at the first permutation, I could naively implement this as repeated calls to next_permutation () as shown below:
template<class Ret, class Iter>
Ret count_permutations(Iter first, Iter last)
{
Ret ret = 0;
do {
++ret;
} while (next_permutation(first, last));
return ret;
}
Is there a faster way that doesn't require iterating through all the permutations to find the answer? He can still assume that the input can be changed and starts with the first permutation, but obviously if it can be implemented without these assumptions, that would be great too.
source to share
The number of permutations for a range in which all elements are unique is n! where n is the length of the range.
If there are duplicate items, you can use n! / (N_0!) ... (n_m!), Where n_0 ... n_m are the lengths of the repeating ranges.
So, for example, [1,2,3] has 3! = 6, while [1,2,2] has 3! / 2! = 3.
EDIT: The best example is [1,2,2,3,3,3], which has 6! / 2! 3! = 60 permutations.
source to share
In mathematics, the factorial! n represents the number of n-element permutations.
As Berg and Greg suggested that if there are duplicate elements in a set, in order to take them into account, we must divide the factorial by the number of permutations of each indistinguishable group (groups of the same elements).
The following implementation counts the number of permutations of elements in the range [first, end]. The range is not required for sorting.
// 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;
}
source to share