#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	ReadMe
#	Makefile
#	cc.h
#	random.c
#	scrambled.c
#	difficult.c
#	permutation.h
#	permutation.c
# This archive created: Fri Jan 27 18:16:26 1995
export PATH; PATH=/bin:$PATH
echo shar: extracting "'ReadMe'" '(674 characters)'
if test -f 'ReadMe'
then
	echo shar: will not over-write existing file "'ReadMe'"
else
sed 's/^	X//' << \SHAR_EOF > 'ReadMe'
	XThis directory contains the following generators of signed permutations.
	X
	X	random n m
	X
	X                Generate m signed permutations with n elements, uniformly
	X                at random.
	X
	X        scrambled n k m
	X
	X                Generator m signed permutations with n elements.
	X                Each permutation is generated by scrambling the identity
	X                permutation with k random reversals, where the intervals
	X                of the reversals are chosen uniformly at random.
	X
	X        difficult n
	X
	X                Generate a signed permutation on n elements guaranteed to
	X                require n - 1 reversals.
	X
	XExecute "make" to compile all the generators.
SHAR_EOF
if test 674 -ne "`wc -c < 'ReadMe'`"
then
	echo shar: error transmitting "'ReadMe'" '(should have been 674 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'Makefile'" '(786 characters)'
if test -f 'Makefile'
then
	echo shar: will not over-write existing file "'Makefile'"
else
sed 's/^	X//' << \SHAR_EOF > 'Makefile'
	XSHAR = shar -a
	XRM = rm -i
	X
	XCFLAGS = -O
	X
	X# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	X
	Xall : random scrambled difficult
	X
	X# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	X
	Xrandom : random.o permutation.o
	X	${CC} ${CFLAGS} -o random random.o permutation.o
	X
	Xscrambled : scrambled.o permutation.o
	X	${CC} ${CFLAGS} -o scrambled scrambled.o permutation.o
	X
	Xdifficult : difficult.o
	X	${CC} ${CFLAGS} -o difficult difficult.o
	X
	Xrandom.o scrambled.o permutation.o : permutation.h
	X
	X# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	X
	Xclean:
	X	${RM} random.o scrambled.o difficult.o permutation.o
	X
	Xshar:
	X	${SHAR} ReadMe Makefile cc.h \
	X	random.c scrambled.c difficult.c permutation.h permutation.c \
	X	> Shar
SHAR_EOF
if test 786 -ne "`wc -c < 'Makefile'`"
then
	echo shar: error transmitting "'Makefile'" '(should have been 786 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'cc.h'" '(787 characters)'
if test -f 'cc.h'
then
	echo shar: will not over-write existing file "'cc.h'"
else
sed 's/^	X//' << \SHAR_EOF > 'cc.h'
	X/*
	X * cc.h -- C definitions
	X */
	X
	X/*
	X * Copyright (c) 1989 by John Kececioglu.  All rights reserved.
	X */
	X
	X
	X#ifndef CcInclude
	X#define CcInclude
	X
	X
	X#undef Ansi
	X  /*
	X   * Should not be defined if the compiler does not support the ANSI standard
	X   */
	X
	X
	X/*
	X * Argument lists for function prototypes
	X */
	X#ifdef Ansi
	X#define Proto(Arguments) Arguments
	X#else
	X#define Proto(Arguments) ()
	X#endif
	X
	X
	X/*
	X * Void data type
	X */
	X#ifdef Ansi
	Xtypedef void Void;
	X#else
	Xtypedef int Void;
	X#endif
	X
	X
	X/*
	X * Generic pointer data type
	X */
	X#ifdef Ansi
	Xtypedef void *Pointer;
	X#else
	Xtypedef char *Pointer;
	X#endif
	X
	X
	X/*
	X * Dynamic memory allocation
	X */
	X#define Allocate(Bytes) malloc(Bytes)
	X#define Free(Memory)    free((Pointer) (Memory))
	X
	X
	X/*
	X * Exiting the program
	X */
	X#define Halt() exit(1)
	X
	X
	X#endif /* CcInclude */
