1

如何找到可以重新排列数字序列（可能包含类似项目）的方式的数量，以便数字不会放置在与其或类似数字相同的位置。

例如，[0,0,0,1,1,1]只能以一种方式重新排列，即[1,1,1,0,0,0].

[0,0,0,1,1,1,1]不能以任何方式安排。

[1,2,2,14]可以以两种方式排列，即[2,1,14,2], [2,14,1,2]。

[1,1,2,2,14]可以以 4 种方式排列，即[14,2,1,1,2], [2,2,14,1,1], [2,2,1,14,1], [2,14,1,1,2]。

数学解决方案是可用的，但我正在考虑使用编程概念的一些简单方法。数学代码有点像这样..（对不起，我不能以正确的格式发布）

∫∞0 Ln1(x)..Lnr(x)e−xdx

其中 r 是项目数，ni 是项目 i 的出现次数，Lk 是第 k 个拉盖尔多项式。例如，对于 1,1,2,2,14，我们有 r=3，n1=2，n2=2，n3=1，所以直到一个符号，重排的数量是

∫∞0 L2(x)L2(x)L1(x)e−xdx 
= ∫∞0 12(x2−4x+2)12(x2−4x+2)(1−x)e−xdx 
= ∫∞0(−14x5+94x4−7x3+9x2−5x+1)e−xdx
= −4

但我在想是否有任何 python 库可以根据我们的需要生成所有排列。

4

3 回答 3

3

您是否尝试过 itertools.permutations？

http://docs.python.org/library/itertools.html#itertools.permutations

import itertools

def my_combos(val):
    results = []
    l = itertools.permutations(val, len(val))
    for c in l:
        if all([x != y for (x,y) in zip(c,val)]):
            results.append(c)
    return list(set(results))


print my_combos([0,0,0,1,1,1])
print my_combos([1,1,2,2,14])

产量：

[(1, 1, 1, 0, 0, 0)]
[(2, 14, 1, 1, 2), (2, 2, 1, 14, 1), (14, 2, 1, 1, 2), (2, 2, 14, 1, 1)]
于 2012-05-21T10:47:08.313 回答
3

涉及更多，但在长输入序列上应该更快：

from collections import Counter

def _rearrange(orig, rem):
    if len(orig)==1:
        v = rem[0][0]
        if v != orig[0]:
            yield [v]
    else:
        o, orig = orig[0], orig[1:]
        for i,(v,c) in enumerate(rem):
            if v != o:
                for r in _rearrange(orig, rem[:i]+([(v,c-1)] if c>1 else [])+rem[i+1:]):
                    yield [v]+r

def rearrange(orig):
    if len(orig) > 1:
        return list(_rearrange(orig, Counter(orig).items()))
    else:
        return []

def main():
    print rearrange([0,0,0,1,1,1])
    print rearrange([1,1,2,2,14])

if __name__=="__main__":
    main()

结果是

[[1, 1, 1, 0, 0, 0]]
[[2, 2, 1, 14, 1], [2, 2, 14, 1, 1], [2, 14, 1, 1, 2], [14, 2, 1, 1, 2]]

.

编辑：比较函数的运行时，我得到：

在此处输入图像描述

（蒂姆的蓝色，我的绿色；点是数据，线最适合（数据对数的最小二乘）；x 轴是序列长度，y 轴是以秒为单位的运行时间（对数刻度）。数据点是十个中最好的对每个序列长度的 20 个随机序列中的每一个运行。）

结论：

  • Tim 的 fn 的运行时间增长为 7.44 * * n；我的增长为 3.69 * * n。

  • 在十项序列中，他的 fn 平均为 53.9 秒，而我的为 0.93 秒；序列中每个额外项目的差异略多于两倍。

  • 他的 fn 运行时间更加一致；我的是高度可变的，取决于序列中重复项目的数量。

  • 直线拟合看起来不是最好的预测器；运行时应该是 n! 的函数，而不是 k * * n。不过，我不确定如何建模。建议？

于 2012-05-21T14:35:10.067 回答
1

蛮力使用itertools：

import itertools
def arrangements(arr):
    p = itertools.permutations(arr)
    return set(item for item in p if all(x!=y for x,y in zip(item,arr)))

结果：

>>> arrangements([0,0,0,1,1,1])
{(1, 1, 1, 0, 0, 0)}
>>> arrangements([0,0,0,1,1,1,1])
set()
>>> arrangements([1,2,2,14])
{(2, 14, 1, 2), (2, 1, 14, 2)}
>>> arrangements([1,1,2,2,14])
{(2, 14, 1, 1, 2), (2, 2, 1, 14, 1), (14, 2, 1, 1, 2), (2, 2, 14, 1, 1)}
于 2012-05-21T11:00:37.423 回答