algorithm - 有效地生成具有排序限制的排列(可能没有回溯)？

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