Python 算法:项链生成/循环排列 [英] Python Algorithms: Necklace Generation / Circular Permutations

问题描述

我正在努力生成循环排列，或者用 Python 解决项链问题".我基本上希望尽可能有效地生成列表的所有循环排列.

I am struggling with generating circular permutations, or solving the "Necklace Problem" with Python. I am basically looking to generate all circular permutations of a list as efficiently as possible.

基本上，假设我们有一个列表 [1,2,3,4]，我想以循环方式生成所有唯一的排列.所以:

Basically, assume we have a list [1,2,3,4], I want to generate all unique permutations in a circular fashion. So:

[1,2,3,4], [1,3,2,4]

[1,2,3,4], [1,3,2,4]

会被认为是不同的，而:

Would be considered different, whereas:

[1,2,3,4], [4,1,2,3] 将被认为是相同的，因为我只在寻找循环列表的唯一排列.

[1,2,3,4], [4,1,2,3] would be considered the same, as I am looking only for unique permutations of a circular list.

我已经尝试使用 itertools 生成所有排列，但是在使用较大长度的列表时效率非常低.

I have tried generating all permutations with itertools but this is very inefficient when using larger length lists.

再举一个例子，考虑一首循环播放的歌曲，其特点是 [1,2,3,4,5] 重复播放.我正在尝试提出一种算法来仅生成唯一订单.显然 [1,2,3,4,5] 和 [4,5,1,2,3] 会导致相同的顺序.

As another example, consider a running loop songs, characterised by [1,2,3,4,5] playing on repeat. I am trying to come up with an algorithm to generate only unique orders. Obviously [1,2,3,4,5] and [4,5,1,2,3] would result in the same order.

正在努力中，希望能得到一些帮助来解决这个问题！

Struggling and would appreciate some help to solve this problem!

推荐答案

以下代码生成最后 n-1 个数字的所有排列，并在每个排列之前添加原始列表的第一个元素.

The following code produces all permutations of the last n-1 numbers, prepending each permutation with the first element of the original list.

from itertools import permutations
circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]

其中 my_list 是生成所有循环排列的初始值列表.

Where my_list is your initial list of values to generation all circular permutations of.

这篇关于Python 算法:项链生成/循环排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！