有效地生成具有顺序限制的排列（可能没有回溯）？

Question

我需要生成具有排序限制的排列

例如，在列表中[A,B,C,D]

A 必须始终位于 B 之前，而 C 必须始终位于 D 之前。也可能有也可能没有没有限制的 E,F,G...。输入将如下所示：[[A,B],[C,D],[E],[F]]

有没有办法在不计算不必要的排列或回溯的情况下做到这一点？

Answer 1

通常，permutations 算法可能看起来有点像这样 (Python)：

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']])

有效地生成具有顺序限制的排列（可能没有回溯）？

Efficiently generate permutations with ordering restrictions(possibly without backtracking)?

algorithm

enumeration

permutation

combinatorics

backtracking