Permutation Question

[foxgrrl]

I'm trying to figure out how long it takes for a particular shuffling algorithm to cycle for a particular number of elements. The algorithm is to count from 1 to M, moving the character at position M mod N (N:=number of elements) to the end, and moving everything down so there's no space. [i.e. (indexed from 1 here) g(1,"ABCDEF")="BCDEFA", then g(2,"BCDEFA")="BDEFAC", then g(3,"BDEFAC")="BDFACE", eventually this will cycle; How long? (30 in this example (That's M).)] I've stumped The On-Line Encyclopedia of Integer Sequences, I want to find f() which generates the following sequence, and I don't want to think about this too hard, and I don't have my Knuth books handy (I think it involves factorials).

What is f()?
f(2) = 2
f(3) = 4
f(4) = 9
f(5) = 20
f(6) = 30
f(7) = 36
f(8) = 28
f(9) = 72
f(10)= 36
f(11)= 280
f(12)= 110
f(13)= 108
f(14)= 182
f(15)= 168
f(16)= 75
f(17)= 1120
f(18)= 306
f(19)= 432
f(20)= 190
f(21)= 140
f(22)= 4410
f(23)= 2772
f(24)= 2530
f(25)= 1440
f(26)= 650
f(27)= 3120
f(28)= 243
f(29)= 812
f(30)= 870
f(31)= 1800
f(32)= 186
f(33)= 1056
f(34)= 10164
f(35)= 1428
f(36)= 2100
f(37)= 35640
f(38)= 1110
f(39)= 14212

Comments

[yetanotherbob.livejournal.com]

Wow. Not even Wolfram Alpha could crack it.

[dv-girl.livejournal.com]

I think this is easy. If first pass is 10 iterations, second is 9, 8, 7 .. 1. Just reverse it.

Time is 1+2+3+4+5 etc. Then it's just the sum of an arithmetic progression.

(1 + N)*(N/2) I think?

[dv-girl.livejournal.com]

Er.. ( (1+N)*(N/2) * T) Where N is number of elements in array and T is the time required to copy the current element off somewhere, then move all the elements down one.

Though if it's a very large list and time is important, I'd use a use a doubly linked list. Then time is constant regardless of size.

cur_ptr=front_ptr; //where front is head of list.


while (cur_ptr && cur_ptr!=back_ptr){
   if (cur_ptr->back!=NULL) //Relink forward pointer of previous element.
   {
      cur_ptr->back->forward = cur_ptr->forward; 
   }
   cur_ptr->forward->back = cur_ptr->back; //Relink back pointer of next element.
   back_ptr->forward = cur_ptr->forward;   //Using as temp variable.
   cur_ptr->back = back_ptr; //Change current element's back pointer to current back of list.
   back_ptr = cur_ptr;  //Move back pointer to point at current element.
   cur_ptr = cur_ptr->back->forward;  //Use our temp variable now to set cur pointer for next loop.
   cur_ptr->back->forward=back_ptr;  //Fix our temp variable to its correct pointing.
   back_ptr->forward=NULL;  //No next element.
}

I believe that's right but it's 5-minute stream of consciousness so check it.

[viesti.livejournal.com]

Where did you find this number sequence? i.e. did it come up at work, or in some other context?

The reason I ask: f(n) = (n-1) * A051732, which is related to shuffling (interlacing in this case) and cycling a deck of size n. I'm curious as to where the extra (n-1) factor comes from. :)

[foxgrrl]

Where did you find this number sequence? i.e. did it come up at work, or in some other context?

I'm critiquing a very poor crypto algorithm. And yeah it does look exactly like f(n) = (n-1) * A051732 which makes sense, since this is a kind of shuffle.

#!/usr/bin/perl
# I'm sure there must be a more clever way to do this in Perl
sub permutate {
   my $offset = shift;
   my $key    = shift;

   $offset = $offset % (length($key)-1);
   my $beginning = substr($key, 0, $offset);
   my $middle    = substr($key, $offset, 1);
   my $end       = substr($key, $offset+1); 
   $key = $beginning . $end . $middle;     
   return $key;                       
}              
      
my $foo = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefg";
$key = "A";
for (my $j=2; $j<40; $j++) {
  $key = substr($foo,0,$j);
  print("offset\tGenerator State\n");
  for (my $i=0; $i < 100 ; $i++) {
     $key = permutate($i,$key);
     printf("%i\t%i\t%s\n",$i,length($key),$key);
  }
}

[viesti.livejournal.com]

Ahhhhh, makes sense now. A051732 is a count of the number of interlaces of the entire string at once. The function above is counting each individual permutate call separately. That would account for the additional factor of (n-1).

Kinda surprised that Wolfram Alpha is not making more direct use of the On-Line Encyclopedia of Integer Sequences as of yet...