相关疑难解决方法(0)

如何在Python中生成列表的所有排列,与该列表中的元素类型无关？

例如:

permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

一些背景:我正在编写或多或少的强力搜索算法来解决我遇到的问题.为了做到这一点,我需要生成并评估所有可能性,以找出哪个是最好的.由于评估实际上需要一些时间,我宁愿尽可能少地生成完全覆盖我的搜索空间的解决方案.此外,我可以做的更多元素越多越好.对于任何数字K,通常有K!对于高于~10的数字,排列和生成它们都很难.

真正的问题:搜索空间应包含两个元素的所有排列(N次el1和M乘以el2,其中K = M + N),具有以下限制:

1. 他们必须是独一无二的(即我只想要[aabbb]一次)
2. 我不需要任何排列的反转(即如果我有[aab],我也不需要[baa])
3. 我认为排列是圆形的,所以[aab] = [aba] = [baa]

如果我能够做到这一点,可能性的数量将大大减少.由于理想情况下K很大,因此首先生成所有排列然后根据这些标准过滤它们是不可行的.我已经完成了第一个限制(见下文),它将Matlab的正常排列函数(perms)的数量从2 ^ K减少到K!/ N!M !,这是一个巨大的胜利.第二个限制只会将可能性的数量减少一半(在最好的情况下),但我认为第三个也应该能够真正减少可能性的数量.

如果有人知道怎么做,最好还有如何计算会有多少种可能性,这对我有很大的帮助!我更喜欢解释,但代码也很好(我可以读C语言,Java(脚本),Python,Ruby,Lisp/Scheme).

对于感兴趣的:这是迄今为止我只获得唯一排列的算法:

function genPossibilities(n, m, e1, e2)
     if n == 0
         return array of m e2's
     else
         possibilities = genPossibilities(n-1, m, e1, e2)
         for every possibility:
             gain = number of new possibilities we'll get for this smaller possibility*
             for i in max(0,(m+n-gain))
                 if possibility(i) is not e1
                     add possiblity with e1 inserted in position i
         return new possibilities

• 如果您有N-1和M的所有排列,那么您可以使用它们通过将e1插入其中来查找N和M的排列.你不能只是在任何地方插入,因为那样你就会得到重复.我不知道为什么会这样,但你可以计算出你从旧的可能性中产生的新可能性的数量(我称之为"增益").对于第一个旧排列,该数字从M + 1开始,并且对于每个旧排列减少一个,直到它变为零,此时它返回到M等等(仅当M> = …