python - 递归 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”，我尝试重置贡献，但无法弄清楚将其放在哪里。如果整个事情都很愚蠢，只要我完成工作，我愿意重写。

Answer 1

我认为你必须做一棵树，因为它看起来像一棵树

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

所以我实现了this code做正确的树

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 的新手，我知道代码可以做得更好，但我只是想帮忙
现在我将执行您的计算并更新我的答案

希望对你有用