SHAR_EOF
if test 787 -ne "`wc -c < 'cc.h'`"
then
	echo shar: error transmitting "'cc.h'" '(should have been 787 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'random.c'" '(634 characters)'
if test -f 'random.c'
then
	echo shar: will not over-write existing file "'random.c'"
else
sed 's/^	X//' << \SHAR_EOF > 'random.c'
	X#include <stdio.h>
	X#include "permutation.h"
	X
	X
	X#define Usage "random <size of permutation> <number of permutations>"
	X   
	X   
	XVoid main
	X
	X#ifdef Ansi
	X   (int argc, char *argv[])
	X#else
	X   (argc, argv) int argc; char *argv[];
	X#endif
	X
	X{
	X   register int i, j;
	X   register int *Perm, Size, Sample;
	X   
	X   Size = atoi(argv[1]);
	X   Sample = atoi(argv[2]);
	X   
	X   Perm = (int *) Allocate(Size * sizeof(int));
	X   Perm -= 1;
	X   
	X   Randomize();
	X   for (i = 1; i <= Sample; i++)
	X   {
	X      RandomPermutation(Perm, Size);
	X      for (j = 1; j <= Size; j++)
	X         printf("%d ", Perm[j]);
	X      printf("\n");
	X   }
	X   
	X   Perm += 1;
	X   Free(Perm);
	X}
SHAR_EOF
if test 634 -ne "`wc -c < 'random.c'`"
then
	echo shar: error transmitting "'random.c'" '(should have been 634 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'scrambled.c'" '(696 characters)'
if test -f 'scrambled.c'
then
	echo shar: will not over-write existing file "'scrambled.c'"
else
sed 's/^	X//' << \SHAR_EOF > 'scrambled.c'
	X#include <stdio.h>
	X#include "permutation.h"
	X
	X
	X#define Usage "scrambled <size> <reversals> <number>"
	X   
	X   
	XVoid main
	X
	X#ifdef Ansi
	X   (int argc, char *argv[])
	X#else
	X   (argc, argv) int argc; char *argv[];
	X#endif
	X
	X{
	X   register int i, j;
	X   register int *Perm, Size;
	X   auto     int Sample, Reversals;
	X   
	X   Size = atoi(argv[1]);
	X   Reversals = atoi(argv[2]);
	X   Sample = atoi(argv[3]);
	X   
	X   Perm = (int *) Allocate(Size * sizeof(int));
	X   Perm -= 1;
	X   
	X   Randomize();
	X   for (i = 1; i <= Sample; i++)
	X   {
	X      RandomlyReversedPermutation(Perm, Size, Reversals);
	X      for (j = 1; j <= Size; j++)
	X         printf("%d ", Perm[j]);
	X      printf("\n");
	X   }
	X   
	X   Perm += 1;
	X   Free(Perm);
	X}
SHAR_EOF
if test 696 -ne "`wc -c < 'scrambled.c'`"
then
	echo shar: error transmitting "'scrambled.c'" '(should have been 696 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'difficult.c'" '(1187 characters)'
if test -f 'difficult.c'
then
	echo shar: will not over-write existing file "'difficult.c'"
