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)