Как переписать рекурсивную функцию, чтобы вместо нее использовать цикл? - PullRequest
Новая
       17

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

1 голос
/ 16 марта 2011

Этот поток переполнения стека утверждает, что каждая рекурсивная функция может быть записана как цикл.

Какие рекурсивные функции нельзя переписать с помощью циклов?

Это имеет полный смысл. Но я не уверен, как выразить следующую рекурсивную функцию как цикл, потому что она имеет предрекурсивный фрагмент логики и пострекурсивный фрагмент логики.

Очевидно, что решение не может использовать оператор goto. Код здесь: 

def gen_perms(lst, k, m):

    if k == m:
        all_perms.append(list(lst))
    else:
        for i in xrange(k, m+1):

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

            gen_perms(lst, k+1, m)

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

Вызов это будет выглядеть так: 

all_perms = []
gen_perm([1, 2, 3], 0, 2)

и генерирует каждую перестановку списка 1,2,3.

Ответы [ 3 ]

3 голосов
/ 16 марта 2011

Наиболее питонным способом перестановок является использование: 

>>> from itertools import permutations
>>> permutations([1,2,3])
>>> list(permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
1 голос
/ 17 марта 2011

Допустим, вы хотите найти все перестановки из [1, 2, 3, 4]. Их 24 (= 4!), Поэтому их число 0-23. Нам нужен нерекурсивный способ найти N-ю перестановку.

Допустим, мы сортируем перестановки в порядке возрастания чисел. Тогда:

  • Перестановки 0-5 начинаются с 1
  • Перестановки 6-11 начинаются с 2
  • Перестановки 12-17 начинаются с 3
  • Перестановки 18-23 начинаются с 4

Таким образом, мы можем получить первое число перестановок N, разделив N на 6 (= 3!) И округлив.

Как мы получаем следующий номер? Посмотрите на вторые числа в перестановках 0-5:

  • Перестановки 0-1 имеют второй номер 2.
  • Перестановки 2-3 имеют второй номер 3.
  • Перестановки 4-5 имеют второе число 4.

Мы видим похожую вещь с перестановками 6-11:

  • Перестановки 6-7 имеют второе число 1.
  • Перестановки 8-9 имеют второе число 3.
  • Перестановки 10-11 имеют второе число 4.

В общем случае возьмите остаток после деления на 6 раньше, разделите его на 2 (= 2!) И округлите. Это дает вам 1, 2 или 3, а вторым элементом является 1-й, 2-й или 3-й элемент, оставленный в списке (после того, как вы вынули первый элемент).

Вы можете продолжать идти по этому пути. Вот код, который делает это: 

from math import factorial

def gen_perms(lst):
    all_perms = []

    # Find the number of permutations.
    num_perms = factorial(len(lst))

    for i in range(num_perms):
        # Generate the ith permutation.
        perm = []
        remainder = i

        # Clone the list so we can remove items from it as we
        # add them to our permutation.
        items = lst[:]

        # Pick out each item in turn.
        for j in range(len(lst) - 1):
            # Divide the remainder at the previous step by the
            # next factorial down, to get the item number.
            divisor = factorial(len(lst) - j - 1)
            item_num = remainder / divisor

            # Add the item to the permutation, and remove it
            # from the list of available items.
            perm.append(items[item_num])
            items.remove(items[item_num])

            # Take the remainder for the next step.
            remainder = remainder % divisor

        # Only one item left - add it to the permutation.
        perm.append(items[0])

        # Add the permutation to the list.
        all_perms.append(perm)

    return all_perms
0 голосов
/ 16 марта 2011

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

int list[3]={1,2,3};
int i,j,k;

for(i=0;i < SIZE;i++)
for(j=0;j < SIZE;j++)
for(k=0;k < SIZE;k++)
if(i!=j && j!=k && i!=k)
printf("%d%d%d\n",list[i],list[j],list[k]);
...