This is a quirky way to shuffle an array, without actually rearranging it. The basic idea is that we shuffle the order of the indices of the array, instead of the items themselves. Then we will iterate through the order of the shuffled indices and use them as an index to get the next item in the array. Without further ado, let’s jump straight into the code.

Algorithm:

We have our array:

array = [5,17,23,1,11,99,37];

First we find its length and we initialize a new array, called order, that will hold the indices of the array, from 0 to n-1.

n = len(array);

order = range(n);

In this case, order is [0,1,2,3,4,5,6].

We want to shuffle the indices in order around.

order = Shuffle(order);

Where Shuffle is a function we will build on our own. First thing in the function, we will get the length of order. Then we will iterate through the indices in the array, and for every index we will pick a random index and we will swap them in place.

def Shuffle(order):
        n = len(order);

       for i in range(n):
               r = randint(0,n-1);

               order[i], order[r] = order[r], order[i];

Where r is the random index to swap with. To use randint we will need to import it from the random library.

from random import randint;

With the function done, we can return to our main code. We just shuffled order. What we do next depends on the program we want to make. The general idea is that we will iterate through the indices in order and use the iterated index to get an item from the array.

For the purpose for this tutorial, say we want to simply print the numbers in the array in a random order. We write this:

for i in range(n):
        index = order[i];
        print array[index];

Instead of the print command, you can use the array item as you wish.

Conclusion

This algorithm can be used in mainly two cases:

1) The items in array are large and would be costly (time wise) to swap around.
2) You want the initial array to remain intact, without duplicating (because it might be costly, memory wise).

The complete code:

from random import randint;

def Shuffle(order):
    n = len(order);

    #Iterate through all indices in order
    for i in range(n):
        #Pick random index
        r = randint(0,n-1);

        #Swap iterated index and random index
        order[i], order[r] = order[r], order[i];

    return order;


array = [5,17,23,1,11,99,37];

#Length of the array
n = len(array);

#Initialize order of indices
order = range(n);
order = Shuffle(order);

#Print array in new order
for i in range(n):
    index = order[i];
    print array[index];
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s