0

Как создать все возможные комбинации из элементов массива?

-Длина каждой комбинации должна быть равна 5

-Недостающие пробелы нужо заполнить 0ми

-Элементы должны остаться в той же последовательности.

-Между элементами должен быть хотя бы один ноль.

пример 1

Массив ['1','11']
N = 5

Ответ:

['10110','10011','01011']

пример 2: Массив ['1','1']

N = 5

Ответ:

['10100','10010','10001','01010','01001','00101']
2
  • В исходном списке (в питоне нет массивов) могут быть пустые строки? Если да, как их обрабатывать? Что на выходе, если на входе ['1', '']? Если нет, рассматриваем отдельно все 3 возможности: в списке 1, 2 или 3 элемента.
    – andy.37
    18 фев 2018 в 20:04
  • Пустых строк нет. Минимум один знак есть 18 фев 2018 в 22:23

3 ответа 3

4

Можно воспользоваться рекурсивной функцией

def f(arr, N, start=''):
  # Массив без первого элемента
  arr1 = arr[1:]
  # Сколько мест надо, чтоб разместить arr1
  alen = sum(map(len, arr1))+len(arr1)-1
  # Нужен ли 0 после первого элемента
  if(alen):
    alen += 1
  # Размещаем первый элемент на всех возможных позициях
  for i in range(N-alen-len(arr[0])+1):
    add = '0'*i + arr[0]
    if(arr1):
      f(arr1, N-len(add)-1, start + add + '0')
    else:
      # Если элементов не осталось, печатаем результат
      print(start + add + '0'*(N-len(add)))

arr = ['1','11']
N = 5
f(arr,N)

demo

2

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

import itertools
i = str(input("i: "))
j = str(input("j: "))
my_list = [i,j]
check = 0
for k in my_list:
    check+=len(k)

while check < 5:
    my_list.append('0')
    check+=1

my_list = list(itertools.permutations(my_list))

new_set = set()

check_list = [i+'0'+j, i+'00'+j, i+'000'+j]

for comb in my_list:
    for check in check_list:
        if check in ''.join(comb):
            new_set.add(comb)
print(new_set)
0

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

Если на входе: ['a', 'bb'], то так как обязателен нуль между элементами и их порядок должен сохраняться, то можно считать что на входе ['a', '0bb']. Так как N=5 и общая длина элементов равна 4, то только одна позиция свободная в этом примере, то есть задача сводится: включить один бит в трёх битовом числе binary(3, 1):

0 0 1
0 1 0
1 0 0

Каждый включённый бит соответствует нулю в результате:

a 0bb 0
a 0 0bb 
0 a 0bb

Возвращаясь к примеру в вопросе: ['1', '11'] результат получается:

1 011 0
1 0 011
0 1 011

Пробелы для наглядности оставлены, в фактическом результате их нет:

<script src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()">
<script type="text/python">
def binary(n, k):
    """Generate all *n* bits with *k* set bits."""
    if k == 0:  # no bits set
        yield (0,) * n
    elif n == k:  # all bits set
        yield (1,) * k
    else:
        assert n > k > 0
        for bits in binary(n - 1, k):
            yield (0,) + bits
        for bits in binary(n - 1, k - 1):
            yield (1,) + bits

def arrange_zeros(nplaces, items):
    """Arrange zeros in *nplaces* between *items*"""
    occupied_len = sum(map(len, items)) # place for items
    assert len(items) > 0
    occupied_len += len(items) - 1  # place for mandatory 0 in between items
    nzeros = nplaces - occupied_len
    assert nzeros >= 0
    items = items[:1] + ['0'+item for item in items[1:]]  # add zero in between items
    for bits in binary(len(items)+nzeros, nzeros):
        it = iter(items)
        yield ''.join('0' if b else next(it) for b in bits)
    
# try your own input    
from browser import document
@document["mybutton"].bind("click") 
def on_click(event):
    nplaces = int(document["nplaces"].value)
    items = document["items"].value.split()
    print(f"N: {nplaces} Элементы: {items}")
    for s in arrange_zeros(nplaces, items):
        print(s)
</script>
<div><label for="nplaces">N: <input id="nplaces" value="5"></div>
<div><label for="items">Элементы: <input id="items" value="1 11"></div>
<div><button id="mybutton">Запустить</button></div></body>

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.