Python算法:项链生成/循环排列
Python算法:项链生成/循环排列
提问于 2018-07-26 13:45:22
我正在努力生成循环排列，或者用Python解决“项链问题”。我基本上是希望尽可能高效地生成列表的所有循环排列。
基本上，假设我们有一个列表1,2,3,4，我想以循环的方式生成所有唯一的排列。所以：
1,2,3,4，1,3,2,4
会被认为是不同的，而：
1,2,3, 4，1,2,3被认为是相同的，因为我只寻找循环列表的唯一排列。
我尝试过用itertools生成所有的排列，但是当使用更长的列表时效率非常低。
作为另一个例子，考虑由重复播放的1,2,3,4,5首歌曲组成的运行循环。我正在尝试想出一种算法，只生成唯一的订单。显然，1,2,3,4,5和4,5,1,2,3将导致相同的顺序。
正在苦苦挣扎，希望能得到一些帮助解决这个问题！
回答 3
Stack Overflow用户
发布于 2018-07-26 14:59:24
下面的代码生成最后一个n-1数的所有排列，并在每个排列前面加上原始列表的第一个元素。
from itertools import permutations
circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]其中my_list是要生成所有循环排列的初始值列表。
Stack Overflow用户
发布于 2018-07-26 14:32:27
进行排列的复杂度大约是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)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51531766
复制相关文章
相似问题