這個Python腳本爲什麼偶爾遞歸？

Question

我在自學Python，寫了一個小腳本來交換聖誕禮物（這不是家庭作業）。我的家人喜歡每個人給同一個性別的人送一份禮物。以下腳本大部分時間都適用，但有時會通過無限遞歸失敗。我不知道爲什麼，因爲我認爲基本案例最終會得到滿足。

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) 

這是錯誤（編輯添加的完整的錯誤）：

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 

感謝您的任何幫助。

Answer 1

首先讓我們考慮女性。如果您的程序運行並將Jane與Jill匹配，然後將Jill與Jane匹配，Jane是唯一剩下的女性，並且因爲她無法匹配自己，您的程序將無限期地無限期運行。

讓我提出一種替代方法來解決您的問題。隨機洗牌您的送禮者/接收者的訂單，並讓每個人給列表中的下列人員送禮，並讓列表中的最後一個人送禮給第一個人。這將是這個樣子：

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] 

Answer 2

簡吉爾和吉爾簡

誰不玉器給？

Answer 3

這裏是你的腳本的一個簡單的迭代變。它工作得很好。

作爲一個假設，我認爲，基於概率論，有時候你只需要調用的匹配功能太多次，所以它使程序達到遞歸限制

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) 

Answer 4

有一個稍微容易明白這樣做的方法：

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')] 

Answer 5

以下版本實際上允許更多的選擇可能性。

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) 

編輯：不知何故，我覺得這個遺址從感恩節帽子畫的樂趣.... :)