CODEWITHSUNDEEP
c++algorithmmath
Greg Rogers
Greg Rogers

Reputation: 36459

Better way to implement count_permutations?

I need a function count_permutations() that returns the number of permutations of a given range. Assuming that the range is allowed to be modified, and starts at the first permutation, I could naively implement this as repeated calls to next_permutation() as 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? It could still assume that the input can be modified, and starts in the first permutation, but obviously if it is possible to implement without those assumtions it'd be great too.

Upvotes: 1

Views: 382

Answers (2)

Nicola Bonelli
Nicola Bonelli

Reputation: 8287

In math the function factorial !n represents the number of permutations of n elements.

As Can Berg and Greg suggested, if there are repeated elements in a set, to take them into account, we must divide the factorial by the number of permutations of each indistinguishable group (groups composed of identical elements).

The following implementation counts the number of permutations of the elements in the range [first, end). The range is not required to be sorted.

// 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;
}

Upvotes: 0

Can Berk G&#252;der
Can Berk G&#252;der

Reputation: 113370

The number of permutations for a range where all the elements are unique is n! where n is the length of the range.

If there are duplicate elements, you can use n!/(n_0!)...(n_m!) where n_0...n_m are the lengths of duplicate ranges.

So for example [1,2,3] has 3! = 6 permutations while [1,2,2] has 3!/2! = 3 permutations.

EDIT: A better example is [1,2,2,3,3,3] which has 6!/2!3! = 60 permutations.

Upvotes: 9

Related Questions