Генератор рекурсивных перестановок, замена элементов списка не работает

Случилось на моем старом вопросе позже в моей карьере

Чтобы сделать это эффективно, вам нужно написать генератор.

Вместо того, чтобы возвращать список всех перестановок, что требует сохранения их (всех) в памяти, генератор возвращает одну перестановку (один элемент этого списка), затем делает паузу, а затем вычисляет следующий, когда вы его запрашиваете.

Преимущества генераторов:

• Take up much less space.
  • Generators take up between 40 and 80 bytes of space. One generators can have generate millions of items.
  • Список с одним элементом занимает 40 байт. Список из 1000 элементов занимает 4560 байт.
• More efficient
  • Only computes as many values as you need. In permuting the alphabet, if the correct permutation was found before the end of the list, the time spend generating all of the other permutations was wasted.

(Itertools.permutation является примером генератора)

Как написать генератор?

Написать генератор на питоне на самом деле очень просто.
По сути, напишите код, который будет работать для создания списка перестановок. Теперь вместо resultList+=[ resultItem ] напишите yield(resultItem).

Вот вы и сделали генератор. Если бы я хотел зациклить свой генератор, я мог бы написать

for i in myGenerator:

Это так просто.

Ниже представлен генератор кода, который я давно пытался написать:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Я думаю, у вас есть действительно хорошая идея, но отслеживание позиций может оказаться немного сложным. Общий способ, который я видел для рекурсивного создания перестановок, - это функция, которая принимает два строковых аргумента: один для удаления символов из (str) и один для добавления символов в (soFar).

При создании перестановки мы можем подумать о том, чтобы взять символы из str и добавить их в soFar. Предположим, у нас есть функция perm, которая принимает эти два аргумента и находит все перестановки str. Затем мы можем рассмотреть текущую строку str. У нас будут перестановки, начинающиеся с каждого символа в str, поэтому нам просто нужно перебрать str, используя каждый из этих символов в качестве начального символа и вызывая perm для символов, оставшихся в строке:

// half python half pseudocode    
def perm(str, soFar):
    if(str == ""):
        print soFar // here we have a valid permutation
        return

    for i = 0 to str.length:
        next = soFar + str[i]
        remaining = str.substr(0, i) + str.substr(i+1)
        perm(remaining, next)