Генератор рекурсивной перестановки, обмен местами не работает - PullRequest
Новая
       72

Генератор рекурсивной перестановки, обмен местами не работает

0 голосов
/ 09 апреля 2011

Я хочу систематически генерировать перестановки алфавита.Я не могу не хотеть использовать python itertools.permutation, потому что при создании списка каждой перестановки мой компьютер падает (в первый раз, когда я действительно заставил его завершить работу, это было довольно здорово).

ПоэтомуМой новый подход заключается в создании и тестировании каждого ключа на лету.В настоящее время я пытаюсь справиться с этим с помощью рекурсии.

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

Например, для 123

123 (позиция обмена0 с позицией 0) 

    23    --> 123 (swap position 1 with position 1)
    32    --> 132 (swap position 1 with position 2)

213 (позиция свопа 0 с позицией 1) 

    13    --> 213 (swap position 1 with position 1)
    31    --> 231 (swap position 1 with position 2)

321 (позиция свопа 0 с позицией 2) 

    21    --> 321 (swap position 1 with position 1)
    12    --> 312 (swap position 1 with position 2)

для четырехбуквенного числа (1234)

1234 (позиция обмена 0 с позицией 0) 

    234    (swap position 1 with position 1)

           34 --> 1234
           43 --> 1243
    324    (swap position 1 with position 2)
           24 --> 1324
           42 --> 1342
    432    (swap position 1 with position 3)
           32 --> 1432
           23 --> 1423

2134 (позиция замены 0 для позиции 1) 134 (свопположение 1 с положением 1) 34 -> 2134 43 -> 2143 314 (поменяйте положение 1 с положением 2) 14 -> 2314 41 -> 2341 431 (поменяйте положение 1 с положением 3) 31 -> 2431 13-> 2413

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

def perm(x, y, key):
    print "Perm called: X=",x,", Y=",y,", key=",key
    while (x<y):

        print "\tLooping Inward"

        print "\t", x," ",y," ", key
        x=x+1
        key=perm(x, y, key)
        swap(x,y,key)
        print "\tAfter 'swap':",x," ",y," ", key, "\n"

    print "\nFull Depth Reached"
    #print key, " SWAPPED:? ",swap(x,y,key)
    print swap(x, y, key)
    print " X=",x,", Y=",y,", key=",key
    return key

def swap(x, y, key):
    v=key[x]
    key[x]=key[y]
    key[y]=v
    return key

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

Спасибо всем!Комментарии на мой метод или что-нибудь приветствуются.

Ответы [ 2 ]

1 голос
/ 20 июня 2012

Произошел мой старый вопрос позже в моей карьере

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

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

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

  • Занимают гораздо меньше места.
    • Генераторы занимают от 40 до 80 байт пространства.Один генератор может генерировать миллионы элементов.
    • Список с одним элементом занимает 40 байтов.Список из 1000 элементов занимает 4560 байт
  • Более эффективно
    • Вычисляет только столько значений, сколько вам нужно.При перестановке алфавита, если правильная перестановка была найдена до конца списка, время, затрачиваемое на создание всех других перестановок, было потрачено впустую.

(Itertools.permutationпример генератора)

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

На самом деле написать генератор на python очень просто.
По сути, напишите код, который бы работал для генерации списка перестановок.Теперь вместо 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

0 голосов
/ 09 апреля 2011

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