时间戳

首页 > 解决方案 > 如何返回所有可能的条件二分匹配？

python - 如何返回所有可能的条件二分匹配？

问题描述

假设我们有一个X = (x_1, ..., x_N)长度数组N。我们希望返回所有可能的长度数组M（M固定），其元素可以来自(x_1, ..., x_N, NaN)这样的元素，每个元素最多x_i使用一次并x_i保留顺序。例如，如果N = 3和M = 7，一些可能的向量是 

 Z = (x_1, NaN, NaN, x_2, x_3, NaN, NaN)
 Z = (NaN, x_1, NaN, NaN, x_3, NaN, NaN)
 Z = (x_3, NaN, NaN, NaN, NaN, NaN, NaN)
 Z = (NaN, NaN, NaN, NaN, NaN, NaN, NaN)

但以下向量是不可接受的：

 Z = (x_1, x_1, NaN, x_2, x_3, NaN, NaN)
 Z = (NaN, x_3, NaN, NaN, x_2, NaN, NaN)

这个问题可以被视为将一些x_is 与位置匹配，1,...,M从而x_i保留 s 顺序。我怎样才能做到这一点？我正在考虑使用递归函数在每个可能的点 ( ) 处f(X, M)切割向量，然后将(定义为基本情况) 与(递归)。但是这种方法并没有给出唯一的向量，我必须在之后删除重复项，而且效率不高。有没有更好的方法来解决这个问题？也许使用 itertools？Zfor i in range(1,M+1)f(x_1, i)f((x_2, ..., x_N), M-i+1)

标签： pythonrecursionpermutationmatching

解决方案

我认为这样的事情应该适合你。它基本上是M通过从 list 中获取元素来迭代填充框X。默认内容是None在这种情况下，但你应该能够调整。你可以在 repl 上看到它是如何工作的

N = 3
M = 6

X = range(N) # or example, can be [x1,x2,x3]

for j1 in range(M-N+1):
  for j2 in range(j1+1,M-N+2):
    for j3 in range(j2+1,M):
      r = [None]*M
      r[j1] = X[0]
      r[j2] = X[1]
      r[j3] = X[2]
      print(r)

这将产生以下输出：

[0, 1, 2, None, None, None]
[0, 1, None, 2, None, None]
[0, 1, None, None, 2, None]
[0, 1, None, None, None, 2]
[0, None, 1, 2, None, None]
[0, None, 1, None, 2, None]
[0, None, 1, None, None, 2]
[0, None, None, 1, 2, None]
[0, None, None, 1, None, 2]
[0, None, None, None, 1, 2]
[None, 0, 1, 2, None, None]
[None, 0, 1, None, 2, None]
[None, 0, 1, None, None, 2]
[None, 0, None, 1, 2, None]
[None, 0, None, 1, None, 2]
[None, 0, None, None, 1, 2]
[None, None, 0, 1, 2, None]
[None, None, 0, 1, None, 2]
[None, None, 0, None, 1, 2]
[None, None, None, 0, 1, 2]

理想情况下，您希望将其推广到任意 N，这样您就不必对 、 和索引进行j1硬j2编码j3。

推荐阅读