Why is this Python script occasionally recursive?

Question

I am teaching myself Python and have written a small script for exchanging Christmas gifts (this is not homework). My family likes for each person to give one gift to one person of the same gender. The following script works most of the time but sometimes fails through infinite recursion. I am not sure why, because I think the base case will eventually be met.

import random

family = {'Joe': 'm', 'Jane': 'f', 'John': 'm', 'Jill': 'f', 'James': 'm', 'Jade': 'f'}
receivers = family.copy()
givers = family.copy()

def match(giver):
    index = random.randrange(len(receivers))
    giverGender = givers[giver]
    receiver = receivers.keys()[index]
    receiverGender = receivers.values()[index]

    if giver != receiver and giverGender == receiverGender:
        del receivers[receiver]
        return giver + ' to ' + receiver
    else:
        return match(giver)

# main program
for i in givers:
    print match(i)

This is the error (EDIT to add full error):

Traceback (most recent call last):
  File "C:\...\christmasGifts.py", line 22, in <module>
    print match(i)
  File "C:\...\christmasGifts.py", line 18, in match
    return match(giver)

  ...

  File "C:\...\christmasGifts.py", line 18, in match
    return match(giver)
  File "C:\...\christmasGifts.py", line 9, in match
  index = random.randrange(len(receivers))
  File "C:\Python27\lib\random.py", line 184, in randrange
istart = int(start)
RuntimeError: maximum recursion depth exceeded while calling a Python object

Thank you for any help.

This isn't an answer, more of a suggestion: look up Derangement, as it describes your problem fairly well, minus the gender requirement. — Kevin
– Kevin, Commented Nov 16, 2012 at 17:58
@Kevin, thanks. This is interesting and definitely a partial answer, as that link also has a (Python!) algorithm for derangement. — jds
– jds, Commented Nov 16, 2012 at 18:39

Bi Rico · Accepted Answer · 2012-11-16 17:59:05Z

6

First lets just consider the women. If your program runs and matches Jane to Jill, then matches Jill to Jane, Jane is the only female left and because she cannot match herself, your program runs indefinitely without a match.

Let me propose an alternate method to solve your problem. Randomly shuffle the order of your givers/recieves and have each person give a gift the the following person in the list, and have the last person in the list gift the first person. That would look something like this:

from random import shuffle
women = ['Jane', 'Jill', 'Jade']
shuffle(women)
print women[-1] + ' to ' + women[0]
for i in range(len(women) - 1):
    print women[i] + ' to ' + women[i+1]

edited Nov 16, 2012 at 17:59

answered Nov 16, 2012 at 17:53

Bi Rico

25.9k3 gold badges57 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Kevin Over a year ago

Your shuffle method is a cool idea, although it doesn't generate all possible gift-giving possibilities if you have 4+ participants. For example, A -> B, B -> A, C -> D, D -> C can't be generated in this way. Not that it matters much for Secret Santa, of course. Uncle Joe won't care whether the gift-giving graph is always fully connected or not.

Bi Rico Over a year ago

Ya you're right, I figured it would be good enough for Secret Santa purposes. I don't know of an algorithm to do derangement, though I'm sure it exists.

mgilson Over a year ago

@Kevin -- What gives you the right to say what Uncle Joe does or does not care about? ;-)

jds Over a year ago

Thank you! Both an explanation and a nice solution.

John Gaines Jr. Over a year ago

Yay! for non-recursive solution. Unless the language depends on recursion (e.g. lisp) I'd suggest staying away from recursion while learning the language (unless of course you're a functional language guru out on a jaunt).

f p · Accepted Answer · 2012-11-16 17:53:31Z

2

Jane to Jill and Jill to Jane

Who does Jade give to?

answered Nov 16, 2012 at 17:53

f p

3,2431 gold badge30 silver badges36 bronze badges

1 Comment

jds Over a year ago

Perfect. This explains why it works fine for four people (two males, two females).

mr_borsch · Accepted Answer · 2012-11-16 17:54:34Z

0

Here is a simple iterative variant of your script. It works pretty well.

As an assumption I think that, based on the probability theory, sometimes you just call the match function too many times, so it cause the program to reach the recursion limit

import random

family = {'Joe': 'm', 'Jane': 'f', 'John': 'm', 'Jill': 'f', 'James': 'm', 'Jade': 'f'}
receivers = family.copy()
givers = family.copy()

def match(giver):
    giverGender = givers[giver]

    Found = False
    while not Found:
        index = random.randrange(len(receivers))
        receiver = receivers.keys()[index]
        receiverGender = receivers.values()[index]
        if giver != receiver and giverGender == receiverGender:
            Found = True
            del receivers[receiver]
    return giver + ' to ' + receiver


# main program
if __name__=='__main__':
    for i in givers:
        print match(i)

answered Nov 16, 2012 at 17:54

mr_borsch

813 bronze badges

1 Comment

Kevin Over a year ago

Does this address the problem raised by the other answers? That is, if Joe gives John a present, and John gives Joe a present, will this loop forever when trying to find a recipient for James' present?

Jon Clements · Accepted Answer · 2012-11-16 18:10:00Z

0

There's a slightly easier to understand way of doing this:

from itertools import izip_longest
from random import shuffle

family = {
    'Joe': 'm',
    'Jane': 'f',
    'John': 'm',
    'Jill': 'f',
    'James': 'm',
    'Jade': 'f'
}

females = [k for k, v in family.iteritems() if v == 'f']
for num in range(5):
    shuffle(females) # muck up the order a bit
    print list(izip_longest(females, females[1:], fillvalue=females[0]))

[('Jade', 'Jill'), ('Jill', 'Jane'), ('Jane', 'Jade')]
[('Jane', 'Jill'), ('Jill', 'Jade'), ('Jade', 'Jane')]
[('Jade', 'Jane'), ('Jane', 'Jill'), ('Jill', 'Jade')]
[('Jade', 'Jane'), ('Jane', 'Jill'), ('Jill', 'Jade')]
[('Jill', 'Jane'), ('Jane', 'Jade'), ('Jade', 'Jill')]

answered Nov 16, 2012 at 18:10

Jon Clements

143k34 gold badges254 silver badges288 bronze badges

Comments

Noah · Accepted Answer · 2012-11-16 20:22:33Z

0

The version below actually allows for more possibilities of choices.

from random import randint

giver = ['Jane', 'Jill', 'Jade', 'Nicole', 'Charlotte']

receiver = [i for i in giver]

def match(giver, receiver):
    for i in giver:

        #get random receiver
        rec = receiver[randint(0,len(receiver)-1)]

        #check to see if only two remain, so person doesn't pick self in loop.
        if len(receiver) == 2:
            rec = receiver[1]

        #make sure person doesn't select themself.
        while i == rec:
            rec = receiver[randint(0,len(receiver)-1)]

        print i + " gives to " + rec
        #reduce receiver pool
        receiver.remove(rec)

Edit: I somehow think this ruins the fun of drawing from a hat at Thanksgiving.... :)

edited Nov 16, 2012 at 20:22

answered Nov 16, 2012 at 20:17

Noah

3191 silver badge5 bronze badges

Collectives™ on Stack Overflow

Why is this Python script occasionally recursive?

5 Answers 5

5 Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

5 Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related