我正在努力生成圓形排列，或者使用Python解決“項鏈問題”。我基本上是希望盡可能高效地生成列表的所有循環(huán)排列?；旧希僭O(shè)我們有一個列表[1,2,3,4]，我想以循環(huán)方式生成所有唯一排列。所以：[1,2,3,4]，[1,3,2,4]被認(rèn)為是不同的，而：[1,2,3,4]，[4,1,2,3]被認(rèn)為是相同的，因為我只在尋找循環(huán)列表的唯一排列。我嘗試使用生成所有排列，itertools但這在使用較大長度的列表時效率很低。再舉一個例子，考慮一個循環(huán)循環(huán)的歌曲，其特征是[1,2,3,4,5]重復(fù)播放。我正在嘗試提出一種僅生成唯一訂單的算法。顯然[1,2,3,4,5]和[4,5,1,2,3]的順序相同。努力奮斗，希望能為解決該問題提供幫助！
3 回答
翻翻過去那場雪
TA貢獻2065條經(jīng)驗 獲得超14個贊
以下代碼生成最后一個n-1數(shù)字的所有排列，并在每個排列之前加上原始列表的第一個元素。
from itertools import permutations circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]
my_list您要生成其所有循環(huán)排列的值的初始列表在哪里。
動漫人物
TA貢獻1815條經(jīng)驗 獲得超10個贊
當(dāng)您有一個由N個元素組成的列表時，該列表的一個循環(huán)排列由其第一個元素唯一地給出。Than表示您將具有正好N個循環(huán)排列（包括原始列表），并且可以通過刪除fist元素并將其添加到列表的末尾從一個傳遞到另一個。
您可以輕松地為列表的所有循環(huán)排列構(gòu)建一個生成器：
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]]
如果您想要的是唯一的排列（當(dāng)兩個排列是另一個排列的排列）時，您仍然可以使用以下事實：循環(huán)排列由其第一個元素給出，并固定第一個元素，并找到剩下的所有排列：
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]]
犯罪嫌疑人X
TA貢獻2080條經(jīng)驗 獲得超4個贊
進行排列的復(fù)雜度約為O（n * n?。?，因此對于大數(shù)或列表而言，生成所有可能的排列效率低下，您可以使用回溯來生成列表排列，我將分享一個鏈接，可能會有所幫助。 該解決方案基于回溯
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)
添加回答
舉報
0/150
提交
取消