Блог

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

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

#python #recursion #permutation #matching

#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_i s с местоположениями 1,...,M таким образом, чтобы x_i порядок s сохранялся. Как я могу это сделать? Я думал об использовании рекурсивной функции 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. какую реальную проблему вы пытаетесь решить? Как вы будете использовать такую функцию?

2. @aaaaaa Я хочу разработать функцию для возврата всех возможных Z s. Число можно вычислить математически, например, для M = 7 и N = 3 должно дать 70 (я думаю) различных Z s. Позже я хочу использовать результат в других частях моего кода.

3. Я понимаю ваш вопрос, но я хочу знать, может быть, большую проблему можно решить проще, чем вы думаете прямо сейчас. вы собираетесь часто вызывать этот генератор, например? почему ваше решение недостаточно эффективно?

4. @aaaaaa я вижу. Да, я буду часто вызывать этот генератор. В моей проблеме я N = 3 исправил, но M варьируется (я думаю, от 3 до 10). Но, может быть, я могу вычислить их заранее и сохранить результаты генератора в словаре.

5. тем не менее, было бы полезно опубликовать фрагмент кода, который использует эти списки. По сути, у вас есть M контейнеров подряд, и вы должны заполнить их, беря элементы один за другим X1, X2, X3, размещая в контейнерах по-разному?

Ответ №1:

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