递归Python函数-无法计算边缘情况

Question

我有以下字典：

>>> for key, details in relationships.items():
                print key, details[2]

('INVOICE', 'INVOICE') 1
('INVOICE', 'ORDER2') 0.50000000
('INVOICE', 'ORDER1') 0.01536410
('ORDER1', 'ORDER2') 0.05023163
('INVOICE', 'ORDER4') 0.00573215
('ORDER4', 'ORDER1') 0.08777898
('ORDER4', 'ORDER3') 0.01674388

这将创建以下层次结构：

INVOICE -> ORDER2
        -> ORDER1 -> ORDER2
        -> ORDER4 -> ORDER1 -> ORDER2
                  -> ORDER3

每个箭头代表details[2]的值。需要计算每个订单与发票的最终“关系”。预期值：

> ORDER1: 0.01586726 (0.0153641 + 0.0877898 x 0.00573215) 
> ORDER2: 0.50079704 (0.5 + 0.05023163 x 0.0153641 + 0.05023163 x 0.0877898 x 0.00573215)
> ORDER3: 0.00009598 (0.01674388 x 0.00573215)
> ORDER4: 0.00573215 (0.00573215)

我有以下递归函数的尝试：

for invoice in final_relationships.keys():
     calculate(invoice, invoice, Decimal(1))

def calculate(orig_ord, curr_ord, contribution):
     for rel_ID, rel_details in relationships.items():
          if rel_ID[1] == curr_ord:
               if orig_ord == curr_ord:
                    contribution = Decimal(1)
               if rel_ID[0] != rel_ID[1]:
                    contribution = (contribution * rel_details[2]).quantize(Decimal('0.00000001'), rounding=ROUND_HALF_UP)
                    calculate(orig_ord, rel_ID[0], contribution)
               else:
                    final_relationships[orig_ord] += contribution
                    contribution = Decimal(0)

这段代码可以正确计算所有情况，但对于ORDER2的情况则不适用。

------- ORDER2
1  # rel_ID,               curr_ord,     rel_details[2],    contribution
2  ('ORDER1', 'ORDER2')    ORDER2        0.05023163         1
3  ('INVOICE', 'ORDER1')    ORDER1        0.01536410         0.05023163
4  ('INVOICE', 'INVOICE')  INVOICE       1                  0.00077176
5  # final
6  0.00077176
7  ('ORDER4', 'ORDER1')    ORDER1        0.08777898         0.00077176
8  ('INVOICE', 'ORDER4')   ORDER4        0.00573215         0.00006774
9  ('INVOICE', 'INVOICE')  INVOICE       1                  3.9E-7
10 # final
11 0.00077215
12 ('INVOICE', 'ORDER2')   ORDER2        0.50000000         0.05023163
13 ('INVOICE', 'INVOICE')  INVOICE       1                  0.50000000
14 # final
15 0.50077215

问题在第7行，因为贡献从0.00077176开始而不是0.05023163，因为对于('ORDER1', 'ORDER2')的迭代没有第二次发生（在第2行之后）。 这是关系：INVOICE -> ORDER4 -> ORDER1 -> ORDER2。

我该如何修复这个函数？ 我尝试重置贡献，如果'orig_ord'没有被处理，但找不到放置它的位置。 如果整个东西都很愚蠢，我可以重新写，只要完成工作即可。

- user2524282

Answer 1

我认为你需要制作一棵树，因为这看起来像一棵树

INVOICE -> ORDER2
        -> ORDER1 -> ORDER2
        -> ORDER4 -> ORDER1 -> ORDER2
                  -> ORDER3

所以我实现了这段代码来生成正确的树

hierarchi = [('INVOICE', 'ORDER2'),
('INVOICE', 'ORDER1'),
('ORDER1', 'ORDER2'),
('INVOICE', 'ORDER4'),
('ORDER4', 'ORDER1'),
('ORDER4', 'ORDER3')]

def make_based_list(base):
  the_list = []
  i = 0
  for item in hierarchi:
    if(item[0] == base):
      the_list.insert(i,item)
      i+=1
  return the_list

class Node:
  def __init__(self,base):
    self.base = base
    self.children = []
    self.n_of_child = 0

  def get_child(self,base):
    found_child = Node('NOT_FOUND')
    for child in self.children:
      if child.base == base:
        found_child = child

    if found_child.base!='NOT_FOUND':
      return found_child
    else:
      for child in self.children:
        found_child = child.get_child(base)
        if found_child.base!='NOT_FOUND':
          return found_child
    return found_child

  def add_child(self,child_node):
    self.children.insert(self.n_of_child,child_node)
    self.n_of_child+=1

  def update_child(self,base,child_node):
    for child in self.children:
        if child.base == base:
          child = child_node
          return 1
    return 0

  def populate(self,assoc_list):
    for assoc in assoc_list:
      child_node = Node(assoc[1])
      self.add_child(child_node)

  def print_childrens(self):
    for child in self.children:
      child.print_me()

  def print_me(self):
    print("Me:"+self.base)
    if self.n_of_child>0:
      print("Mychilds:")
      self.print_childrens()
    else:
      print("No child")

top_base = 'INVOICE'
top_based_list = make_based_list(top_base)
top_node = Node(top_base)
top_node.populate(top_based_list)

for item in hierarchi:
  if item[0]!=top_base:
    the_child = top_node.get_child(item[1])
    the_parent = top_node.get_child(item[0])
    if the_child.base=='NOT_FOUND':
      the_child = Node(item[1])
    the_parent.add_child(the_child)
    top_node.update_child(item[0],the_parent)

top_node.print_me()

我是Python的新手，我知道代码可以更好，但我只是想帮忙。
现在我将实现你的计算并更新我的答案。

希望对你有用。

- Alessandro Lodi