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
