在Python中给出n个元素列出所有定向循环的最有效方法

Question

我有一个可以说是相当大的(100种+元素)元素的列表:elements = [a, b, c, d, e, f, g...].

并且我需要建立所有可能的定向循环的列表,考虑到序列 [a,b,c,d,e], [b,c,d,e,a], [c,d,e,a,b], [d,e,a,b,c], [e,a,b,c,d]被认为是相同的,因为它们是相同定向循环的不同表示.只有起点不同.

此外,由于方向很重要,[a,b,c,d,e]并且[e,d,c,b,a]不同.

我正在寻找所有长度的定向循环,从2到len(elements).什么是最Python的方式做到这一点利用内置的优化permutations,combinations等等？

Answer 1

也许我错过了一些东西,但这对我来说似乎很简单:

def gen_oriented_cycles(xs):
    from itertools import combinations, permutations
    for length in range(2, len(xs) + 1):
        for pieces in combinations(xs, length):
            first = pieces[0],  # 1-tuple
            for rest in permutations(pieces[1:]):
                yield first + rest

然后,例如,

for c in gen_oriented_cycles('abcd'):
    print c

显示:

('a', 'b')
('a', 'c')
('a', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
('a', 'b', 'c')
('a', 'c', 'b')
('a', 'b', 'd')
('a', 'd', 'b')
('a', 'c', 'd')
('a', 'd', 'c')
('b', 'c', 'd')
('b', 'd', 'c')
('a', 'b', 'c', 'd')
('a', 'b', 'd', 'c')
('a', 'c', 'b', 'd')
('a', 'c', 'd', 'b')
('a', 'd', 'b', 'c')
('a', 'd', 'c', 'b')

这是否缺少一些您正在寻找的基本属性？

编辑

我认为可能会遗漏这部分标准:

此外,由于方向很重要,[a,b,c,d,e]和[e,d,c,b,a]不同.

但在第二个想法,我认为它符合要求,因为[e,d,c,b,a]是一样的[a,e,d,c,b]你.