Python 算法 : Necklace Generation/Circular Permutations

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 是生成所有循环排列的初始值列表。