Conference rusure::math

#define ndigs 4
main()
{
int choiceptr,permptr,value,weight,tryslot,perm[ndigs],fact,i;

fact = ndigs;

for (i=ndigs-1; i>1; i--) fact *= i;

for (permptr=0; permptr<fact; permptr++)
	{
	value = permptr;
	for (tryslot=0; tryslot<ndigs; tryslot++)
		perm[tryslot] = -1;
	for (weight=ndigs; weight>=1; weight--)
		{
		choiceptr = value % weight;
		value /= weight;
		tryslot = 0;
		while (choiceptr >= 0)
			if (perm[tryslot++] < 0) choiceptr--;
		perm[tryslot-1] = ndigs - weight;
		}
	for (i=0; i<ndigs; i++) printf ("%d",perm[i]);
	printf ("\n");
	}
}

#include <stdio.h>
#define ML 100
int L; char A[ML], B[ML];
main(){
	while(gets(A)){
                for(L=0;L<ML;L++) B[L]='\0'; L=strlen(A); perm(A);
        }
}

perm(S) char *S; {
	int j;
        for(j=0;j<L;j++) if(!B[j]){
                B[j] = *S; if(S[1]) perm(S+1); else puts(B); B[j]='\0';
        }
}

    Note that with unsigned, 32 bit arithmetic, the calculation of "fact"
    in .1 will overflow for ndigs>13.

					Topher

Thank's for all replies, they give me first ideas.

As dan d'eramo mails me, Perhaps some descriptions may help.
The key is more like a seed for a random number generator... 

ie: reading 64 blocks of a file, i would like to create a unique permutation of 
those 64 blocks using the given key. 
	This key may look like 8 acsii digits.
        	f("JHte532j") = <45,63,...,0,10,2,30>
        	f("jhte13e2") = <24,31,...,63,11,21,39>


Thanks for all complements.

        There are various ways you can use an 8 byte ascii key to
        seed a random number generator.  For now, assuming that has
        already been done, one way to compute a random permutation of
        n items is to put them all into a bag and draw them out one by
        one. :-)  In a programming language it is probably easiest to
        pick on of the first n and swap it with the last item; pick
        one of the first n-1 and swap it with the next to the last
        item, etc.  [In randomize_permutation below, at the start of
        each pass through the loop the "bag" is the elements in array
        positions 0...i, and the drawing out of the bag means choosing
        one of those elements and putting it at position i, so that
        the next time through the loop i is one less and that item is
        out of the bag.]
        
        Assuming you are keeping an array of n integers as the
        permutation, you can have C functions like
        
        	void identity_permutation(int *a, int n)
        	{
        	  int i;
        	  int *p;
        
        	  for (i = 0, p = a ; i < n ; i++, p++)
        	    *p = i;
        	}
        
        	void randomize_permutation(int *a, int n)
        	{
        	  int i;
        	  int j;
        	  int temp;
        
        	  for (i = n-1 ; i > 0; i++) {
        	    j = <a random integer in the range {0,...,i}>;
        	    temp = a[i] ; a[i] = a[j] ; a[j] = temp;
        	  }
        	}
        
        Sometimes j may be equal to i, I don't know if this is faster
        for the above loop:
        
        	  for (i = n-1 ; i > 0; i++) {
        	    j = <a random integer in the range {0,...,i}>;
        	    if (j != i) { temp = a[i] ; a[i] = a[j] ; a[j] = temp; }
        	  }
        
        If you have a second array, you can invert the permutation
        with something like
        
        	void invert_permutation(int *a, int *inv, int n)
        	{
        	  int i;
        
        	  for (i = 0 ; i < n ; i++)
        	    inv[a[i]] = i;
        	}
        
        That's in case you later want to use the same key to put the 64
        blocks back into the original order.
        
        If your programming language uses 1...n instead of 0...n-1 for
        n element arrays, then the above needs to be adjusted a little.
        
        Dan

    But this does not assure that each eight byte key will produce a
    different permutation.  I think that the basic technique from .5
    combined with arithmetic coding should allow the key itself to be
    efficiently treated as the random number sequence needed for the algorithm.

    Note, however, that if the "key" is English text you can only figure
    that the eight characters represent somewhere between eight and sixteen
    *bits* of "randomness".

					Topher

    Re .4:
    
    You'll need at least 37 bytes to unique identify one permutation of 64
    objects.  If your key uses only printable standard ASCII characters,
    with codes from 32 to 127, inclusive, you will need 45 characters.  If
    people will be copying and entering these keys, you should attach a
    checksum.
    
    Here is a simple scheme to associate an integer n with a permutation of
    k objects.  Write a recursive function, f(n,k).  Given an integer n and
    a permutation of k objects, this function divides n by k, obtaining
    quotient q and remainder r.  The function then makes the r-th object
    last (or first) and places the remaining k-1 objects in the order
    determined by the function f(q,k-1).  (If k is 1, the function does no
    division, but simply leaves the single object alone.)
    
    
    				-- edp

    I did not have time to add a couple of points to .7:  With 37- or
    45-byte numbers involved, you'll need a way to do extended-precision
    arithmetic.  The conversion from a 45-byte ASCII character string to a
    37-byte number is basically a base conversion; from base 96 to base
    256.
    
    This conversion and extended arithmetic can be avoided at the cost of
    key size.  To select one of 64! permutations, you could use a list of
    numbers, the first from 0 to 63, the next from 0 to 62, et cetera,
    where each number is used to select which object is next in the
    ordering.  An easy way to keep such a list is as 64 bytes.  Some space
    could be saved by packing each number into as few whole bits as
    possible -- 6 bits from the numbers that could be larger than 31, 5
    bits for those that might be larger than 15, et cetera.  That would
    require a total of 321 bits, or 41 bytes or 54 printable ASCII
    characters.
    
    
    				-- edp

Many thank's to all of you.


Bye,
Olivier

>.6 But this does not assure that each eight byte key will produce a
>.6 different permutation.
        
        Hmmm, yes.  If you hash the eight byte ascii key to, say, a
        single four byte integer and use it to seed rand or a similar
        random number generator, then it is likely that some pairs of
        distinct keys will hash to the same seed, thus yielding the
        same permutation.
        
        One would have to use a random number generator which uses
        more than one longword as the state or seed.  These do exist. 
        You'd have to analyze the random number generator to determine
        how to seed it so that different eight byte ascii keys lead to
        different permutations.
        
        Dan
        

   This raises a question I had from a note some years ago... if
   you only want a permutation chosen uniformly randomly from the N!
   possible ones, how close can you come to this with a coset shuffling
   algorithm like Dan posted if the random number generator has much
   less than N! states?

   One thing about permutations that may be interesting in this regard
   is that they fall into equivalence classes, one for each partition
   of the integer N.  Could this be used to analyze if these classes
   are chosesn the expected number of times with your random number
   generator?

   On the other hand, cryptographically strong random number generators
   *based* on permutations, shifts, and xor's exist (such as Merkle's
   Snefru), so in principle you can always have enough state with little
   practical computation cost.

   - Jim