Как получить все возможные комбинации?

Question

[HrustHr]

Как сгенерировать все возможные комбинации, если в ряде заменить одну из букв на Z?
Т.е. получить из abcdefg: Zbcdefg…abcZefg…abcdefZ.

Как сгенерировать все возможные комбинации, если в ряде заменить две буквы на Z и Y?
Т.е. получить из abcdefg: ZbcYefg…abZYefg…abcdeZY.

Comments

[kalapanga]

А при чём тут алгоритмы, математика? Это видимо какая-то задачка по программированию для начинающих?
В цикле ставите Z вместо очередной буквы - первой, второй, третьей и т.д.
Второй вопрос - два цикла, один внутри другого.

[HrustHr]

kalapanga, и как вы себе представляете один цикл внутри другого что бы все замены получились ? Если знаете, можно пример ?

[kalapanga]

HrustHr, вы бы попробовали что-то начать писать, всё бы и получилось!
Во внешнем цикле поставили Z на очередную позицию, во внутреннем ставите Y по очереди на все позиции, кроме той, на которой Z.

[Alexandroppolus]

kalapanga, возможно, внутренний цикл должен быть от позиции внешнего + 1, чтобы Y был справа

[Максим Припадчев]

Если у нас строка 'abc' например для меньшего количества вариантов то результат должен быть такой или нет?

[('Z', 'b', 'c'),
 ('Z', 'c', 'b'),
 ('a', 'Z', 'c'),
 ('c', 'Z', 'a'),
 ('a', 'b', 'Z'),
 ('b', 'a', 'Z')]

Для одной замены только на Z естественно.

[Максим Припадчев]

Смотри я сейчас про одну говорю, это же не все перестановки? У меня все когда устанавливаю Z на позицию, я ее фиксирую, и делаю все возможные перестановки остальных. А то что ты пишешь это другое где здесь все возможные перестановки после замены?

[Максим Припадчев]

HrustHr, Ничего не понимаю что вы хотите. Бред какой то, у вас первая Z всегда на первой позиции. Ну не знаю вот так можно этот бред воспроизвести.

sequence = '12345'
length = len(sequence)
seq = sequence[:0] + 'Z' + sequence[0 + 1:]
result = []
for i in range(1,length):
    result.append(seq[:i] + 'Z' + seq[i + 1:])

Answer 1

[Wataru]

itertools.combinations. Скармливаете туда range индексов вашей строки. Получаете список из 1/2/сколько надо сделать замен индексов, на эти позиции ставьте ваши Z, Y.

Вот набросок кода.
Я не питонист, возможно есть более лаконичная реализация. Особенно мерзкий хак с перобразованием строки в list, потому что строки в питоне immutable.

import itertools

def GenerateAll(source, rep):
  for comb in itertools.combinations(range(len(source)), len(rep)):
    s = list(source)
    for (i, j) in enumerate(comb):
      s[j] = rep[i];
    yield "".join(s)
    
print(list(GenerateAll("abcd", "XY")))
# ['XYcd', 'XbYd', 'XbcY', 'aXYd', 'aXcY', 'abXY']

Comments

[Wataru]

HrustHr, Дополнил ответ.

[HrustHr]

Wataru, почему то не находит aXZ1010101:

import itertools

def GenerateAll(source, rep):
  for comb in itertools.combinations(range(len(source)), len(rep)):
    s = list(source)
    for (i, j) in enumerate(comb):
      s[j] = rep[i];
    yield "".join(s)
    
#print(list(GenerateAll("0101010101", "aXZ")))

z =(list(GenerateAll("0101010101", "aXZ")))

if z == 'aXZ1010101':print(z)

[Wataru]

HrustHr, потому что вы сравниваете список всех замен со строкой. Сделайте

for x in GenerateAll(.....):
  if x == "....":

Все найдется.

[Wataru]

HrustHr, list() надо вызывать, если вы хотите все распечатать. Чтобы пройтись по всем комбинациям циклом, он не нужен.

Answer 2

[CBET_TbMbI]

Самый простой для понимания способ - цикл в цикле. Внешним циклом меняйте один символы по порядку на Z. Во вложенном перебирайте замены оставшихся букв хоть на Z, хоть на Y.

Answer 3

[Константин Цветков]

СТРОКА
ЦИКЛ i ОТ 1 ДО ДЛИНА(СТРОКА)
  ЗАМЕНИТЬ(СТРОКА, i, 'Z')

СТРОКА
ЦИКЛ i ОТ 1 ДО ДЛИНА(СТРОКА)-1
  ЗАМЕНИТЬ(СТРОКА, i, 'Z')
    ЦИКЛ j ОТ i+1 ДО ДЛИНА(СТРОКА)
        ЗАМЕНИТЬ(СТРОКА, j, 'Y')