- 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