计算 list 有多少可能的排列，只要它 'fits' 进入另一个列表

Question

我正在尝试查找每个排列 'fitting' 到另一个列表中可能有多少列表排列（即排列的所有元素必须小于或等于相应的元素）。例如，列表 [1, 2, 3, 4] 必须适合列表 [2, 4, 3, 4].

本例有8种可能的排列方式：

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

因为 3 和 4 无法放入列表的第一个位置，所以所有以 3 或 4 开头的排列都被删除。此外，4 无法放入第三个插槽，因此删除了第三个插槽中带有 4 的任何剩余排列。

这是我当前尝试暴力破解问题的代码：

from itertools import permutations  

x = [1, 2, 3, 4] 
box = [2, 4, 3, 4] # this is the list we need to fit our arrangements into

counter = 0

for permutation in permutations(x):
  foo = True
  for i in range(len(permutation)):
    if permutation[i] > box[i]:
      foo = False
      break
  if foo:
    counter += 1
print(counter)

它有效，但因为我正在生成第一个列表的所有可能排列，所以它非常慢，但我就是找不到它的算法。我知道这基本上是一道数学题，但我数学不好。

Answer 1

如果将 x 反向排序，您可以尝试一次找到每个元素可以放入框中的所有位置。

在你的例子中：

4 有 2 个可以去的地方
3 有 3 个位置，但您必须考虑已经放置了“4”，所以你有 3 - 1 = 2 个可用
2 有 4 个位置，但你必须考虑已经放置了两个东西（“4”和“3”），所以你有 4 - 2 = 2 个可用
1 有 4 个位置，但您已经放置了 3 个...所以 4 - 3 = 1

乘积 2 * 2 * 2 * 1 是 8。

您可以通过以下一种方式做到这一点：

import numpy as np
counter = 1
for i, val in enumerate(reversed(sorted(x))):
    counter *= ( (val <= np.array(box)).sum() - i)
print(counter)

...或者没有 numpy（实际上更快）：

for i, val in enumerate(reversed(sorted(x))):
    counter *= ( sum( ( val <= boxval for boxval in box)) - i)

Answer 2

我对计时进行了一些试验，结果如下：

您的原始代码

for permutation in permutations(x):
    foo = True
    for i in range(len(permutation)):
        if permutation[i] > box[i]:
            foo = False
            break
    if foo:
        counter += 1

每个运行

大约需要 13569 ns

过滤排列

for i in range(100):
    res = len(list(filter(lambda perm: all([perm[i] <= box[i] for i in range(len(box))]), permutations(x))))

在 16717 ns 时花费了稍长的时间

里克 M

counter = 1
for i, val in enumerate(reversed(sorted(x))):
    counter *= ((val <= np.array(box)).sum() - i)

在 20146 ns 时花费了更长的时间

递归列表理解

def findPossiblities(possibleValues, box):
    return not box or sum([findPossiblities([rem for rem in possibleValues if rem != val], box[1:]) for val in [val for val in possibleValues if val <= box[0]]])
findPossiblities(x, box)

在 27052 ns 时甚至更长。

总而言之，使用 itertools 和过滤可能是最好的选择

计算 list 有多少可能的排列，只要它 'fits' 进入另一个列表

Count how many permutations of list possible as long as it 'fits' into another list

python

permutation

您的原始代码

过滤排列

里克 M

递归列表理解