else
sed 's/^	X//' << \SHAR_EOF > 'difficult.c'
	X#include <stdio.h>
	X#include "cc.h"
	X
	X
	X#define Usage "difficult <size of permutation>"
	X   
	X   
	Xstatic Void Difficult Proto(( int *Perm, int Size ));
	X
	X   
	XVoid main
	X
	X#ifdef Ansi
	X   (int argc, char *argv[])
	X#else
	X   (argc, argv) int argc; char *argv[];
	X#endif
	X
	X{
	X   int *Perm, Size;
	X   int i;
	X   
	X   
	X   Size = atoi(argv[1]);
	X   
	X   Perm = (int *) Allocate(Size * sizeof(int));
	X   Perm -= 1;
	X   
	X   Difficult(Perm, Size);
	X   
	X   for (i = 1; i <= Size; i++)
	X      printf("%d ", Perm[i]);
	X   printf("\n");
	X   
	X   Perm += 1;
	X   Free(Perm);
	X}
	X
	X
	X/*
	X * Difficult -- Return a difficult permutation of a given size
	X *
	X * The permutation is guaranteed to require n - 1 reversals.
	X *
	X */
	Xstatic Void Difficult
	X
	X#ifdef Ansi
	X   (register int *Perm, register int Size)
	X#else
	X   (Perm, Size) register int *Perm, Size;
	X#endif
	X
	X{
	X   register int i;
	X   
	X   if (Size <= 0)
	X      return;
	X   else if (Size % 2 == 1)
	X   {
	X      for (i = 1; i <= Size; i++)
	X         Perm[i] = Size - i + 1;
	X   }
	X   else
	X   {
	X      for (i = 1; i <= Size / 2; i++)
	X         Perm[i] = -(Size - 2 * (i - 1));
	X      for (i = (Size / 2) + 1; i <= Size - 1; i++)
	X         Perm[i] = 2 * (i - (Size / 2)) + 1;
	X      Perm[Size] = 1;
	X   }
	X}
SHAR_EOF
if test 1187 -ne "`wc -c < 'difficult.c'`"
then
	echo shar: error transmitting "'difficult.c'" '(should have been 1187 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'permutation.h'" '(667 characters)'
if test -f 'permutation.h'
then
	echo shar: will not over-write existing file "'permutation.h'"
else
sed 's/^	X//' << \SHAR_EOF > 'permutation.h'
	X/*
	X * permutation.h -- Definitions for permutation generators
	X */
	X
	X
	X#ifndef PermutationInclude
	X#define PermutationInclude
	X
	X
	X#include "cc.h"
	X
	X
	Xtypedef struct {
	X   int   Size;
	X   int   *Permutation;
	X   int   *Inverse;
	X   int   *Output;
	X   short *Direction;
	X} Permuter;
	X
	X
	Xextern Permuter *CreatePermuter
	X   Proto(( int Size ));
	Xextern Void DestroyPermuter
	X   Proto(( Permuter *P ));
	Xextern int *NextPermutation
	X   Proto(( Permuter *P ));
	X
	Xextern Void Randomize
	X   Proto(( Void ));
	Xextern Void RandomPermutation
	X   Proto(( int *Perm, int Size ));
	Xextern Void RandomlyReversedPermutation
	X   Proto(( int *Perm, int Size, int Reversals ));
	X
	X
	X#endif /* PermutationInclude */
SHAR_EOF
if test 667 -ne "`wc -c < 'permutation.h'`"
then
	echo shar: error transmitting "'permutation.h'" '(should have been 667 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'permutation.c'" '(5921 characters)'
if test -f 'permutation.c'
then
	echo shar: will not over-write existing file "'permutation.c'"
