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

以下代码生成最后一个n-1数字的所有排列，并在每个排列之前加上原始列表的第一个元素。from itertools import permutations circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]my_list您要生成其所有循环排列的值的初始列表在哪里。

Answer 2

当您有一个由N个元素组成的列表时，该列表的一个循环排列由其第一个元素唯一地给出。Than表示您将具有正好N个循环排列（包括原始列表），并且可以通过删除fist元素并将其添加到列表的末尾从一个传递到另一个。您可以轻松地为列表的所有循环排列构建一个生成器：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演示：>>> list(circ_perm([1,2,3,4]))[[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]如果您想要的是唯一的排列（当两个排列是另一个排列的排列）时，您仍然可以使用以下事实：循环排列由其第一个元素给出，并固定第一个元素，并找到剩下的所有排列：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]]

Answer 3

进行排列的复杂度约为O（n * n！），因此对于大数或列表而言，生成所有可能的排列效率低下，您可以使用回溯来生成列表排列，我将分享一个链接，可能会有所帮助。 该解决方案基于回溯   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)