Как вернуть все возможные условные двудольные совпадения? - PullRequest
Новая
       39

Как вернуть все возможные условные двудольные совпадения?

0 голосов
/ 12 апреля 2019

Предположим, что у нас есть массив 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_i с местоположениями 1,...,M, так что порядок x_i сохраняется.Как я могу это сделать?Я думал об использовании рекурсивной функции f(X, M), которая обрезает вектор Z в каждой возможной точке (for i in range(1,M+1)), а затем объединяет f(x_1, i) (определяется как базовый случай) с f((x_2, ..., x_N), M-i+1) (рекурсия).Но этот подход не дает уникальных векторов, и я должен удалить дубликаты впоследствии, и он неэффективен.Есть ли лучший способ решить эту проблему?Может быть, с помощью itertools?

1 Ответ

0 голосов
/ 12 апреля 2019

Я думаю, что-то подобное должно работать на вас. По сути, это итеративное заполнение полей M путем извлечения элементов из списка 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.

...