没有循环的排列

Question

我想生成列表的所有可能排列，其中循环排列（从左到右）应该只发生一次。

举个例子：

让列表为

[A, B, C]

。然后我想要像

[A, C, B]

这样的排列，但不是

[B, C, A]

，因为这将是原始列表

[A, B, C]

的循环排列。对于上面的列表，结果应该是这样的

[A, B, C]
[A, C, B]
[B, A, C]
[C, B, A]

这是一个最小的工作示例，它使用

permutations()

中的

itertools

。

from itertools import permutations


def permutations_without_cycles(seq: list):
    # Get a list of all permutations
    permutations_all = list(permutations(seq))

    print("\nAll permutations:")
    for i, p in enumerate(permutations_all):
        print(i, "\t", p)

    # Get a list of all cyclic permutations
    cyclic_permutations = [tuple(seq[i:] + seq[:i]) for i in range(len(seq))]

    print("\nAll cyclic permutations:")
    for i, p in enumerate(cyclic_permutations):
        print(i, "\t", p)

    # Remove all cyclic permutations except for one
    cyclic_permutations = cyclic_permutations[1:]  # keep one cycle
    permutations_cleaned = [p for p in permutations_all if p not in cyclic_permutations]

    print("\nCleaned permutations:")
    for i, item in enumerate(permutations_cleaned):
        print(i, "\t", item)


def main():
    seq = ["A", "B", "C"]
    permutations_without_cycles(seq=seq)


if __name__ == "__main__":
    main()

想知道

itertools

有没有什么方法可以有效的解决这个问题？

Answer 1

这很不寻常，所以不，itertools 中还没有。但是我们可以显着优化您的方式（主要是通过使用 set 而不是列表来过滤掉不需要的循环，或者甚至只使用下一个不需要的循环）。更有效的是，我们可以计算它们之间不需要的排列^[*] 和

islice

的索引。请参阅底部的完整代码。

[*] 使用来自 more-itertools 的 permutation_index 的简化版本。

基准测试结果，使用

list(range(n))

作为序列。整数比较相当快，所以如果序列元素是一些比较昂贵的对象，我的

efficient

解决方案将具有更大的优势，因为它是唯一不依赖于比较排列/元素的方法。

8 elements:
  1.10 ±  0.01 ms  efficient
  2.25 ±  0.02 ms  original_optimized2
  2.83 ±  0.04 ms  original_optimized3
  3.28 ±  0.08 ms  original_optimized
 13.07 ±  0.48 ms  original

9 elements:
 10.56 ±  0.50 ms  efficient
 22.59 ±  2.00 ms  original_optimized2
 27.83 ±  1.25 ms  original_optimized3
 34.42 ±  2.11 ms  original_optimized
178.86 ± 10.38 ms  original

10 elements:
108.28 ±  4.69 ms  efficient
259.80 ± 19.20 ms  original_optimized2
327.01 ± 33.55 ms  original_optimized3
397.93 ± 25.59 ms  original_optimized
         too slow  original

代码（在线尝试！）：

from itertools import permutations, chain, islice, filterfalse, takewhile
from timeit import timeit
from statistics import mean, stdev
from collections import deque

# Your original, just without the prints/comments, and returning the result
def original(seq: list):
    permutations_all = list(permutations(seq))
    cyclic_permutations = [tuple(seq[i:] + seq[:i]) for i in range(len(seq))]
    cyclic_permutations = cyclic_permutations[1:]
    permutations_cleaned = [p for p in permutations_all if p not in cyclic_permutations]
    return permutations_cleaned


# Your original with several optimizations
def original_optimized(seq: list): 
    cyclic_permutations = {tuple(seq[i:] + seq[:i]) for i in range(1, len(seq))}
    return filterfalse(cyclic_permutations.__contains__, permutations(seq))


# Further optimized to filter by just the single next unwanted permutation
def original_optimized2(seq: list):
    def parts():
        it = permutations(seq)
        yield next(it),
        for i in range(1, len(seq)):
            skip = tuple(seq[i:] + seq[:i])
            yield iter(it.__next__, skip)
        yield it
    return chain.from_iterable(parts())


# Another way to filter by just the single next unwanted permutation
def original_optimized3(seq: list):
    def parts():
        it = permutations(seq)
        yield next(it),
        for i in range(1, len(seq)):
            skip = tuple(seq[i:] + seq[:i])
            yield takewhile(skip.__ne__, it)
        yield it
    return chain.from_iterable(parts())


def efficient(seq):
    def parts():
        it = permutations(seq)
        yield next(it),
        it_index = 1
        n = len(seq)
        for rot in range(1, n):
            index = 0
            for i in range(n, 1, -1):
                index = index * i + rot * (i > rot)
            yield islice(it, index - it_index)
            next(it)
            it_index = index + 1
        yield it
    return chain.from_iterable(parts())


funcs = original, original_optimized, original_optimized2, original_optimized3, efficient


#--- Correctness checks

seq = ["A", "B", "C"]
for f in funcs:
    print(*f(seq), f.__name__)

seq = 3,1,4,5,9,2,6
for f in funcs:
    assert list(f(seq)) == original(seq)

for n in range(10):
    seq = list(range(n))
    for f in funcs:
        assert list(f(seq)) == original(seq)


#--- Speed tests

def test(seq, funcs):
    print()
    print(len(seq), 'elements:')

    times = {f: [] for f in funcs}
    def stats(f):
        ts = [t * 1e3 for t in sorted(times[f])[:5]]
        return f'{mean(ts):6.2f} ± {stdev(ts):5.2f} ms '

    for _ in range(25):
        for f in funcs:
            t = timeit(lambda: deque(f(seq), 0), number=1)
            times[f].append(t)

    for f in sorted(funcs, key=stats):
        print(stats(f), f.__name__)

test(list(range(8)), funcs)
test(list(range(9)), funcs)
test(list(range(10)), funcs[1:])

Answer 2

请参阅这篇文章：Python：根据条件生成所有排列

想法是从列表中拉出第一个元素，生成 remaining 元素的所有排列，并将这些排列附加到第一个元素。