Re: [boost] combinations and permutations

Subject: Re: [boost] combinations and permutations
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2011-01-04 19:07:49

On Jan 4, 2011, at 4:37 PM, Thorsten Ottosen wrote:

> Den 04-01-2011 19:56, Howard Hinnant skrev:
>> On Jan 4, 2011, at 12:00 PM, Thorsten Ottosen wrote:
>> 
>>> Den 04-01-2011 04:40, Howard Hinnant skrev:
>>>> Warming this up for tr2:
>>>> 
>>>> http://home.roadrunner.com/~hinnant/combinations.html
>>>> 
>>>> Comments welcome.  Real world use welcome.
> 
>> I'm curious:  Which algorithms of his do you use?  And for what
>> ballpark ranges of r (distance[first, middle)) and N (distance(first,
>> last))?
> 
> I can see that I have only used next_combination(), and in my case I needed to call it for all possible sizes of combinations, so I call next_combination() inside a for loop.
> 
> I have no predetermined bound on N, it depends on my models, but can range from 10 to 30 to even more, although such N usually become intractable.

I ran some performance tests for this scenario.  This tests compares the next_combination algorithm with the for_each_combination, with the visit for each combination doing nothing but a long long increment.  The test prints out the N, the total time for each algorithm.  The time/visit for each algorithm, and the time for next_combination / the time for for_each_combination.  Here is the code:

#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>

struct F
{
    unsigned long long count_;

    F() : count_(0) {}

    void operator()(std::vector<int>::iterator, std::vector<int>::iterator)
    {++count_;}
};

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    typedef std::chrono::duration<double, std::nano> ns;
    int n = 33;
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 0);
    F f;
    Clock::time_point t0 = Clock::now();
    for (std::vector<int>::iterator r = std::next(v.begin()); r != v.end(); ++r)
    {
        do
        {
            f(v.begin(), r);
        } while (next_combination(v.begin(), r, v.end()));
    }
    Clock::time_point t1 = Clock::now();
    sec s0 = t1 - t0;
    ns pvt0 = s0 / f.count_;
    f = F();
    t0 = Clock::now();
    for (std::vector<int>::iterator r = std::next(v.begin()); r != v.end(); ++r)
        f = for_each_combination(v.begin(), r, v.end(), f);
    t1 = Clock::now();
    sec s1 = t1 - t0;
    ns pvt1 = s1 / f.count_;
    std::cout << "N = " << v.size() << ", visits = " << f.count_
              << "\n\tnext_combination total = " << s0.count() << " seconds"
              << ", next_combination per visit = " << pvt0.count() << " nanoseconds"
              << "\n\tfor_each_combination = " << s1.count() << " seconds"
              << ", for_each_combination per visit = " << pvt1.count() << " nanoseconds"
              << "\n\tnext_combination/for_each_combination = " << s0/s1 << '\n';
}

And here are the results:

N = 10, visits = 1022
        next_combination total = 2.292e-05 seconds, next_combination per visit = 22.4266 nanoseconds
        for_each_combination = 1.7091e-05 seconds, for_each_combination per visit = 16.7231 nanoseconds
        next_combination/for_each_combination = 1.34106

N = 20, visits = 1048574
        next_combination total = 0.0268492 seconds, next_combination per visit = 25.6054 nanoseconds
        for_each_combination = 0.0144714 seconds, for_each_combination per visit = 13.8011 nanoseconds
        next_combination/for_each_combination = 1.85532

N = 30, visits = 1073741822
        next_combination total = 32.2251 seconds, next_combination per visit = 30.012 nanoseconds
        for_each_combination = 14.4642 seconds, for_each_combination per visit = 13.4709 nanoseconds
        next_combination/for_each_combination = 2.22792

N = 31, visits = 2147483646
        next_combination total = 65.1725 seconds, next_combination per visit = 30.3483 nanoseconds
        for_each_combination = 28.9122 seconds, for_each_combination per visit = 13.4633 nanoseconds
        next_combination/for_each_combination = 2.25415

N = 32, visits = 4294967294
        next_combination total = 131.869 seconds, next_combination per visit = 30.703 nanoseconds
        for_each_combination = 57.8251 seconds, for_each_combination per visit = 13.4635 nanoseconds
        next_combination/for_each_combination = 2.28047

N = 33, visits = 8589934590
        next_combination total = 266.712 seconds, next_combination per visit = 31.0493 nanoseconds
        for_each_combination = 115.835 seconds, for_each_combination per visit = 13.4849 nanoseconds
        next_combination/for_each_combination = 2.30252

In this scenario the number of visits grows rapidly with N: visits = 2^N - 2.  And in this scenario for_each_combination is only 2x faster than next_combination which may not make any difference if your visit time is much greater than a few tens of nanoseconds.  If your visit time is greater than that, then that will be the driving factor for performance, and not the combination algorithm.

> So I haven' used all of Herve's interface, although I think they could be useful at some point. The thing is, once you need one of these functions, then it's soo nice to find one implemented and tested.

Much agreed.  Though I must admit that I haven't invested enough time to really understand the use case for next_mapping.

I have found other requests for the functionality offered by for_each_reversible_permutation.  The suggested solution to that query was not the algorithm I've implemented, and would be horribly inefficient (though correct) if implemented.

> 
> In general, I believe there are much more efficient ways to visit all
> combinations (*) than using the swap-based algorithms provided by Herve, but they give me a fast solution I can use to unit-test other more complicated approached (at least for small N).
> 
> -Thorsten
> 
> (*) I have a paper lying around somewhere .... don't have time to find it ... something along "subset enumeration trees" or something

Thanks for the link! (in your next post).  I've skimmed it.

-Howard