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


Quote:
>/*  Buyanovsky's permutations algorithm [1997]
>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
followed his advice and made special optimization for moving N
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:

% ./perm_buy 12
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_t; // linked list
  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  
 
 [ 2 post ] 

 Relevant Pages 

1. Comments on "Algorithm in C" or "Algorithm in C++"

2. "Until" Algorithm

3. Algorithm for "diff"ing files/strings

4. Algorithm for "bit copy" function

5. Wanted: "tick" algorithm for graph axis

6. "Best fit" algorithm (help)

7. source code in "Algorithms in C"

8. remove() vrs fopen("""w")

9. Displaying binary data as ascii "1"'s and "0"'s

10. Looking for "Shroud"/"Obfus"

11. ""help with TSR""

12. Parse trees and "("")"

 

 
Powered by phpBB® Forum Software