有效地生成排序限制（可能沒有回溯）？

Question

我需要生成的排列與訂貨

例如訂購的限制，在列表中[A,B,C,D]

A必須總是B面前，C必須D之前總會來。也有可能沒有限制的E,F,G...。 輸入看起來像這樣：[[A,B],[C,D],[E],[F]]

有沒有辦法做到這一點，而無需計算不必要的排列或回溯？

Answer 1

通常情況下，permutations算法可能看起來有點像這樣（蟒蛇）：

def permutations(elements): 
    if elements: 
     for i, current in enumerate(elements): 
      front, back = elements[:i], elements[i+1:] 
      for perm in permutations(front + back): 
       yield [current] + perm 
    else: 
     yield [] 

您遍歷列表，同時每一個元素作爲第一元素，並將它們與所有的排列組合剩下的元素。您可以輕鬆地修改這一點，以便elements實際上元素的列表，而不是僅僅使用current元素，你彈出第一個元素關閉該列表並插入休息回遞歸調用：

def ordered_permutations(elements): 
    if elements: 
     for i, current in enumerate(elements): 
      front, back = elements[:i], elements[i+1:] 
      first, rest = current[0], current[1:] 
      for perm in ordered_permutations(front + ([rest] if rest else []) + back): 
       yield [first] + perm 
    else: 
     yield [] 

結果爲ordered_permutations([['A', 'B'], ['C', 'D'], ['E'], ['F']])：

['A', 'B', 'C', 'D', 'E', 'F'] 
['A', 'B', 'C', 'D', 'F', 'E'] 
['A', 'B', 'C', 'E', 'D', 'F'] 
[ ... some 173 more ... ] 
['F', 'E', 'A', 'C', 'D', 'B'] 
['F', 'E', 'C', 'A', 'B', 'D'] 
['F', 'E', 'C', 'A', 'D', 'B'] 
['F', 'E', 'C', 'D', 'A', 'B'] 

但是請注意，這將在每次遞歸調用創造了很多中間的列表中。相反，您可以使用堆棧，將第一個元素從堆棧彈出並在遞歸調用之後重新打開。

def ordered_permutations_stack(elements): 
    if any(elements): 
     for current in elements: 
      if current: 
       first = current.pop() 
       for perm in ordered_permutations_stack(elements): 
        yield [first] + perm 
       current.append(first) 
    else: 
     yield [] 

該代碼也許更容易理解。在這種情況下，您必須保留子列表，即將其稱爲ordered_permutations_stack([['B', 'A'], ['D', 'C'], ['E'], ['F']])