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

Question

假设我们有一个长度为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_is顺序。我怎样才能做到这一点？我正在考虑使用递归函数f(X, M)在每个可能的点（Z）切割矢量for i in range(1,M+1)，然后用f(x_1, i)（递归）连接f((x_2, ..., x_N), M-i+1)（定义为基本情况）。但是这种方法并没有给出独特的向量，我不得不在之后删除重复项并且效率不高。有没有更好的方法来解决这个问题？也许使用itertools？

Answer 1

我认为这样的事情对你有用。它基本上是通过从列表M中获取元素来迭代填充X框。在这种情况下，默认内容是None，但您应该能够进行调整。你可以see how it works on 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指数。