How to rewrite a recursive function to use a loop instead?

This stack overflow thread claims that every recursive function can be written as a loop.

Which recursive functions cannot be rewritten using loops?

It makes complete sense. But I'm not sure how to express the following recursive function as a loop because it has a pre recursive piece of 开发者_如何学Gologic and a post recursive piece of logic.

Obviously the solution cannot use the goto statement. The code is here:

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

Invoking it would be like this:

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

and it generates every permutation of the list 1,2,3.

The most pythonic way of doing permutations is to use:

>>> 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)]

Let's say you want to find all permutations of [1, 2, 3, 4]. There are 24 (=4!) of these, so number them 0-23. What we want is a non-recursive way to find the Nth permutation.

Let's say we sort the permutations in increasing numerical order. Then:

• Permutations 0-5 start with 1
• Permutations 6-11 start with 2
• Permutations 12-17 start with 3
• Permutations 18-23 start with 4

So we can get the first number of permutation N by dividing N by 6 (=3!), and rounding up.

How do we get the next number? Look at the second numbers in permutations 0-5:

• Permutations 0-1 have second number 2.
• Permutations 2-3 have second number 3.
• Permutations 4-5 have second number 4.

We see a similar thing with permutations 6-11:

• Permutations 6-7 have second number 1.
• Permutations 8-9 have second number 3.
• Permutations 10-11 have second number 4.

In general, take the remainder after dividing by 6 earlier, divide that by 2 (=2!), and round up. That gives you 1, 2, or 3, and the second item is the 1st, 2nd or 3rd item left in the list (after you've taken out the first item).

You can keep going in this way. Here's some code that does this:

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

I am not too familiar with the python syntax, but the following code (in 'c') shouldn't be too hard to translate assuming python can do nested for statements.

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]);