permute.c


/* generates ordered sets of permutations */
/* emilbarton 2009-2013 */
/* Compilation: gcc permute.c -o permute */

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <time.h>

// Global variables:
int Ole; int Scnt; size_t Psiz;
char* Orip; char Perm[25]; char* Permp = Perm;

// Functions:
void     stdoset(void);
void     stdorec(char*,int);
void     perm(char*,int,int);

/// Bait: 
void stdoset (void) {
  int lev = 0; Scnt++;
  fprintf(stdout,"%s\n",Permp);
  stdorec(Permp, lev) ;
} // END stdoset()

/// Recursion: 
void stdorec(char* strp, int lev) {
  int pos;
  unsigned char* newp ;
  newp = malloc(Psiz);
  strcpy(newp,strp);
  for (pos = lev; pos < Psiz; pos++){
    if (pos != lev) {
      Scnt++;
      perm(newp,lev,pos);
      fprintf(stdout,"%s\n",newp);
    }
    stdorec(newp, lev+1);
  }
  free (newp);
} // END stdorec()

///  Single permutation: 
void perm (char* newp, int start, int pos) {
  char s = newp[start];
  char p = newp[pos];
  newp[start] = p;
  newp[pos] = s;
} // END perm()

///  MAIN: 
int main (int argc,  char *argv[]) {
  if (argc < 2) { 
    fprintf(stderr,"Usage: %s permutation\n\t With a permutation base < 25\n\t Example: ./permord 0123\n", argv[0]); 
    return(0); 
  }
  // Vars:
  Orip =  argv[1]; Psiz = strlen(Orip);
  time_t t1; time_t t2; double tdiff; char tscale = 's';;
  // Time:
  t1 = time(NULL);
  if (Psiz < 2 || Psiz > 24 || Ole > Psiz-1) { 
    fprintf(stderr,"Usage: %s permutation\n\t With a permutation base < 25\n\t Example: ./permord 0123\n", argv[0]); 
    return(0); 
  }
  fprintf(stderr,"Computing permutations of %s .. (Psiz=%d)\n",Orip,Psiz);
  strncpy(Permp,Orip,25);  
  stdoset() ;
  t2 = time(NULL); tdiff = difftime(t2,t1);
  if (tdiff > 3599) {tdiff = tdiff/3600; tscale = 'h'; }
  else if (tdiff > 59) { tdiff = tdiff/60; tscale = 'm'; }
  fprintf(stderr,"%d permutations done in %.2f %c.\n", Scnt,tdiff,tscale);
  return(Scnt);
}  // END main()


/// Example:
/*
$ ./permute 012
Computing permutations of 012 .. (Psiz=3)
012
021
102
120
201
210
6 permutations done in 0.00 s.
*/

//EOF
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s