Inept question about probability

[AgingMinotaur]

EDIT: some crude testing suggests that my code works just as it should. Sometimes it's better to think things over twice before posting for help. Ah, well ...

Sometimes I'm feeling very stupid. Like ... just about now. Someone with a clearer mind should be able to help me out with this one.

I'm reworking the parts of my code that picks a random element from a set (of monsters, or items, or something else). First, the possible choices are put in a python dictionary, where the key is the name/identifier of the element, and the value is the relative probability of that element showing up. Something like this, in other words: {'sword':1, 'croquet club':2, 'knife and fork':4} In this example, croquet clubs should be twice as probable as swords, and cutlery four times as probable. Here's what I'm uncertain about:

Code: [Select]

def draw_lot(pd): # pd is the dictionary of stuff
    full_prob=reduce(lambda x,y : x+y, pd.itervalues()) # adds all values,
            # ie. sets full_prob to 7 in the example with the weapons
        choice=random.randint(1,full_prob) # a number between 1 and full_prob
        while 1:
            k=pd.popitem() # pops a random key+value from the pd dictionary
            if k[1]>=choice: # k[1] is the value, ie. 1, 2, or 4
                return k[0] # returns name of picked item
            else:
                choice-=k[1]

This works pretty fast, but I'm unsure as to whether it produces the intended effect. Will it actually return clubs twice as often as swords, and cutlery twice as often as clubs? I feel like I've a short circuit here somewhere, but I can't wrap my mind around it. So, any help regarding this would be appreciated.

As always,
Minotauros

[corremn]

wow, where did you come up with that scheme?

I did something simular but mine is somewhat more basic. 
I have a list that I add things to multiple times, depending on its probablility.  I.e 'sword' will be added once, 'knife and fork' will be added 4 times.  Then I randomly choose an integer between 0 and size-1 of the list.
Then I select element at that place.

This works well if you know what is going in the list.  Before you add something you have to remember what is already in the list so you can set the probability correct.  But I guess all schemes have that problem.

[Ex]

wow, where did you come up with that scheme?

I did something simular but mine is somewhat more basic. 
I have a list that I add things to multiple times, depending on its probablility.  I.e 'sword' will be added once, 'knife and fork' will be added 4 times.  Then I randomly choose an integer between 0 and size-1 of the list.
Then I select element at that place.

This works well if you know what is going in the list.  Before you add something you have to remember what is already in the list so you can set the probability correct.  But I guess all schemes have that problem.

You can do this with math, too. For instance, sword=1 knife=2 spoon=4, we can add together sword+knife+spoon and then pick a random number between 0 and this number. Then, 0 would be the sword, 1-2 the knife and 3-7 the spoon. If spoon+knife<what we picked, it must be sword. If spoon<what we picked and if spoon+knife>what we picked, it must be the knife, and so on.

But, I'd probably just use a list that gets added to multiple times, because that's easy

[AgingMinotaur]

wow, where did you come up with that scheme?

I guess I'm just a natural

I did something simular but mine is somewhat more basic. 
I have a list that I add things to multiple times, depending on its probablility.  I.e 'sword' will be added once, 'knife and fork' will be added 4 times.  Then I randomly choose an integer between 0 and size-1 of the list.
Then I select element at that place.

This is basically what I used to do, as well. It still seems like a natural approach. The reason I wanted to redo it, was that it ran slightly slow as my lists-of-stuff became bigger. I guess this has to do in part with the slowness of sorted lists in python, but mainly of course it's due to my subhuman coding skillz (my horns get in the way as I type). The new piece of code takes up less space in my source, and runs several times faster, sometimes knocking a few tenths of a second off of map building times.

As always,
Minotauros

[Z]

The approach with probability distributions given as numbers rather as repetitions generalizes to formulae. Thus, an elven sword might be very hard to find on low levels, popular on middle levels, and obsolete on high levels; abundant in elven-themed locations and avoided in orc-themed ones.

Also, repetitions are not very useful if you want some items to be extremely rare (in the given conditions) -- you would have to replicate the usual ones, say, thousands of times.

[AgingMinotaur]

Also, repetitions are not very useful if you want some items to be extremely rare (in the given conditions) -- you would have to replicate the usual ones, say, thousands of times.

Yes, that's what started happening to my list-based scheme. Some of the lists would be several hundred thousand instances long ...

As always,
Minotauros

[corremn]

Man, thats huge.

I choose random base types first then choose from the type that comes up. I.e First put in weapons, armour and misc items.  If weapons come up, I make another list with swords, axes, etc.  If swords comes up, I make another list with daggers, long swords.. and so on and so forth, thus eliminating creating massive lists of all items. 

So my lists only ever contain a few elements at a time.

[Z]

Yes, that's also a good idea because it is easy to maintain a balance between items of different kind. (So that if you decide to add a new weapon type, the balance won't be disrupted by reducing the chance of, say, obtaining potions of healing.)

Still, you need to put rare items somewhere in your tree (unless you use a different method altogether for them), and use a high multiplicity for your common path.