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 that you have read and understand our privacy policy and code of conduct.

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