Блог

Я хочу сгенерировать полный список перестановок из 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]… вы поняли идею.

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

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

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

Есть ли простой способ сгенерировать этот список??

[Отредактировано: написано как минимум, а не как максимум]

Набор перестановок логического массива длины 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]
  

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

Возможно, чрезмерно функциональный 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)
  

 from itertools import permutations

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

  

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

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

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

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

Описание:

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)}