Перестановки Python с ограничениями

Question

Я использую python 3, и я пытаюсь найти способ получить все перестановки списка при одновременном применении некоторых ограничений.

Например, у меня есть список L=[1, 2, 3, 4, 5, 6, 7]

Я хочу, чтобы найти все перестановки. Однако, мои ограничения:

• 1 всегда должны прийти до 2.
• 3 должны прийти до 4, которые в свою очередь, должны прийти до 5.
• Наконец, 6 должны прийти до 7.

Конечно, я могу сгенерировать все перестановки и игнорировать те, которые не соответствуют этим ограничениям, но это было бы неэффективно, я думаю.

Answer 1

Этот подход фильтрует перестановкам с помощью простого фильтра ,

import itertools 

groups = [(1,2),(3,4,5),(6,7)] 
groupdxs = [i for i, group in enumerate(groups) for j in range(len(group))] 
old_combo = [] 
for dx_combo in itertools.permutations(groupdxs): 
    if dx_combo <= old_combo: # as simple filter 
     continue 
    old_combo = dx_combo 
    iters = [iter(group) for group in groups] 
    print [next(iters[i]) for i in dx_combo] 

Что мы здесь делаем, это найти permutations of a multiset. (В этом случае мультимножество groupdxs.) Вот paper, в котором подробно описывается алгоритм O (1).

Answer 2

Один из способов - взять один из алгоритмов подкачки, и когда вы собираетесь заменить элемент на его конечную позицию, проверьте, находится ли он в правильном порядке. Код ниже делает именно это.

Но сначала позвольте мне показать его использование:

L = [1, 2, 3, 4, 5, 6, 7] 
constraints = [[1, 2], [3, 4, 5], [6, 7]] 

A = list(p[:] for p in constrained_permutations(L, constraints)) # copy the permutation if you want to keep it 
print(len(A)) 
print(["".join(map(str, p)) for p in A[:50]]) 

и выход:

210 
['1234567', '1234657', '1234675', '1236457', '1236475', '1236745', '1263457', '1263475', '1263745', '1267345', '1324567', '1324657', '1324675', '1326457', '1326475', '1326745', '1342567', '1342657', '1342675', '1345267', '1345627', '1345672', '1346527', '1346572', '1346257', '1346275', '1346725', '1346752', '1364527', '1364572', '1364257', '1364275', '1364725', '1364752', '1362457', '1362475', '1362745', '1367245', '1367425', '1367452', '1634527', '1634572', '1634257', '1634275', '1634725', '1634752', '1632457', '1632475', '1632745', '1637245'] 

Но теперь код:

def _permute(L, nexts, numbers, begin, end): 
    if end == begin + 1: 
     yield L 
    else: 
     for i in range(begin, end): 
      c = L[i] 
      if nexts[c][0] == numbers[c]: 
       nexts[c][0] += 1 
       L[begin], L[i] = L[i], L[begin] 
       for p in _permute(L, nexts, numbers, begin + 1, end): 
        yield p 
       L[begin], L[i] = L[i], L[begin] 
       nexts[c][0] -= 1 


def constrained_permutations(L, constraints): 
    # warning: assumes that L has unique, hashable elements 
    # constraints is a list of constraints, where each constraint is a list of elements which should appear in the permatation in that order 
    # warning: constraints may not overlap! 
    nexts = dict((a, [0]) for a in L) 
    numbers = dict.fromkeys(L, 0) # number of each element in its constraint 
    for constraint in constraints: 
     for i, pos in enumerate(constraint): 
      nexts[pos] = nexts[constraint[0]] 
      numbers[pos] = i 

    for p in _permute(L, nexts, numbers, 0, len(L)): 
     yield p 

Answer 3

def partial_permutations(*groups): 
    groups = list(filter(None, groups)) # remove empties. 
    # Since we iterate over 'groups' twice, we need to 
    # make an explicit copy for 3.x for this approach to work. 
    if not groups: 
     yield [] 
     return 
    for group in groups: 
     for pp in partial_permutations(*(
      g[1:] if g == group else g 
      for g in groups 
     )): 
      yield [group[0]] + pp