Proof of Concept: Randomize a list

Well, the idea was essentially that RvS allows up to 30~32 maps or so all stored as a pair of assicated arrays loaded from the servers configuration file. One array that holds the game types (e.g. tango hunt, hostage rescue, misson et. al.) and the other the actual maps to load, i.e. GameType[0]=first maps gametype and Maps[0]=first map to load.


I took a moment the other day (before my gfx card went fuzzy) to write a small program that would generate a new configuration file with a maplist specified from another file, the prototype works fine but I didn't know how I could archive my real goal: randomly populate the maplist from that file.


Here is a proof-of-concept algorithm that takes a list of items and returns a new list containing the same values but sorted into a 'random' order.

#!/usr/bin/env python

import random

def unsort(list, index):
    "return a copy of list reordered randomly"

    new_list = []
    table = []

    while len(new_list) != index:
        r = random.randint(0, index)
        try:
            if r not in table:
                table.append(r)
                new_list.append(list[r])
            else:
                continue
        except IndexError:
            pass
    return new_list

if __name__ == "__main__":
    li = [1,2,3,4,5]
    print unsort(li, len(li))

This took me about 10 minutes of thinking at work today and about 12 or 14 hours later I've made a test script in Python since that is the language I've been using for stuff latly. Basically the problem is the only way to randomly map items from one list into another is if you access elements in the list at random. But if you access a list at a random index and push it into a new list you can get duplicates. So a table (list) is used to store random numbers we have already generated. If the current number is not referenced in the table we can assume that we have not copied the element at that index in the list into the new list, if it does exist we need to try again. One bad thing is the algorithm is designed to run until completion, which can take an arbitrary amount of time to 'unsort' any given set. In theory, it could loop forever! However it would be trivial to modify it to abort the randomization process after a given time frame (such as >N iterations or seconds, which ever comes first) and just append remaining elements onto the end of the new list.

Here is a few test runs:

Terry@Dixie$ ./unsort.py
[3, 5, 4, 1, 2]
Terry@Dixie$ ./unsort.py
[3, 5, 2, 1, 4]
Terry@Dixie$ ./unsort.py
[4, 1, 2, 3, 5]
Terry@Dixie$ ./unsort.py
[5, 4, 1, 2, 3]
Terry@Dixie$ ./unsort.py
[5, 2, 4, 1, 3]
Terry@Dixie$ ./unsort.py
[3, 2, 1, 4, 5]
Terry@Dixie$ ./unsort.py
[4, 5, 3, 2, 1]
Terry@Dixie$

Odds are the PRNG is being seeded with the system time by default or making use of /dev/random on my FreeBSD laptop and that is good enough for me. And these results are random enough for me because I dunno how to write first class pseudo random number generators hehe.