Про НЕрекурсивный перебор комбинаций в последовательности когда-то спрашивал, но за год чуть подзабыл логику...

Question

Про НЕрекурсивный перебор комбинаций в последовательности когда-то спрашивал, но за год чуть подзабыл логику...

Celtic Hammer Мудрец (16454), закрыт 3 месяца назад

Правильно сейчас ее восстановил в памяти?
==>
Берем самый правый ноль, заменяем его на 1, все что правее него (там только единицы, раз он самый правый) заменяем на нули.
Нужно перебрать комбинации всех возможных перестановок 0 и 1 в последовательности длины N.
Во-первых берем к сведению что это будут двоичные числа.
Во-вторых 0101 это десятичное 5, 0110 - 6, 0111 - 7, 1000 - 8 и так далее.
То есть в переходе к следующему числу есть закономерность - движемся справа налево, если встречаем 1 - заменяем его на 0, если встречаем 0 заменяем его на 1 и останавливаемся.
Реализуем это нерекурсивным перебором

 n = 4 
x = [0] * n 
def next_(x): 
    i = n - 1 
    while x[i] == 1:       
        x[i] = 0 
        i -= 1 
    x[i] = 1 
    return x 
         
while x != [1] * n: 
    print(*x) 
    x = next_(x) 
print(*x)

0 0 0 0
0 0 0 1
0 0 1 0 # В цикл не попадаем, так как x[i] == 0. x[i] заменяем на 1
0 0 1 1 # чик-чик, единички заменяем на нули, встретили ноль, выходим из цикла и встреченный ноль меняем на 1
0 1 0 0 # Опять в цикл не попадаем, так как x[i] == 0. x[i] заменяем на 1
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Answer 1

Да, идея вполне правильная.

Обобщённая реализация (для любого кол-ва значений, а не только 0, 1) через генератор:

 def gen(n, m):
    t = [0] * n
    while True:
        yield t
        for i in range(n - 1, -1 , -1):
            t[i] = (t[i] + 1) % m
            if t[i]: break
        else: return

for v in gen(3, 5): print(*v)