在Python中找到答案時如何停止遞回？

我正在嘗試用 Python 構建一個簡單的聯系人跟蹤系統。下面的函式應該在我的資料庫中獲取 2 個人，如果他們有（in）直接聯系，則回傳，如果是間接聯系，則回傳他們之間的人數。

contact_tracing_datastructure = [{'Koen', 'Pieter'}, {'Kim', 'Koen', 'Bart'}, {'Tom', 'Pieter'}, {'Yana', 'Bart'}, {'Wouter', 'Yana'}, {'Wouter', 'Bert'}, {'Koen'}]

already_checked = set()

def x_had_contact_with_y_with_distance(meetings, person_x, person_y, distance=0):
    contacts_x = give_contacts(meetings, person_x)
    already_checked.add(person_x)
    if person_y in contacts_x:
        return True, distance
    elif len(already_checked) != len(population):
        distance  = 1
        for i in contacts_x:
            found = x_had_contact_with_y_with_distance(meetings, i, person_y, distance)
            if found:
                return True, distance
    else:
        return False

print(x_had_contact_with_y_with_distance(contact_tracing_datastructure, "Koen", "Wouter")

然而，該函式會一直運行直到達到最大遞回深度，即使我已經添加了 already_checked 變數來使它不會對一個人進行兩次檢查。在這種情況下，函式應該回傳 (True, 2)。Give_contacts(person_x) 只是給出一組 person_x 已經接觸過的人。
找到解決方案后如何停止遞回？提前致謝！

uj5u.com熱心網友回復：

重塑

首先，我會將您的資料從list(set(str))到dict(str,set(str))-

# list of set of string
input = [{'Koen', 'Pieter'}, {'Kim', 'Koen', 'Bart'}, {'Tom', 'Pieter'}, {'Yana', 'Bart'}, {'Wouter', 'Yana'}, {'Wouter', 'Bert'}, {'Koen'}]

# dict of (string -> set of string)
index = dict()
for s in input:
  for name in s:
    if name in index:
      index[name] = index[name] | s - {name}
    else:
      index[name] = s - {name}

for (name, others) in index.items():
  print(name, others)

Pieter {'Koen', 'Tom'}
Koen {'Pieter', 'Bart', 'Kim'}
Kim {'Koen', 'Bart'}
Bart {'Yana', 'Koen', 'Kim'}
Tom {'Pieter'}
Yana {'Bart', 'Wouter'}
Wouter {'Yana', 'Bert'}
Bert {'Wouter'}

圖形

優越的index外形讓您輕松書寫graph(t, q)——

def graph(t, q):
  def loop(r, q):
    yield r
    for name in t[q]:
      if name not in r:
        yield from loop((*r, name), name)
  return loop((q,), q)

for line in graph(index, "Koen"):
  print(line)

('Koen',)
('Koen', 'Bart')
('Koen', 'Bart', 'Kim')
('Koen', 'Bart', 'Yana')
('Koen', 'Bart', 'Yana', 'Wouter')
('Koen', 'Bart', 'Yana', 'Wouter', 'Bert')
('Koen', 'Pieter')
('Koen', 'Pieter', 'Tom')
('Koen', 'Kim')
('Koen', 'Kim', 'Bart')
('Koen', 'Kim', 'Bart', 'Yana')
('Koen', 'Kim', 'Bart', 'Yana', 'Wouter')
('Koen', 'Kim', 'Bart', 'Yana', 'Wouter', 'Bert')

痕跡

利用graph我們可以很容易地寫trace(t, q, p)-

def trace(t, p, q):
  for line in graph(t, p):
    if line[-1] == q:
      yield line

讓我們看看Koen追蹤到Kim-

for contact in trace(index, "Koen", "Kim"):
  print(len(contact) - 1, "->".join(contact))

2 Koen->Bart->Kim
1 Koen->Kim

以及如何Bert追蹤到Kim-

for contact in trace(index, "Bert", "Kim"):
  print(len(contact) - 1, "->".join(contact))

5 Bert->Wouter->Yana->Bart->Koen->Kim
4 Bert->Wouter->Yana->Bart->Kim

以及如何Yana追蹤Wouter——

for contact in trace(index, "Yana", "Wouter"):
  print(len(contact) - 1, "->".join(contact))

1 Yana->Wouter

彈力

修改graph以便可以搜索任何名稱，即使是圖中未出現的名稱 -

def graph(t, q):
  def loop(r, q):
    try:                                       # <- try
      yield r
      for name in t[q]:
        if name not in r:
          yield from loop((*r, name), name)
    except KeyError:                           # <- name not found
      return                                   # <- stop iteration
  return loop((q,), q)

for contact in trace(index, "Vivian", "Sylvia"):
  print(len(contact) - 1, "->".join(contact))

(no output)

標籤：Python 递归

上一篇：遞回函式中的計數器

下一篇：django-在一個post請求中提交多個表單（與單擊不同，因為我需要一起處理這兩個表單的資料！）