Re: looking for random array reshuffling algorithm

From: Rick D. (nomail_at_mail.com)
Date: 03/20/05 

Date: Sun, 20 Mar 2005 23:45:54 +0100

On Sun, 20 Mar 2005 21:20:40 +0000 (UTC), Willem <willem@stack.nl>
wrote:

-snip-

>) Yes, i'm looking for a fast algorithm that can generate n+1,n+2,..
>) based on n and reverse it back to n (1 step at a time) and is as
>) chaotic as possible and has a very big cycle period.
>
>A few facts about applying the same permutation over and over again:
>
>- A permutation can be subdivided into a number of cycles.
>- The period of the permutation is the least common multiple
> of the sizes of each of those cycles.
>
>So, to get the largest possible period, you have to find a set
>of numbers that sums to twenty, and has the largest possible LCM.
>
>Here's the best I can do: 3 * 4 * 5 * 7 = 420
>
>Given that you cited a period of around 60000, I don't think you
>meant applying the same permutation over and over again.

Right now i use a sequence of pre-defined functions (permutations) to
transform/regroup the array from state n to n+1. The last function in
the sequence uses a 1024 * 1-bit fixed random seed to add chaos to the
process and boost the cycle, because as you mentioned, just using
straight permutations produces small cycles. Each seed produces a
different cycle, ranging from 2500 up to 60000 so far.

But i'm sure there are better, simpler and faster solutions to do
this. I've jus not been able to find one yet.

Best regards,
Rick

Relevant Pages

  • Re: "Interleave" permutation algorithm?
    ... So what would be a good in-place algorithm for this permutation? ... (defun interleave (vector) ... processing the vector cycle by cycle and avoiding storing moving ... (defun iota (count &optional start step) ...
    (comp.programming)
  • Re: Rearranging based on permutation of indices
    ... When you have a permutation, you can see it as a bunch of disjoint ... (loop; this loop returns the minimum i ... was in the permutation of the cycle. ... (defun permute-cycle (vector permutation cycle) ...
    (comp.programming)
  • Re: Expected average cycle length...
    ... > in a random permutation of N elements, all N cycle lengths are ... Using the first definition, for the case of S4, you get 1.92. ... To me, the second definition seems more reasonable, since we want to know ...
    (sci.crypt)
  • Re: Expected average cycle length...
    ... > random permutation of the M-bit vectors, ... > cycle lengths are equally likely. ... First, only one permutation has ... the expected cycle length on 4 elements is 2.875. ...
    (sci.crypt)
  • Re: Proof of Collatz Conjecture?
    ... sequence Cn has a length-3 cycle because there is always one ... any sequence or the cycle. ... print 'PART II: Count legal sequences using partition generator:' ...
    (sci.math)
Loading