递归 - 创建正嵌套在Python

“for”循环

首先，这里有一些背景：

想象有一个3 * 6表与它的一些项目（比方说4）。根据一定的规则，这些项目可以在此表中移动。我想要获得这些项目的所有可能的展示位置。我的解决办法是找出一个“运动空间”为每个项目，其中一个项目可以在不违反规则的自由移动，然后生成所有可能的展示位置。

一件重要的事情：一个项目的“运动空间”依赖于其他项目的立场。如果一个项目改变其位置，其他项目的“移动空间”也会改变。

比方说，我们有四个项目，其初始位置存储在一个字典：

items = ['a','b','c','d'] 

position_dict = {'a': (1, 6), 'b': (1, 1), 'c': (1, 4), 'd': (2, 1)}

我们在给定的字典中找出了“运动空间”为给定项目的功能。

available_pos('a', position_dict) 

[(1, 5), (1, 6), (2, 4), (2, 5), (2, 6)]

好的，这是问题所在。我正在编写一个丑陋的嵌套'for'循环来生成展示位置。它首先更新字典并获取下一个项目的移动空间，然后循环这个新的移动空间。直到达到最低水平。

pos = [] 

ava1 = available_pos('a', position_dict) # a dict for a's space 

for a in ava1: 
    position_dict['a'] = a # update the dict 
    ava2 = available_pos('b', position_dict) # new dict for b's space 

    for b in ava2: 
     position_dict['b'] = b # update the dict 
     ava3 = available_pos('c', position_dict) # new dict for c's space 

     for c in ava3: 
      position_dict['c'] = C# update the dict 
      ava4 = available_pos('d', position_dict) # new dict for d's space 

      for d in ava4: 
       pos.append([a, b, c, d])

这是问题，因为我有各种情况下具有不同数量的项目和位置设置的这样500+同样的问题。因此，我想知道是否有可能为它可以创建在每个级别一个新的要被重复字典正嵌套循环创建一个函数？

我知道递归可以做的伎俩，但我不是很熟悉。有什么建议么？

谢谢！

编辑：因为它是从1开始，更糟糕的

的指示系统，可能觉得奇怪，在坐标的第一个数字是指列，第二个数字指的是行。我这样做是因为一些微不足道的原因，但如果我将它们改回来，问题仍然存在。

来源

2017-02-23 Han Zhang

你想将它们或第一把它们并将它们放置后要移动呢？如果你只想放置它们，那么我认为这是一个相当基本的计算机科学问题。 – Elmex80s

@ Elmex80s我想我想放置它们，然后移动它们。每个项目在表格中都有一个初始位置，这决定了它们的初始“移动空间”。但是，当一件物品移动到另一个位置时，其他物品的移动空间可能会改变。 –

首先移动哪一个很重要？或者他们试着同时移动，也就是说在每次迭代中，'a''，''b''，'c''和''d''移动到他们的新位置？ – Elmex80s

这也许

def do_step(item, position_dict, depth): 
    print position_dict 

    if depth > 0:   
     new_positions = available_pos(item, position_dict) 

     for (x, y) in new_positions: 
      position_dict[item] = (x, y) 

      for next_item in ['a', 'b', 'c', 'd']: 
       do_step(next_item, position_dict.copy(), depth - 1)

你叫do_step('a', position_dict.copy(), 10)。给出了position_dict。

这是应该运行的非功能性的版本快

def do_step(item, position_dict, depth): 
    print position_dict 

    if depth > 0: 
     old_position = position_dict[item]   
     new_positions = available_pos(item, position_dict) 

     for (x, y) in new_positions: 
      position_dict[item] = (x, y) 

      for next_item in ['a', 'b', 'c', 'd']: 
       do_step(next_item, position_dict, depth - 1) 

     # Restore the old position 
     position_dict[item] = old_position

来源

2017-02-23 20:36:47 Elmex80s

递归是去这里的路。由于你多次做同样的事情，编写一个函数来做它是很自然的。

让我们先从非递归函数。它可能看起来像这样：

def update_pos(item): 
    ava1 = available_pos(item, position_dict) 

    for a in ava1: 
     position_dict[item] = a 
     # but now what? we need to update the next item's location

这更新了1个项目的位置，所以下一步是让它更新多个项目的位置。因此，我们不会传递一个项目，而是将它传递给一个项目列表。

def update_pos(items_): # I called it items_ to avoid a name clash with the global items list 
    item= items_[0] 
    ava1 = available_pos(item, position_dict) 

    for a in ava1: 
     position_dict[item] = a 
     #recursively update the remaining items' positions 
     if len(items_) > 1: 
      update_pos(items_[1:])

所有剩下现在要做的就是以实际产生的结果：

def update_pos(items_): 
    item= items_[0] 
    ava1 = available_pos(item, position_dict) 

    for a in ava1: 
     position_dict[item] = a 
     #recursively update the remaining items' positions 
     if len(items_) > 1: 
      update_pos(items_[1:]) 
     else: 
      pos.append([position_dict[i] for i in items])

我没有测试此代码，但它至少应该给你一个想法如何解决你的问题。

来源

2017-02-23 20:09:04

递归 - 创建正嵌套在Python

回答

相关问题