Как добавить «-» между элементами в списке для каждой возможной комбинации?

Question

Допустим, у меня есть список ['a', 'b', '1', '2']. Мне нужно создать все возможные комбинации этого списка в том же порядке, но с добавлением тире между символами.

Так что мне нужно было бы получить все следующие ответы:

a-b12
ab-12
ab1-2
a-b-12
a-b1-2
ab-1-2
a-b-1-2

Я хочу сделать это для гораздо более длинной строки, которая будет иметь гораздо больше комбинаций. Как я могу это сделать?

Редактировать: Ребята, все эти комментарии были очень полезны! Я очень благодарен всем, кто помогает мне решить эту проблему, а не объясняет это так подробно!

Answer 1

a   b   1   2
  ^   ^   ^
  |   |   |
  0   1   2

Представьте, что у каждого пробела между символами есть индекс. Между a и b - индекс 0. Между b и 1 - индекс 1. Между 1 и 2 - индекс 2.

Каждый пробел может иметь тире илиничего.

Вы хотите проверить каждую комбинацию тире или ничего. Если вы думаете о каждом пробеле как о «бите», где каждый бит может быть 0 (пустым) или 1 (тире), это очень хорошо сопоставляется с проверкой всех комбинаций b битов, где b на единицу меньше количества имеющихся у вас предметов.

Чтобы проверить все битовые комбинации, все, что вам нужно сделать, - это перебрать от 1 до 2 ^b . (Пропустите 0, чтобы убедиться, что всегда есть хотя бы один тире.) Для каждой итерации вставляйте тире всякий раз, когда установлен соответствующий бит.

Вот как это выглядит, если мы просто излучаем тире или пробелы, игнорируя ab12 символов на данный момент.

Только тире

items = ['a', 'b', '1', '2']
bits  = len(items) - 1

for n in range(1, 2**bits):
    print(''.join('-' if n & (1<<i) else ' ' for i in range(bits)))

Выход

-  
 - 
-- 
  -
- -
 --
---

Есть чертовскиМногое происходит в этих последних двух строках. Позвольте мне разобрать это.

• for n in range(1, 2**bits) - Это прямой перевод того, что я объяснил выше. Цикл от 1 до 2 ^b . Разница лишь в том, что я назвал его битами вместо b . Код выигрывает от использования более описательных имен переменных.

• (<expr> for i in range(bits)) - цикл for внутри скобок называется выражением генератора . Это компактный способ создания серии элементов в одной строке кода. expr оценивается для каждого значения i .

• '-' if n & (1<<i) else ' ' - expr выше - это частьработай. Это основа алгоритма: для каждого пробела мы либо излучаем '-', либо ' '. Загадочный бит n & (1<<i) - это формула для проверки, установлен ли бит .

  Если вы не знакомы с побитовыми операциями, такими как &, побитовое AND и <<, сдвиг влево, я призываю вас за Google для получения дополнительной информации. Это отдельная увлекательная тема, которую я мог бы потратить, пытаясь объяснить страницы.

• ''.join(...) - это объединяет все строки '-' и ' ', которые мы генерируем водна большая строка.

Последний шаг - перемежать элементы и тире. Мы можем сделать это, добавив пару битов в код выше. Во-первых, мы будем добавлять items[i] перед каждой потенциальной чертой. Во-вторых, мы добавим items[-1] в конце. Эти два шага эффективно окружают штрихи элементами из списка.

Элементы и штрихи

items = ['a', 'b', '1', '2']
bits  = len(items) - 1

for n in range(1, 2**bits):
    print(''.join(items[i] + ('-' if n & (1<<i) else '') for i in range(bits)) + items[-1])

Выходные данные

a-b12
ab-12
a-b-12
ab1-2
a-b1-2
ab-1-2
a-b-1-2

Answer 2

Для ясности в отличие от скорости:

def insert( seq ):
    answers = [] 
    if seq[1:]:
        for subseq in insert( seq[1:] ):
            answers.append( [ seq[0],    ] + subseq )
            answers.append( [ seq[0],'-' ] + subseq )
    else:
        answers.append( seq )
    return answers

for answer in insert(['a','b','1','2'])[1:]:
    print ''.join(answer)

Вывод по желанию (хотя я бы хотел также вывести решение без черты):

a-b12
ab-12
a-b-12
ab1-2
a-b1-2
ab-1-2
a-b-1-2

Answer 3

Вот простое пошаговое решение. Это, вероятно, более неэффективно, чем другие ответы, но это простой подход.

Вы можете сначала перечислить все двоичные комбинации n-1, используя itertools.product():

from itertools import product

lst = ['a', 'b', '1', '2']

def binary_combinations(bits):
    return list(product([0, 1], repeat=bits))

binary_combs = binary_combinations(bits=len(lst) - 1)
# [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]

Затем вы можете разбить свой список с помощью '' между каждымпредмет. Это облегчает присоединение позже.

def intersperse(lst, item):
    result = [item] * (len(lst) * 2 - 1)
    result[0::2] = lst
    return result

interspersed_items = intersperse(lst, '')
# ['a', '', 'b', '', '1', '', '2']

Затем, наконец, вы можете вывести комбинации с замененными - и str.join() комбинацией результатов:

for comb in binary_combs[1:]:
    result = interspersed_items[:]

    for i, binary in enumerate(comb):
        if binary == 1:
            result[i * 2 + 1] = '-'

    print("".join(result))

, которая выводит следующие комбинации. Следующий порядок отличается от вопроса, но это не должно быть проблемой?

ab1-2
ab-12
ab-1-2
a-b12
a-b1-2
a-b-12
a-b-1-2