Генерируйте все возможные перестановки для логических элементов 'n', которые имеют не более 'm' элементов, которые равны 1 или True

Question

Я хочу создать полный список перестановок из 4 элементов, которые имеют не более двух '1'.

Например, у меня n = 4 и m = 2:

Я хочувсе перестановки, которые содержат не более двух «1»:

[1,0,0,0], [0,1,0,0], [0,0,1,0],[0,0,0,1], [1,0,1,0], [0,0,1,1], [1,1,0,0], [1,1,0,0],[1,0,0,1] ... вы поняли идею.

Я попытался сгенерировать полный список всех перестановок, а затем выполнил If SUM <3, затем передайте его мне.Это работало хорошо, когда русских было мало.Проблема в том, что мне нужно сделать это для больших n> 30.

Как вы можете видеть, итерации будут идти до 2 ^ N, и это будет невозможно.

Поскольку m меньше(Я работаю с m меньше 5), мне просто нужен небольшой процент перестановок по сравнению со всеми возможными комбинациями.И порядок величин для итераций становится N ^ M, так что в этом случае он будет N ^ 5.

Есть ли простой способ создать этот список ??

[Отредактировано: написалхотя бы вместо максимум]

Answer 1

Набор перестановок логического массива длины n с точно m истинными значениями, по сути, совпадает с набором m -комбинаций из набора n вещей, что и является возвращается itertools.combinations. (В данном случае n - это индексы истинных значений m.)

Чтобы получить перестановки от до m истинных значений, нам просто нужно связать воедино комбинации значений i для i в range(m + 1), что можно легко сделать с помощью itertools.chain.from_iterable

from itertools import combinations, chain
# This returns an iterator
up_to_m_of_n = lambda n, m: chain.from_iterable(combinations(range(n), i)
                                                for i in range(m+1))
# Example:
list(up_to_m_of_n(4, 2))
[(), (0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

Превращение этих индексных массивов в логический массив немного раздражает, но все же выполнимо:

from operator import setitem
from functools import reduce
up_to_m_of_n_true = lambda n, m: map(lambda inds: reduce(lambda a, ind: setitem(a, ind, True) or a,
                                                         inds, [False] * n),
                                     up_to_m_of_n(n, m))
# Example (output reformatted)
list(up_to_m_of_n_true(4,2))
[False, False, False, False]
[True, False, False, False]
[False, True, False, False]
[False, False, True, False]
[False, False, False, True]
[True, True, False, False]
[True, False, True, False]
[True, False, False, True]
[False, True, True, False]
[False, True, False, True]
[False, False, True, True]

Обратите внимание, что в отличие от вашего примера, это относится и к случаю, когда значения True отсутствуют.

Возможно, чрезмерно функциональный up_to_m_of_n_true может быть более читабельным, как:

def indices_to_boolean(n, inds):
  bools = [False] * n
  for ind in inds: bools[ind] = True
  return bools

def up_to_m_of_n_true(n, m):
  for inds in up_to_m_of_n(n, m):
    yield indices_to_boolean(inds, n)

Answer 2

Не уверен, что это соответствует вашим ожиданиям производительности, вот один из подходов:

Описание:

1. n - это одинаковая длина двоичных последовательностейчто мы собираемся сгенерировать (например, 5). max_ones - это максимальное число единиц (например, 3)
2. ones, - это число единиц в одной из действительных перестановок.Оно может варьироваться от 0 до max_ones.
3. . Для каждого такого действительного значения ones (скажем, ones == 3) перестановки получаются путем взятия "семени" (скажем, (1,1,1,0,0)),создание итератора, который генерирует перестановки этой «начальной» последовательности, и, наконец, передача этого итератора в set() (чтобы он автоматически избегал дубликатов).Выражение (1,)*ones + (0,)*(n-ones) создает «начальную» последовательность.
4. Поскольку «единицы» варьируются от 0 до max_ones, мы получим много таких наборов.Мы наконец chain() все эти наборы вместе.

Код:

import itertools as itr

n = 4
max_ones = 2

my_all_atmost = set(itr.chain.from_iterable([set(itr.permutations(seed_row)) 
                                             for seed_row in {(1,)*ones + (0,)*(n-ones) 
                                                              for ones in range(0,max_ones+1)}]))

Вывод: (Например, где n == 4, max_ones == 2):

print (my_all_atmost)
{(1, 0, 0, 0), (1, 0, 1, 0), (1, 1, 0, 0), 
(0, 0, 0, 1), (1, 0, 0, 1), (0, 0, 1, 0), 
(0, 1, 0, 0), (0, 1, 1, 0), (0, 0, 0, 0), 
(0, 1, 0, 1), (0, 0, 1, 1)}

Answer 3

from itertools import permutations

l = list(permutations([0, 0, 1, 1]))

если вам нужны только уникальные, вы можете обернуть его в set:

set(list(permutations([0, 0, 1, 1])))

, если подсчет количества таких комбинаций / комбинаций - ваш единственныйбеспокойство, и вам не нужно использовать фактические экземпляры перестановок в ваших данных, просто используйте математические.Для всего этого есть выражения в замкнутой форме, см. Комбинаторику.