[boost] for_each combination/permutation - call for interest

5 Sep 2005

      On and off for the past 7 months (well, mostly off), I've been working 
on a few combination/permutation algorithms.  I was inspired by the CUJ 
article written by John Dibling in the Feb. 2005 issue titled 
"Extending the STL".

The std::lib currently has next_permutation, perv_permutation.  But 
these functions are lacking in two respects:

1.  They only allow the entire sequence to be permuted.  They do not 
allow (for example) the ability to find all permutations of 5 items 
considered only 2 at a time.

Consider 5 items 2 at a time from this sequence
1   : a b c d e
Permutations
1   : a b
2   : a c
3   : a d
4   : a e
5   : b a
6   : b c
7   : b d
8   : b e
9   : c a
10  : c b
11  : c d
12  : c e
13  : d a
14  : d b
15  : d c
16  : d e
17  : e a
18  : e b
19  : e c
20  : e d

When you know that you need to consider only a few items at a time, 
std::next_permutation is excessively expensive as it will loop through 
many more iterations.  (e.g. consider the permutations of 5 items 5 at 
a time leads to a list of 120 - vs 20 sequences).

2.  std::next/prev_permutation require a sorted sequence and an 
ordering predicate.  This is not always convenient.

In addition to permutations of N objects taken K at a time, other 
useful algorithms would be:

*  Circular permutations of N objects taken K at a time.
*  Combinations of N objects taken K at a time.
*  Reversible permutations of N objects taken K at a time.
*  Reversible circular permutations of N objects taken K at a time.

Out of these 5 algorithms, today I can only present the first 3.  The 
reversible versions are meant to take a sequence over all permutations 
where an order, and the reverse order are considered to be the same 
sequence.  E.g.

1 2 3 4 is the same permutation as 4 3 2 1 for a "reversible" 
permutation.

This is handy in situations where you are scoring "distances" between 
items in the list, and it doesn't matter which direction the list is 
traveled in.  Unfortunately I haven't yet found a way to efficiently 
compute these "reversible" permutations.

---
Interface
---

I've followed the advice of John Dibling in the CUJ article except that 
the functor doesn't receive the entire range, but only the first K 
elements.  For example consider:

char array[] = {'a', 'b', 'c', 'd', 'e'};
unsigned size_array = sizeof(array)/sizeof(array[0]);
const int k = 3;
print p = std::for_each_combination(array, array + size_array, k, 
print());

This calls the print() functor (say p) like:

     p(array, array+k);

for array permuted such that [array, array+k) will hold each 
combination of 3 items taken from the total of 5 items.  And after the 
for_each_combination call, array will be in its original order.  While 
always permuting the elements into positions [0, k) may at first seem 
limiting in how the for_each_* algorithms can be implemented, it offers 
interesting possibilities for the functors.

If a functor knows the total length of the sequence (say N), and 
receives [array, array+k) as a subsequence representing the current 
combination/permutation, that functor can then call for_each_* on the 
remaining sequence [array+k, array+N).  This allows for a very complex 
analysis where one considers all combinations (or permutations) of the 
first k elements, and then simultaneously considers permutations of the 
remaining elements for each of the outer combinations.

One could use this capability to search for solutions to variations of 
the traveling salesman problem.  Instead of minimizing the route of 1 
salesman over N cities.  You might want to minimize two salesmen's 
routes over the same set of cities, each city being visited by one and 
only one salesman.  For example you might consider:

For each circular-reversible permutation of 10 cities considered 5 at a 
time:
     Compute distance around the 5 city route and add to that:
     For each circular-reversible permutation of the remaining 5 cities 
considered 5 at a time:
        Compute distance around the 5 city route.
        Record minimum combined distance and routes.

Naturally this technique can easily be generalized to M salesmen 
covering N cites, N/M cites covered by each salesman.  Unfortunately I 
currently lack the circular-reversible permutation algorithm and have 
to instead use the twice-as-expensive circular permutation algorithm.

The three algorithms I do have are here:

