python 无圈置换

x9ybnkn6  于 2023-06-20  发布在  Python
关注(0)|答案(3)|浏览(139)

我想生成一个列表的所有可能的排列,其中循环排列(从左到右)应该只发生一次。
下面是一个例子:
设列表为[A, B, C]。然后我想有像[A, C, B]这样的排列,而不是[B, C, A],因为这将是原始列表[A, B, C]的循环排列。对于上面的列表,结果应该如下所示

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

下面是一个使用itertools中的permutations()的最小工作示例。

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中是否有一种方法可以有效地解决这个问题?

jucafojl

jucafojl1#

这是不寻常的,所以不,这不是已经在itertools。但是我们可以显著地优化你的方法(主要是通过使用 set 而不是列表来过滤掉不需要的循环,甚至只过滤掉下一个不需要的循环)。更有效的是,我们可以计算不需要的排列[*]和它们之间的islice的索引。查看底部的完整代码。
[*]使用more-itertools的permutation_index的简化版本。
基准测试结果,使用list(range(n))作为序列。int比较相当快,所以如果序列元素是一些比较开销更大的对象,我的efficient解决方案将具有更大的优势,因为它是唯一一个不依赖于比较排列/元素的解决方案。

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

代码(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:])
7tofc5zh

7tofc5zh2#

权利要求:经由循环置换彼此不相关的N个元素的集合置换与N-1个元素的所有置换一一对应。
不严格证明:任何置换{i1,i2,…,iN},其中第k个元素ik = 1,可以通过循环置换变换为置换{1,j2,…,jN}(其中j2 = i(k +1),j3 = i(k +2),…)。置换{1,j2,…,jN}唯一地表示循环置换的轨道。因此,N-1个元素{j2,...,jN}的任何置换表示与圈无关的N个元素的置换的轨道。
说服自己的最简单方法是计算维度(元素的数量):Dim [N的所有排列]= N! Dim [循环置换]= N Dim [与循环无关的N的置换]= N!/N =(N-1)!= Dim [N-1的所有排列]
那么你需要做的是:0.给定列表["1","2",...,"N"]
1.弹出第一个元素["2",…,"N"]
1.计算所有排列[“2”,“3”...,“N”],[“3”,“2”...,“N”]...
1.将“1”附加到每个列表[“1”,“2”,“3”…,“N”],[“1”,“3”,“2”…,“N”]…

hgb9j2n6

hgb9j2n63#

请看这篇文章:Python: Generate All Permutations Subject to Condition
这个想法是从列表中提取第一个元素,生成剩余元素的所有排列,并将这些排列附加到第一个元素。

相关问题