Shuffling arrays question
02-28-2015, 10:42 PM
Post: #1
 Namir Senior Member Posts: 822 Joined: Dec 2013
Shuffling arrays question
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
02-28-2015, 11:55 PM (This post was last modified: 03-01-2015 03:33 AM by Mark Hardman.)
Post: #2
 Mark Hardman Senior Member Posts: 525 Joined: Dec 2013
RE: Shuffling arrays question
(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.

Ceci n'est pas une signature.
03-01-2015, 12:42 AM
Post: #3
 Paul Dale Senior Member Posts: 1,748 Joined: Dec 2013
RE: Shuffling arrays question
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
03-01-2015, 01:10 PM (This post was last modified: 03-01-2015 01:13 PM by Namir.)
Post: #4
 Namir Senior Member Posts: 822 Joined: Dec 2013
RE: Shuffling arrays question
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
03-01-2015, 06:48 PM (This post was last modified: 03-01-2015 10:17 PM by Namir.)
Post: #5
 Namir Senior Member Posts: 822 Joined: Dec 2013
RE: Shuffling arrays question
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
03-07-2015, 05:56 AM
Post: #6
 BruceH Senior Member Posts: 382 Joined: Dec 2013
RE: Shuffling arrays question
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.)
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)