#include <iterator>
#include <algorithm>

namespace test
{

namespace detail
{

template<class BidirectionalIterator, class Function, class Size>
Function
permute(BidirectionalIterator first, BidirectionalIterator mid,
           BidirectionalIterator active, BidirectionalIterator last,
           Size k, Function f, Size n)
{
     if (k == 0)
         f(first, mid);
     else
     {
         using std::swap;
         BidirectionalIterator activep1 = active;
         ++activep1;
         BidirectionalIterator p = active;
         ++p;
         for (Size i = 0; i < n; ++i, ++p)
         {
             if (k == 1)
                 f(first, mid);
             else
                 f = permute<BidirectionalIterator,Function,Size>(first, 
mid, activep1, last, k-1, f , n-1);
             if (i != n-1)
                 swap(*active, *p);
         }
         std::rotate(active, activep1, last);
     }
     return f;
}

template<class BidirectionalIterator, class Function, class Size>
Function
combine(BidirectionalIterator first, BidirectionalIterator mid,
            BidirectionalIterator active, BidirectionalIterator last,
            Size k, Function f, Size n)
{
     if (k == 0)
         f(first, mid);
     else
     {
         Size e = n - k + 1;
         Size nn = n-1;
         BidirectionalIterator l2 = last;
         BidirectionalIterator ap1 = active;
         ++ap1;
         BidirectionalIterator apk = active;
         std::advance(apk, k);
         for (Size i = 0; i < e; ++i, --nn, --l2)
         {
             if (k == 1)
                 f(first, mid);
             else
                 f = combine<BidirectionalIterator,Function,Size>(first, 
mid, ap1, l2, k-1, f, nn);
             std::rotate(active, i < e-1 ? ap1 : apk, last);
         }
     }
     return f;
}

}  // detail

template<class BidirectionalIterator, class Function, class Size>
Function
for_each_permutation(BidirectionalIterator first, BidirectionalIterator 
last, Size k, Function f)
{
     typedef typename 
std::iterator_traits<BidirectionalIterator>::difference_type 
difference_type;
     Size n = static_cast<Size>(std::distance(first,last));
     if (k < 1 || n == 0)
         return f;
     if (k > n)
         k = n;
     BidirectionalIterator mid = first;
     std::advance(mid, k);
     return detail::permute<BidirectionalIterator,Function,Size>(first, 
mid, first, last, k, f, n);
}

template<class BidirectionalIterator, class Function, class Size>
Function
for_each_circular_permutation(BidirectionalIterator first, 
BidirectionalIterator last, Size k, Function f)
{
     typedef typename 
std::iterator_traits<BidirectionalIterator>::difference_type 
difference_type;
     Size n = static_cast<Size>(std::distance(first,last));
     if (k < 1 || n == 0)
         return f;
     if (k > n)
         k = n;
     BidirectionalIterator mid = first;
     std::advance(mid, k);
     BidirectionalIterator f2 = first;
     ++f2;
     for (Size i = 0, e = n - k + 1; i < e; ++i, --n, ++first, ++f2, 
++mid)
         f = detail::permute<BidirectionalIterator,Function,Size>(first, 
mid, f2, last, k-1, f, n-1);
     return f;
}

template<class BidirectionalIterator, class Function, class Size>
Function
for_each_combination(BidirectionalIterator first, BidirectionalIterator 
last, Size k, Function f)
{
     typedef typename 
std::iterator_traits<BidirectionalIterator>::difference_type 
difference_type;
     Size n = static_cast<Size>(std::distance(first,last));
     if (k < 1)
         return f;
     if (k > n)
         k = n;
     BidirectionalIterator mid = first;
     std::advance(mid, k);
     return detail::combine<BidirectionalIterator,Function,Size>(first, 
mid, first, last, k, f, n);
}

}  // test

And here's a demo that exercises all 3 algorithms:

// demo

#include <iostream>
#include <iterator>
#include <algorithm>

class print
{
public:
     print() : i_(0) {}

     unsigned get() const {return i_;}