else
sed 's/^	X//' << \SHAR_EOF > 'permutation.c'
	X/*
	X * permutation.c -- Permutation generators
	X */
	X
	X
	X#include <stdio.h>
	X#include "permutation.h"
	X
	X
	X/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	X *
	X * Permutation enumeration
	X */
	X   
	X   
	X/*
	X * CreatePermuter -- Create a permutation enumerator
	X *
	X */
	XPermuter *CreatePermuter
	X
	X#ifdef Ansi
	X   (int Size)
	X#else
	X   (Size) int Size;
	X#endif
	X
	X{
	X   register Permuter *P;
	X   register int i, n;
	X
	X   
	X   /*
	X    * Allocate the generator
	X    */
	X   P = (Permuter *) Allocate(sizeof(Permuter));
	X   if (P == NULL)
	X   {
	X      fprintf(stderr, "(CreatePermuter) Memory allocation failed.\n");
	X      exit(1);
	X   }
	X   P->Output = (int *) Allocate(Size * sizeof(int));
	X   P->Permutation = (int *) Allocate((Size + 2) * sizeof(int));
	X   P->Inverse = (int *) Allocate((Size + 2) * sizeof(int));
	X   P->Direction = (short *) Allocate((Size + 2) * sizeof(short));
	X   if (P->Output == NULL || P->Permutation == NULL || P->Inverse == NULL ||
	X       P->Direction == NULL)
	X   {
	X      fprintf(stderr, "(CreatePermuter) Memory allocation failed.\n");
	X      exit(1);
	X   }
	X   
	X   /*
	X    * Initialize the generator
	X    */
	X   P->Size = Size;
	X   P->Permutation[0] = Size + 1;
	X   P->Inverse[0] = 0;
	X   P->Direction[0] = 0;
	X   for (i = 1; i <= Size; i++)
	X   {
	X      P->Permutation[i] = i;
	X      P->Inverse[i] = i;
	X      P->Direction[i] = -1;
	X   }
	X   P->Permutation[Size + 1] = Size + 1;
	X   P->Direction[Size + 1] = 0;
	X   P->Inverse[Size + 1] = Size + 1;
	X   
	X   /*
	X    * Return the generator
	X    */
	X   return P;
	X}
	X
	X
	X/*
	X * DestroyPermuter -- Destroy a permutation enumerator
	X *
	X */
	XVoid DestroyPermuter
	X
	X#ifdef Ansi
	X   (register Permuter *P)
	X#else
	X   (P) register Permuter *P;
	X#endif
	X
	X{
	X   Free(P->Output);
	X   Free(P->Permutation);
	X   Free(P->Inverse);
	X   Free(P->Direction);
	X   Free(P);
	X}
	X
	X
	X#define Active(P) ((P)->Direction[1] == -1)
	X
	X
	X/*
	X * NextPermutation -- Generate the next permutation
	X *
	X * `NextPermutation' returns a pointer to an array containing the permutation.
	X * This array is reused on subsequent calls.
	X *
	X * Successive permutations differ by a single transposition of adjacent
	X * elements.  See Reingold, Nievergelt, and Deo, Combinatorial Algorithms:
	X * Theory and Practice, Prentice-Hall, 1977, 168-170.
	X *
	X */
	Xint *NextPermutation
	X
	X#ifdef Ansi
	X   (register Permuter *P)
	X#else
	X   (P) register Permuter *P;
	X#endif
	X
	X{
	X   register int i, j, m, n;
	X   
	X   if (Active(P))
	X   {
	X      /*
	X       * Form the permutation
	X       */
	X      for (i = 1, n = P->Size; i <= n; i++)
	X         P->Output[i - 1] = P->Permutation[i];
	X      
	X      /*
	X       * Find the active index
	X       */
	X      m = n;
	X      i = P->Inverse[m];
	X      j = i + P->Direction[m];
	X      while (P->Permutation[j] > m && m > 0)
	X      {
	X         P->Direction[m] = - P->Direction[m];
	X         m -= 1;
	X         i = P->Inverse[m];
	X         j = i + P->Direction[m];
	X      }
	X      
	X      /*
	X       * Transpose the active index
	X       */
	X      P->Permutation[i] = P->Permutation[j];
	X      P->Permutation[j] = m;
	X      P->Inverse[P->Permutation[i]] = i;
	X      P->Inverse[m] = j;
	X      
	X      return P->Output - 1;
	X   }
	X   else
	X   {
	X      /*
	X       * Reinitialize the generator
	X       */
	X      for (i = 1, n = P->Size; i <= n; i++)
	X      {
	X         P->Permutation[i] = P->Inverse[i] = i;
	X         P->Direction[i] = -1;
	X      }
	X      
	X      return 0;
	X   }
	X}
	X
	X
	X/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	X *
	X * Random permutations
	X */ 
	X
	X
	X/*
	X * Randomize -- Initialize the random number generator
	X *
	X */
	XVoid Randomize
	X
	X#ifdef Ansi
	X   (Void)
	X#else
	X   ()
	X#endif
	X
	X{
	X   srandom(1);
	X}
	X
	X
	X/*
	X * RandomInteger -- Return a random integer in the range 1 to n
	X *
	X */
	Xstatic int RandomInteger
	X
	X#ifdef Ansi
	X   (register int n)
	X#else
	X   (n) register int n;
	X#endif
	X
	X{
	X   return 1 + (random() % n);
	X}
	X
	X
	X/*
	X * RandomPermutation -- Return a random permutation
	X *
	X * `RandomPermutation' assumes `Perm' points to an allocated array.
	X *
	X */
	XVoid RandomPermutation
	X
	X#ifdef Ansi
	X   (register int *Perm, register int Size)
	X#else
	X   (Perm, Size) register int *Perm, Size;
	X#endif
	X
	X{
	X   register int X;
	X   register int i, k;
	X   
	X   /*
	X    * Initialize a set to the elements {1, 2, ..., Size}
	X    */
	X   for (i = 1; i <= Size; i++)
	X      Perm[i] = i;
	X   
	X   /*
	X    * Select the elements in a random order
	X    */
	X   for (i = 1; i <= Size; i++)
	X   {
	X      /*
	X       * Choose a random element from those remaining in the set
	X       */
	X      k = RandomInteger(Size - i + 1);
	X      
	X      /*
	X       * Remove the chosen element from the set
	X       */
	X      X = Perm[Size - i + 1];
	X      Perm[Size - i + 1] = Perm[k];
	X      Perm[k] = X;
	X
	X      /*
	X       * Give the element a random sign
	X       */
	X      if (RandomInteger(2) == 1)
	X         Perm[Size - i + 1] *= -1;
	X   }
	X}
	X
	X
	X/*
	X * RandomlyReversedPermutation -- Return a permutation obtained by applying
	X *                                random reversals to the identity permutation
	X *
	X * `RandomlyReversedPermutation' assumes `Perm' points to an allocated array.
	X *
	X */
	XVoid RandomlyReversedPermutation
	X
	X#ifdef Ansi
	X   (register int *Perm, register int Size, register int Reversals)
	X#else
	X   (Perm, Size, Reversals) register int *Perm, Size, Reversals;
	X#endif
	X
	X{
	X   auto     int left, right;
	X   register int a, b, i;
	X   register int p, q, x;
	X   
	X   /*
	X    * Initialize to the identity permutation
	X    */
	X   for (i = 1; i <= Size; i++)
	X      Perm[i] = i;
	X   
	X   /*
	X    * Apply random reversals
	X    */
	X   for (i = 1; i <= Reversals; i++)
	X   {
	X      /*
	X       * Randomly choose an interval
	X       */
	X      a = RandomInteger(Size - 1) + 1;
	X      b = RandomInteger(Size - 1) + 1;
	X      if (a <= b)
	X      {
	X         left = a;
	X         right = b;
	X      }
	X      else
	X      {
	X         left = b;
	X         right = a;
	X      }
	X      
	X      /*
	X       * Reverse the interval
	X       */
	X      for (p = left, q = right; p <= q; p++, q--)
	X      {
	X         x = Perm[p];
	X         Perm[p] = -Perm[q];
	X         Perm[q] = -x;
	X      }
	X   }
	X}
SHAR_EOF
if test 5921 -ne "`wc -c < 'permutation.c'`"
then
	echo shar: error transmitting "'permutation.c'" '(should have been 5921 characters)'
fi
fi # end of overwriting check
#	End of shell archive
exit 0


