没有周期的排列

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。请参阅底部的完整代码。

[*]使用

基准结果，使用list（range（n））作为序列。 ints比较很快，因此，如果序列元素是一些具有更昂贵的比较的对象，则我的有效解决方案将具有更大的优势，因为它是唯一不依赖比较排列/元素的对象。

8 elements:
  1.76 ±  0.07 ms  efficient
  3.60 ±  0.76 ms  optimized_iter
  4.65 ±  0.81 ms  optimized_takewhile
  4.97 ±  0.43 ms  optimized_set
  8.19 ±  0.31 ms  optimized_generator
 21.42 ±  1.19 ms  original

9 elements:
 13.11 ±  2.39 ms  efficient
 34.37 ±  2.83 ms  optimized_iter
 40.87 ±  4.49 ms  optimized_takewhile
 46.74 ±  2.27 ms  optimized_set
 78.79 ±  3.43 ms  optimized_generator
237.72 ±  5.76 ms  original

10 elements:
160.61 ±  4.58 ms  efficient
370.79 ± 14.71 ms  optimized_iter
492.95 ±  2.45 ms  optimized_takewhile
565.04 ±  9.68 ms  optimized_set
         too slow  optimized_generator
         too slow  original

Code (Attempt This Online!):

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 optimized_set(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 optimized_iter(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 optimized_takewhile(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())


# Yet another way to filter by just the single next unwanted permutation
def optimized_generator(seq: list):
    perms = permutations(seq)
    yield next(perms)
    for i in range(1, len(seq)):
        skip = tuple(seq[i:] + seq[:i])
        for perm in perms:
            if perm == skip:
                break
            yield perm
    yield from perms


# Compute the indexes of the unwanted permutations and islice between them
def efficient(seq):
    def parts():
        perms = permutations(seq)
        yield next(perms),
        perms_index = 1
        n = len(seq)
        for rotation in range(1, n):
            index = 0
            for i in range(n, 1, -1):
                index = index * i + rotation * (i > rotation)
            yield islice(perms, index - perms_index)
            next(perms)
            perms_index = index + 1
        yield perms
    return chain.from_iterable(parts())


funcs = original, optimized_generator, optimized_set, optimized_iter, optimized_takewhile, 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(9):
    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[2:])

Answer 2

主张：通过循环排列不相互关联的N元素的集合排列与N-1元素的所有排列一对一的对应关系。

不严格的证明：任何置换{i1，i2，...，in}，具有k'th元素ik = 1，可以通过循环排列转换为置换{1，j2，...，...，jn}（带有j2 = i（k+1），j3 = i（k+2），...）。排列{1，J2，...，Jn}唯一代表循环排列的轨道。因此，n-1元素的任何置换{J2，...，Jn}代表n个元素置换的轨道，而n元素不与周期无关。

说服自己的最简单方法是计算维度（元素数）：
dim [n] = n！
昏暗[循环排列] = n
dim [n的置换n并不与周期相关的n = n！/n =（n-1）！ = dim [N-1的所有置换]

然后您需要做什么：
0。给定列表[“ 1”，“ 2”，...，“ n”]

1. 弹出第一个元素[2“，...，“ n”]
2. 计算所有排列[“ 2”，“ 3”。 。
3. ​“ n”]，[1“，“ 3”，“ 2” ...，“ n”] ...

Answer 3

请参阅这篇文章： python：生成所有符合条件的

排列是从列表中提取第一个元素，生成剩余元素的所有排列，并将这些排列附加到第一个元素。