     template <class It>
     void operator()(It first, It last)
     {
         typedef typename std::iterator_traits<It>::value_type 
value_type;
         std::ostream_iterator<value_type> out(std::cout, " ");
         std::cout << ++i_ << "\t: ";
         std::copy(first, last, out);
         std::cout << '\n';
     }
private:
     unsigned i_;
};

int main()
{
     char array[] = {'a', 'b', 'c', 'd', 'e'};
     unsigned size_array = sizeof(array)/sizeof(array[0]);
     const int k = 3;
     std::cout << "Consider " << size_array << " items " << k << " at a 
time from this sequence\n";
     print()(array, array + size_array);
     {
     std::cout << "Permutations\n";
     print p = test::for_each_permutation(array, array + size_array, k, 
print());
     std::cout << "--- Total of " << p.get() << " calls ---\n";
     std::cout << "Sequence left in orginal order\n";
     print()(array, array + size_array);
     std::cout << '\n';
     }
     {
     std::cout << "Circular Permutations\n";
     print p = test::for_each_circular_permutation(array, array + 
size_array, k, print());
     std::cout << "--- Total of " << p.get() << " calls ---\n";
     std::cout << "Sequence left in orginal order\n";
     print()(array, array + size_array);
     std::cout << '\n';
     }
     {
     std::cout << "Combinations\n";
     print p = test::for_each_combination(array, array + size_array, k, 
print());
     std::cout << "--- Total of " << p.get() << " calls ---\n";
     std::cout << "Sequence left in orginal order\n";
     print()(array, array + size_array);
     std::cout << '\n';
     }
}

The output should be:

Consider 5 items 3 at a time from this sequence
1   : a b c d e
Permutations
1   : a b c
2   : a b d
3   : a b e
4   : a c b
5   : a c d
6   : a c e
7   : a d b
8   : a d c
9   : a d e
10  : a e b
11  : a e c
12  : a e d
13  : b a c
14  : b a d
15  : b a e
16  : b c a
17  : b c d
18  : b c e
19  : b d a
20  : b d c
21  : b d e
22  : b e a
23  : b e c
24  : b e d
25  : c a b
26  : c a d
27  : c a e
28  : c b a
29  : c b d
30  : c b e
31  : c d a
32  : c d b
33  : c d e
34  : c e a
35  : c e b
36  : c e d
37  : d a b
38  : d a c
39  : d a e
40  : d b a
41  : d b c
42  : d b e
43  : d c a
44  : d c b
45  : d c e
46  : d e a
47  : d e b
48  : d e c
49  : e a b
50  : e a c
51  : e a d
52  : e b a
53  : e b c
54  : e b d
55  : e c a
56  : e c b
57  : e c d
58  : e d a
59  : e d b
60  : e d c
--- Total of 60 calls ---
Sequence left in orginal order
1   : a b c d e

Circular Permutations
1   : a b c
2   : a b d
3   : a b e
4   : a c b
5   : a c d
6   : a c e
7   : a d b
8   : a d c
9   : a d e
10  : a e b
11  : a e c
12  : a e d
13  : b c d
14  : b c e
15  : b d c
16  : b d e
17  : b e c
18  : b e d
19  : c d e
20  : c e d
--- Total of 20 calls ---
Sequence left in orginal order
1   : a b c d e

Combinations
1   : a b c
2   : a b d
3   : a b e
4   : a c d
5   : a c e
6   : a d e
7   : b c d
8   : b c e
9   : b d e
10  : c d e
--- Total of 10 calls ---
Sequence left in orginal order
1   : a b c d e

Note that the functor (print() in this case) can be stateful, and that 
state is accumulated from call to call, and returned back to the 
client.  In this case the state is a simple line number counter.

Anyway, I offer these up on the chance they might be useful, and on the 
chance that someone might help complete the library to compute 
"reversible" permutations, which may indeed be quite useful (as in the 
traveling salesman problem, and variations of it).

-Howard

[boost] for_each combination/permutation - call for interest

Howard Hinnant