Psychochild's Blog

A developer's musings on game development and writing.

3 February, 2006

Python randomness
Filed under: — Psychochild @ 9:06 PM

In a previous blog entry I discussed a random number generator without replacement. I recently wrote a Python version of the RandomOdds class I thought some people might find interesting.

Read on for the code and a few comments.

This code is a bit different than the C++ code I provided previously. Given the flexibility of Python lists, I have the class randomly return an element from the list. You can choose to either pass in your own list, or you can have boolean variables returned similar to the C++ code. (The boolean option just constructs a list of boolean values to select from randomly.)

By default, Python uses the Mersenne Twister method to generate random numbers, so the random numbers generated should be nice and random.

Overall, this code is much more flexible. For example you could more easily do dice rolls. A call to

ro = RandomOdds(range(1,21))

would give the results of rolling a 20-sided die (1d20) without replacement. If you want it to feel a bit more random (while still being fair) you could multiply the range object a few times like such as

ro = RandomOdds(range(1,21)*5)

This code has been created with readability and maintainability as the highest priorities. There are probably some optimizations that could be made for execution efficiency, I’m sure.

Without further ado, here’s the code. Once again, this is released under a BSD-style license which boils down to: use it however you want, just give me credit as appropriate.


# RandomOdds: Returns elements of a list randomly without replacement.
#
# Copyright (C) 2006, Brian 'Psychochild' Green
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
#   1. Redistributions of source code must retain the above copyright
#      notice, this list of conditions and the following disclaimer.
#
#   2. Redistributions in binary form must reproduce the above copyright
#      notice, this list of conditions and the following disclaimer in the
#      documentation and/or other materials provided with the distribution.
#
#   3. The names of its contributors may not be used to endorse or promote
#      products derived from this software without specific prior written
#      permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
# OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

import random
import types

class RandomOdds:
    """
    Returns a random value based on what is passed in.  Does random results
    without replacement, in mathematical terms.
    """

    # Initialization
    def __init__(self, oddsList=None):
        # Keep track of the full list we want.
        self.mOddsList = []
        # Keeps track of value we haven't returned yet.
        self.mListLeft = []
        if oddsList == None or not self.SetOdds(oddsList):
            # Something went wrong, set to default 50/50 boolean return.
            self.SetOdds([True, False])

    # SetBoolOdds - Set boolean odds for the object.  This creates a list of
    #               boolean values which we return as normal.
    # params: successes = the number of successes we want.
    #         outof = maximum number of rolls required to get the number of
    #                 successes.
    # return: True if new odds are set.  False otherwise.
    # Side effect: The status is reset.
    def SetBoolOdds(self, successes, outof):
        if successes > outof or successes < 0 or outof < 0:
            # Probably a mistake, don't change anything.
            return False
        accumulator = 1
        oddsList = []
        while accumulator <= outof:
            if accumulator <= successes:
                oddsList += [True]
            else:
                oddsList += [False]
            accumulator += 1
        return self.SetOdds(oddsList)

    # SetOdds - Set the odds list for the object.  This function takes a list
    #           of values, verifies that it's a list, then shuffles it.  Each
    #           subsequent call to GetChance returns one of the list.
    # params: oddsList = a list of values we want returned.
    # return: True if new odds are set.  False otherwise.
    # Side effect: The status is reset.
    def SetOdds(self, oddsList):
        if (type(oddsList) is not types.ListType) or len(oddsList) <= 0:
            # Not a populated list, don't change anything.
            return False
        self.mOddsList = oddsList
        self.ResetState()
        return True

    # ResetState - Reset the odds back to the original state.
    def ResetState(self):
        # Set mListLeft to a copy of mOddsList.
        self.mListLeft = self.mOddsList[0:]

    # GetChance - Returns a value, depending on what we set it to be.
    #             Caller is responsible for handling the value properly.
    def GetChance(self):
        # Select a value.
        retIndex = random.randrange(len(self.mListLeft))
        retVal = self.mListLeft[retIndex]

        del self.mListLeft[retIndex]
        # Do we need to restart?
        if len(self.mListLeft) <= 0:
            self.ResetState()
        return retVal






2 Comments »

  1. I don’t shuffle the list, I pick a random index. From the GetChance() method:

    retIndex = random.randrange(len(self.mListLeft))
    This picks a random number from 0 to the length of the list – 1. So, if you have 5 elements left in the list, it picks a number from 0 to 4. This is the index of the selected item in the list.

    retVal = self.mListLeft[retIndex]
    This actually selects the element for the index we randomly picked in the previous statement so we can return the value.

    del self.mListLeft[retIndex]
    This deletes the element we selected out of the list so it won’t be picked again.

    I thought this was a bit cleaner than shuffling the list when you got it. But, you could change it easily if you knew Python.

    Hope that clarifies. :)

    Comment by Psychochild — 4 February, 2006 @ 12:34 AM

  2. Oh, okay. I don’t know Python itself, so I was just comparing the comments to the code, and got a bit confused at that point.

    Efficiency-wise, the one big thing I see is that you have a list of all the elements. You could just kept track of the counts of each different element type, and this would greatly reduce the amount of space needed, especially in the binomial case.

    For example, if you had 600 balls, and they were either red or blue (50% chance), you’d have a list with 600 elements ([red, red, red,..., blue, blue, blue...]. Or you could have a list [red, blue] with values [300, 300]. When you get an element simply decrement its count. You’ll have gone from nm elements in the list to 2n elements.

    Comment by Rohan Verghese — 4 February, 2006 @ 5:55 PM

Leave a comment

I value your comment and think the discussions are the best part of this blog. However, there's this scourge called comment spam, so I choose to moderate comments rather than giving filthy spammers any advantage.

If this is your first comment, it will be held for moderation and therefore will not show up immediately. I will approve your comment when I can, usually within a day. Comments should eventually be approved if not spam. If your comment doesn't show up and it wasn't spam, send me an email as the spam catchers might have caught it by accident.

Line and paragraph breaks automatic, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Email Subscription

Get posts by email:


Recent Comments

Categories

Search the Blog

Calendar

July 2019
S M T W T F S
« Nov    
 123456
78910111213
14151617181920
21222324252627
28293031  

Meta

Archives

Standard Disclaimer

I speak only for myself, not for any company.

My Book





Information

Around the Internet

Game and Online Developers

Game News Sites

Game Ranters and Discussion

Help for Businesses

Other Fun Stuff

Quiet (aka Dead) Sites

Posts Copyright Brian Green, aka Psychochild. Comments belong to their authors.

Support me and my work on