Я хочу сделать комбинацию 1 и 0 в массиве 2d следующим образом:
[[ 1, 1, 1, 1, 0, 0, 0, 0 ],
[ 1, 1, 1, 0, 1, 0, 0, 0 ],
[ 1, 1, 1, 0, 0, 1, 0, 0 ],
[ 1, 1, 1, 0, 0, 0, 1, 0 ],
[ 1, 1, 1, 0, 0, 0, 0, 1 ],
.
.
.
]
Это означает комбинацию из четырех единиц и четырех нулей. Я просмотрел permutations() и combinations() модуля itertools, но не смог найти подходящих функций для выполнения этой комбинации.
Вы также можете использовать combinations для прямого создания уникальных комбинаций:
n = 8
n1 = 4
for x in itertools.combinations( xrange(n), n1 ) :
print [ 1 if i in x else 0 for i in xrange(n) ]
[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 0, 1, 0, 0, 0]
[1, 1, 1, 0, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 0, 1, 0]
...
[0, 0, 0, 1, 1, 1, 0, 1]
[0, 0, 0, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1]
Это более эффективно, чем permutations, потому что вы не перебираете нежелательные решения.
Интуиция такова, что вы пытаетесь найти все возможные способы разместить четыре «1» в последовательности длиной 8; это точное определение комбинаций. Это число C(8,4)=8! / (4! * 4!) = 70. Напротив, решение, использующее permutations, перебирает 8! = 40,320 решений-кандидатов.
permutations, особенно однострочное, так как сразу понятно, что делает код, и накладные расходы на генерацию тоже не такие большие (но могут быть для большего количества бит).
- person tobias_k; 07.07.2014
permutations может быть более читаемым, но попробуйте использовать его с n>15...
- person usual me; 07.07.2014
Вы создаете перестановку мультимножества.
Простой, но наивный подход заключается в использовании itertools.permutations() с набором чтобы отфильтровать повторяющиеся комбинации:
>>> from itertools import permutations
>>> seen = set()
>>> for combo in permutations([1] * 4 + [0] * 4):
... if combo not in seen:
... seen.add(combo)
... print combo
...
(1, 1, 1, 1, 0, 0, 0, 0)
(1, 1, 1, 0, 1, 0, 0, 0)
(1, 1, 1, 0, 0, 1, 0, 0)
(1, 1, 1, 0, 0, 0, 1, 0)
(1, 1, 1, 0, 0, 0, 0, 1)
(1, 1, 0, 1, 1, 0, 0, 0)
# ...
(0, 0, 1, 0, 1, 0, 1, 1)
(0, 0, 1, 0, 0, 1, 1, 1)
(0, 0, 0, 1, 1, 1, 1, 0)
(0, 0, 0, 1, 1, 1, 0, 1)
(0, 0, 0, 1, 1, 0, 1, 1)
(0, 0, 0, 1, 0, 1, 1, 1)
(0, 0, 0, 0, 1, 1, 1, 1)
или, производя всю последовательность за один раз:
set(permutations([1] * 4 + [0] * 4))
но это теряет порядок, который произвел permutations.
Набор необходим, так как permutations() видит 4 1 и 4 0 как отдельные символы, а один 1, переставленный другим, считается уникальной перестановкой.
Вы также можете использовать порядок в последовательности, чтобы избежать использования набора:
last = (1,) * 8
for combo in permutations([1] * 4 + [0] * 4):
if combo < last:
last = combo
print combo
Подход наивен в том, что 2n! перестановки производятся там, где нам нужны только (2n выбирают n) элементы. Для вашего случая это 40320 перестановок, где нам нужно произвести только 70.
set(itertools.permutations([1]*4+[0]*4))?
- person tobias_k; 07.07.2014
sorted(set(...), reverse=True). +1
- person tobias_k; 07.07.2014
permutations() создает кортежи; вы можете легко вызвать list() для каждого еще не просмотренного результата и добавить его в список.
- person Martijn Pieters; 07.07.2014
sorted(map(list, set(permutations([1]*4+[0]*4))), reverse=True) для создания списка списков.
- person Martijn Pieters; 07.07.2014
