Python算法：项链生成/循环排列

Question

我正在努力生成循环排列，或者用Python解决“项链问题”。基本上，我希望尽可能高效地生成列表的所有循环排列。在

基本上，假设我们有一个列表[1,2,3,4]，我想以循环的方式生成所有唯一的排列。所以：

[1,2,3,4]，[1,3,2,4]

将被视为不同，鉴于：

[1,2,3,4]，[4,1,2,3]将被视为相同的，因为我只寻找循环列表的唯一排列。在

我尝试过用itertools生成所有排列，但是当使用较大长度的列表时，这是非常低效的。在

作为另一个例子，考虑一个循环歌曲，其特点是[1,2,3,4,5]在重复播放。我试图想出一个算法，只生成唯一的订单。显然[1,2,3,4,5]和[4,5,1,2,3]会产生相同的顺序。在

正在挣扎，希望能帮助解决这个问题！在

Answer 1

进行排列的复杂性大约是O（n*n！），所以对于大数或列表，生成所有可能的排列都会很低效，可以用回溯来生成列表排列，我会分享一个链接可能会有帮助。 The solution is based on the backtracking

def permute(a, l, r): if l == r: print(a) else: for i in range(l, r + 1): a[l], a[i] = a[i], a[l] permute(a, l + 1, r) a[l], a[i] = a[i], a[l] data = [1,2,3,4,5] n = len(data) a = list(data) permute(a, 0, n - 1) ；

Answer 2

下面的代码生成最后一个n-1个数的所有置换，在每个置换之前加上原始列表的第一个元素。在

from itertools import permutations
circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]

其中my_list是生成所有循环置换的初始值列表。在

Answer 3

当你有一个N个元素的列表时，列表的一个循环排列是由它的第一个元素唯一给出的。Than意味着您将有N个循环排列（包括原始列表），并且您可以通过移除第一个元素并将其添加到列表末尾来从一个元素传递到另一个元素。在

您可以轻松地为列表的所有循环排列生成生成器：

def circ_perm(lst):
    cpy = lst[:]                 # take a copy because a list is a mutable object
    yield cpy
    for i in range(len(lst) - 1):
        cpy = cpy[1:] + [cpy[0]]
        yield cpy

演示：

^{pr2}$

---

如果你想要的是唯一的排列，当两个排列是另一个的圆形排列时，你仍然可以使用这样一个事实：一个圆形排列是由它的第一个元素给出的，然后固定第一个元素，然后找到剩下的所有排列：

def uniq_perm(lst):
    gen = itertools.permutations(lst[1:])
    for end in gen:
        yield [lst[0]] + list(end)

演示：

>>> list(uniq_perm([1,2,3,4]))
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]