Shuffling arrays question

[Namir]

Does anyone know of an algorithm to shuffle an array of integers WITHOUT USING RANDOM NUMBER FUNCTIONS? I discovered a good (not the best) method for generating random numbers is that you start with an array of n elements (with values from 1 to n), shuffle the elements of that array and then divide each array element by n+1. You get a good set of random numbers. I can do the shuffling using random number functions, like randperm in Matlab. I am looking for a way to shuffle the array (initially in ascending or descending order) using clever swaps of elements. I am basically looking to transform perfect order into as perfect chaos as possible!

Namir

[Mark Hardman]

(02-28-2015 10:42 PM)Namir Wrote:  Does anyone know of an algorithm to shuffle an array of integers WITHOUT USING RANDOM NUMBER FUNCTIONS? I discovered a good (not the best) method for generating random numbers is that you start with an array of n elements (with values from 1 to n), shuffle the elements of that array and then divide each array element by n+1. You get a good set of random numbers. I can do the shuffling using random number functions, like randperm in Matlab. I am looking for a way to shuffle the array (initially in ascending or descending order) using clever swaps of elements. I am basically looking to transform perfect order into as perfect chaos as possible!

Namir

You might be able to get a random order using a perfect shuffle:

The Mathematics of Perfect Shuffles

Thank you for your continued efforts in pushing the limits of randomization. Fascinating stuff.

[Paul Dale]

You are looking for a permutation that appears "random". I'd try looking at permutation ciphers first.

There are methods to generate all permutations of a set, you might be able to pick one of these based on n e.g. let p = floor(n/3) and run the algorithm p times from the initial state. Check out algorithm L.


- Pauli

[Namir]

I was able to write the following un-sort function in Matlab. It does well in scrambling an ordered array. The function primes(m) returns an array of primes from 2 to m (or under it):

Code:

function x=unsort(x)
  n=length(x);
  m=fix(n/2);
  primeArr=primes(m);
  for j=1:195
    for k=1:length(primeArr)
      aprime=primeArr(k);
      for i=1:aprime:n-aprime
        t=x(i);
        x(i)=x(i+aprime);
        x(i+aprime)=t;
      end
    end
  end
end

The number 195 is optimum for sorting an array of 100000 integers in Matlab. While the above code is free of using random number generating functions or code, I feel that the effort needed to scramble an array is not minimal.

Namir

[Namir]

I am working on an array-shuffling algorithm that divides the array into ten "buckets". The method then merges two neighboring or distant buckets, shuffles them, and then copy the shuffled elements back to their original buckets. So far, I am able to get more randomness than the algorithm I posted earlier.

Here is the Matlab code. You can find this code integrated with a more comprehensive Matlab function in the part 3 article in my web site.

Code:

function x=unsort(x)
  N=length(x);
  delta=10;
  n=fix(N/delta);
  spacing=fix(delta)/2:-1:1;  
  for j=1:7
    for k=1:length(spacing)
      spc=spacing(k);
      for i=1:delta-1
        i1=1+(i-1)*n;
        i2=i1+n-1;
        i3=i1+spc*n;
        i4=i3+n-1;
        if i4>N, break; end
        if i1~=i3
          y=[x(i1:i2),x(i3:i4)];
          y=shuffle(y);
          x(i1:i2)=y(1:n);
          x(i3:i4)=y(n+1:2*n);
        end
      end
    end
  end
  %plot(x)
end

function x=shuffle(x)
  n=length(x);
  m=fix(n/2);
  primeArr=[1,primes(m)];
  for j=1:14
    for k=1:length(primeArr)
      aprime=primeArr(k);
      for i=1:aprime:n-aprime
        t=x(i);
        x(i)=x(i+aprime);
        x(i+aprime)=t;
      end
    end
  end
end

[BruceH]

http://en.wikipedia.org/wiki/Linear_feed...t_register

Is this what you are looking for? (Statistically random sequence, but the same sequence every time.)