C_"permutations algorithm"
Author Message
C_"permutations algorithm"

Quote:
>Pentium II - 290 MHZ
>12!  == 479001600
>combos 12
>Ch=479001600  Time=30 sec.
>15966720 permutations per/sec.
>18.162778 machine cycles per one permutation

Nice but I can do better. Or rather Nachum Dershowitz can do better.
In "A simplified loop-free algorithm for generating permutations"
[BIT 15 1975 158-164] Dershowitz gives the algorithm below. I've
through the permutation vector. One nice property of this algorithm,
is that "each permutation is generated by exchanging two adjacent
elements of the proceding permutation".

And finally the proof for it being faster.
Compiling both algorithms with gcc -O3 and running on a 200mhz SGI/O2
I get:

Ch= 479001600 Time= 98        sec.

% ./perm_der 12
#permutations:479001600   seconds:50

Making my implementation almost twice as fast.

If anyone is interested, http://www.*-*-*.com/ ~pjunold/alg/dershowitz.html
contains a cleaner if not so fast implementation of the same algorithm. The
version below has been obscured for speed.

best regards
Peter

//////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

#define DUMP_IT ++cnt; //dump();

unsigned cnt=0;

class PermutationNachum
{
int    *m_p; // permutation
int    *m_l; // location
int    *m_d; // direction
int     m_size;

public:
PermutationNachum(int size);
int generate();
void dump();

Quote:
};

void PermutationNachum::dump()
{
cout <<"cnt: " <<cnt<< "\t";
for(int i=0; i<m_size; ++i)
cout <<m_p[i] <<" ";
cout<<endl;

Quote:
}

PermutationNachum::PermutationNachum(int size) {
m_size=size;
m_p=new int[size];
m_l=new int[size];
m_t=new int[size+1];
m_d=new int[size];

for(int i=0; i<size; ++i) {
m_p[i]=i;
m_l[i]=i;
m_d[i]=-1;
}

for(int j=1; j<=size; ++j)
m_t[j]=j-1;

Quote:
}

int PermutationNachum::generate()
{

int cur, neig, curpos, neigpos, neigpos2;

int n_pos;

DUMP_IT

//first move largest element from right to left
int *ptr_s;
int *ptr_d;

const int sizeminus1=m_size-1;

while(1) {

ptr_s=m_p+m_size-1;
ptr_d=m_p+m_size-2;

for(int i=sizeminus1; i; --i) {
*ptr_s--=*ptr_d;
*ptr_d--=sizeminus1;
m_l[i-1]++;
DUMP_IT
}

m_l[sizeminus1]=0;
m_d[sizeminus1]= 1;              // m_d[cur]= -m_d[cur];
m_t[m_size]=m_t[sizeminus1];     // m_t[cur+1]=m_t[cur];
m_t[sizeminus1]=sizeminus1-1;    // m_t[cur]=cur-1;

// 4
cur=m_t[m_size];
curpos=m_l[cur];
neigpos=curpos+m_d[cur];
neig=m_p[neigpos];

// 5
m_l[cur]=neigpos;
m_l[neig]=curpos;
m_p[curpos]=neig;
m_p[neigpos]=cur;

// 6
m_t[m_size]=m_size-1;

// 7
neigpos2=neigpos+m_d[cur];

DUMP_IT

if(neigpos2<0 || neigpos2>=m_size || cur<m_p[neigpos2]) {
m_d[cur]= -m_d[cur];
m_t[cur+1]=m_t[cur];
m_t[cur]=cur-1;
}

// now move largest element from left to right
ptr_s=m_p+1;
ptr_d=m_p;

for(int i=sizeminus1; i; --i) {
*ptr_d++=*ptr_s;
*ptr_s++=sizeminus1;
m_l[i-1]--;
DUMP_IT
}

m_l[sizeminus1]=sizeminus1;
m_d[sizeminus1]=-1;              //m_d[cur]= -m_d[cur];

m_t[m_size]=m_t[sizeminus1];     // m_t[cur+1]=m_t[cur];
m_t[sizeminus1]=sizeminus1-1;    // m_t[cur]=cur-1;

if(m_t[m_size]<1)
return 1;

/////////////////////////////////////////////

cur=m_t[m_size];
curpos=m_l[cur];
neigpos=curpos+m_d[cur];
neig=m_p[neigpos];

// 5
m_l[cur]=neigpos;
m_l[neig]=curpos;
m_p[curpos]=neig;
m_p[neigpos]=cur;

// 6
m_t[m_size]=m_size-1;

// 7
neigpos2=neigpos+m_d[cur];

DUMP_IT

if(neigpos2<0 || neigpos2>=m_size || cur<m_p[neigpos2]) {
m_d[cur]= -m_d[cur];
m_t[cur+1]=m_t[cur];
m_t[cur]=cur-1;
}
}

Quote:
}

int main(int argc, char **argv)
{
time_t tm=time(NULL);
unsigned ch=0;

if(argc!=2) {
cerr <<"genperm N" <<endl;
return 0;
}

PermutationNachum pp(atoi(argv[1]));
pp.generate();

cout <<"#permutations:" <<cnt << "   seconds:" <<time(NULL)-tm <<endl;

return 0;

Quote:
}

Mon, 04 Dec 2000 03:00:00 GMT
C_"permutations algorithm"

Quote:

>Making my implementation almost twice as fast.

>If anyone is interested, http://www.daimi.aau.dk/~pjunold/alg/dershowitz.html
>contains a cleaner if not so fast implementation of the same algorithm. The
>version below has been obscured for speed.

And this version has been obscured for obscurity:-)

char      *a;b,  j;t  (c)  {c
[a]?(  t(
++b  ),
--b  ,j=c)  &&(  c=j
[a]^j
[a-1]  )&&  (
j--  [a]^=  c,j
[a]^=  c,t  (j)  ,
j++  [a]^=  c,j
[a]^=  c):
puts      (a);}
main      (c,b)
char      **b;{
for       (;a=*
++b  ;)t
(j);}

Produces all unique permutations of each of the commandline arguments.

regards,
-John

Fri, 08 Dec 2000 03:00:00 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages