- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Here's a interesting mathematical question: Is there a way to define a range object that lets us write a parallel_for that iterates over permutations of a set of N objects? Better yet, can it be done so that subranges are always in lexicographic order?
Here's how it might be used. The parallel_for invocation might look something like:
parallel_for( perm_range(N), Body() );
and Body::operator() might look something like:
void Body::operator()( const perm_range& r ) {
permutation p = r.begin();
while( p!=r.end() ) {
...process the permutation...
...get the next permutation...
std::next_permutation( p.begin(), p.end() );
};
}
For example, for N=3, we would want the permutations:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
to be generated. The hard part is figuring out how to divide a permutation range into two roughly equal subranges.
- Arch
P.S. TBB does support recursive parallelism, so it's straightforward to write a recursive program that does permutations in parallel, using a parallel_for at each recursion level. I can post that code if anyone cares.
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
I came up with a reasonably straightforward and efficient solution a while back, but didn't have time to post it until now. See code below. It still has printfs in it that are inappropriate for parallel execution, but I left them there to show where the permutations appear.
- Arch
// permute.cpp : Defines the entry point for the console application.
//
// Program that shows how to write a TBB-style recursive range for permutations.
// Author: Arch D. Robison
// Date: 9/18/2007
#include
#include
#include "tbb/parallel_for.h"
#include "tbb/task_scheduler_init.h"
//! Recursively divisible set of permutations of N objects of type T.
/** Internally, it represents all permutations x of a such that:
x==a for all k
x[position]is some a for k in [i,j)
x is some a for k in [position,N]
Be sure to use the default simple_partitioner, not auto_partitioner, because the range cannot be iterated
over unless is_divisible() returns true.
*/
template<typename T, size_t N>
class permutation_range {
unsigned position;
//! When position reaches limit, the set of permutations is no longer considered divisible.
const unsigned limit;
unsigned i, j;
T a;
//! Check that internal state is c
orrect.
bool assert_okay() {
assert( i
assert( j<=N );
assert( position<=i );
assert( position<=limit );
for( unsigned k=0; k
assert( a
for( unsigned n=0; n
assert( n==k || a!=a );
}
return true;
}
void normalize_if_leaf() {
if( position==limit-1 && i+1==j ) {
std::rotate(&a[position],a+i, a+i+1);
}
assert( assert_okay() );
}
public:
bool empty() const {
return position==N;
}
bool is_divisible() const {
return position+1
}
//! Construct initial permutation
permutation_range( const T x, unsigned grainsize ) :
position(0),
limit(N
i(0),
j(grainsize
{
std::copy( x, x+N, a );
assert( assert_okay() );
}
//! Splitting constructor
permutation_range( permutation_range& r, tbb::split ) : limit(r.limit) {
assert( r.assert_okay() );
assert( r.is_divisible() );
if( r.i+1==r.j ) {
assert(r.j==r.i+1);
std::rotate(&r.a[r.position],r.a+r.i, r.a+r.i+1);
r.i = ++r.position;
r.j = N;
}
std::copy( r.a, r.a+N, a );
int m = (r.j-r.i)/2;
assert(m>0);
j = r.j;
i = r.j = r.i+m;
position = r.position;
normalize_if_leaf();
r.normalize_if_leaf();
}
//! Set x[] to first permutation in this range.
void get_first_subpermutation( T x ) const {
assert(!is_divisible());
std::copy( a, a+N, x );
}
//! Advance x[] to the next permutation in this range. Returns true unless next permutation was a wrap.
bool next_subpermutation( T x ) const {
assert(!is_divisible());
return std::next_permutation( x+limit, x+N );
}
};
const int N = 5;
struct Body {
void operator()( const permutation_range<int,N>& r ) const {
int a;
r.get_first_subpermutation(a);
// Process all permutations in the subrange
printf(" slice
");
do {
// Operations on a given permutation
printf(" ");
for( int k=0; k
printf("%d ",a);
&n
bsp; printf("
");
// Get the next permutation
} while( r.next_subpermutation( a ) );
}
};
int main() {
const int N = 5;
tbb::task_scheduler_init init(1);
int a;
for( unsigned k=0; k
a = k;
// Try different grain sizes
for( int g=1; g<=N; ++g ) {
printf("With grain size=%d
",g);
tbb::parallel_for( permutation_range<int,N>(a,g), Body() );
}
return 0;
}

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page