2

I am trying to find all the permutations of a list of integers from a specific range using recursion. For example, if lst = [0,1,2], then a call to def permute(lst, 0, 1) should return [[0,1], [1,0]] in that format. Similarly, a call to permute(lst, 0, 2) should return [[0,1,2], [0,2,1]...].

So far, my code only works to find permutations of a whole list, from index 0 to len(lst):

def permute(lst, low, high):
    if low == high:
        print(lst)
    for index in range(low, high + 1):
            lst[index], lst[low] = lst[low], lst[index]
            permute(lst, low + 1, high)
            lst[index], lst[low] = lst[low], lst[index]

Where low = 0 and high is the len(lst).

If I change the indices in this code, I do not get a correct output. Any suggestion on how to take the indices into account?

AChampion
  • 29,683
  • 4
  • 59
  • 75
swing1234
  • 233
  • 1
  • 3
  • 13
  • You are changing `lst`, you probably need to create a new list to hold the permutation and `return` it. Why use recursion? – AChampion Oct 12 '17 at 04:53
  • I don't think it can be easily done, without destroying the elegance of the algorithm. You _could_ probably do it by giving `permute` an extra arg that maintains the original `low` arg, but that's a bit clunky. The simple solution is to have another function that acts as an interface to your recursive `permute` function. So you call the interface function and it calls `permute` with a slice of the list. – PM 2Ring Oct 12 '17 at 04:59
  • If you don't need recursion, you can use `itertools.permutation(lst[low:high+1])`. – import random Oct 12 '17 at 05:01
  • BTW, there's an ancient but excellent iterative permutation algorithm that (unlike `itertools.permutations`) handles repeated elements intelligently. Please see [here](https://stackoverflow.com/a/43014919/4014959) for details. – PM 2Ring Oct 12 '17 at 05:02
  • I implemented a version that uses an extra arg. It _is_ a little clunky, but it's not as bad as I thought it might be. ;) – PM 2Ring Oct 12 '17 at 06:20

2 Answers2

0

You can do this with an inner recursive function, e.g.:

def permute(lst, start, end):
    def permutations(l):
        if len(l) <= 1:
            return [l]
        a = []
        for p in permutations(l[:-1]):
            for i in range(len(l)):
                a.append(p[i:] + [l[-1]] + p[:i])
        return a
    return permutations(lst[start:end+1])

In []
lst = [0,1,2,3,4]
permute(lst, 0, 1)

Out[]:
[[0, 1], [1, 0]]

In []
permute(lst, 0, 2)

Out[]:
[[0, 1, 2], [1, 2, 0], [2, 0, 1], [1, 0, 2], [0, 2, 1], [2, 1, 0]]
AChampion
  • 29,683
  • 4
  • 59
  • 75
  • One minor downside of using a nested function is that the inner function is redefined every time the outer function is called, rather than being defined once, when the script starts up. But it's a fairly small function, so hopefully that's not a big deal. – PM 2Ring Oct 12 '17 at 06:19
  • Good point, there's no need for this to be an inner function other that to hide it - there's no closure, so just have 2 global functions. – AChampion Oct 12 '17 at 06:28
0

Here's a version of your code that uses an extra argument to remember the start position of the list. I changed your function into a recursive generator, so it yields the values, rather than printing them. I also changed high to stop, which is consistent with the convention used in Python's slicing eg, seq[start:stop], and in range(start, stop).

def permute(lst, start, stop, low=None):
    if low == stop - 1:
        yield lst[start:stop]
    if low is None:
        low = start
    for index in range(low, stop):
            lst[index], lst[low] = lst[low], lst[index]
            for t in permute(lst, start, stop, low + 1):
                yield t
            lst[index], lst[low] = lst[low], lst[index]

# Test
lst = list(range(5))
print(list(permute(lst, 1, 4)))

for t in permute(lst, 0, 3):
    print(t)

output

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 1, 0]
[2, 0, 1]

That code works identically on Python 2 & 3, although in Python 3 it can be made a little more efficient (and more compact) by using the yield from syntax. Replace that for t in permute... loop with

yield from permute(lst, start, stop, low + 1)

In Python 3 you can also create a list of the values in a more compact way:

[*permute(lst, 1, 4)]

Finally, here's another recursive generator built from your algorithm, but it permutes the whole list. Of course, you can call it with an interface function to permute a sublist.

def permuter(lst):
    if not lst:
        yield lst
    for index in range(len(lst)):
        lst[index], lst[0] = lst[0], lst[index]
        first = lst[:1]
        for t in permuter(lst[1:]):
            yield first + t
        lst[index], lst[0] = lst[0], lst[index]

def permute(lst, start, stop):
    yield from permuter(lst[start:stop])

lst = list(range(5))
print(list(permute(lst, 1, 4)))
PM 2Ring
  • 54,345
  • 6
  • 82
  • 182
  • Helpful, but I was looking for a solution that does not change the original parameters def permute(lst, low, high) – swing1234 Oct 12 '17 at 20:10
  • @sweeper123 As I said in the comment on your question I don't think it's possible to do this without having some way of tracking the original `low`. We don't need to do that with an extra arg, but that's a convenient way; another option (apart from using a global, which would be gross) is to use a function attribute. – PM 2Ring Oct 12 '17 at 20:48
  • @sweeper123 And of course it's best in Python to avoid recursion if you don't really need it (eg when processing recursive data structures) because unlike some other languages Python cannot optimize recursion. And it has a limit to how deep recursion can go, although that won't be a problem here, since if you try to permute a list of 1000 elements you'll have other problems before you hit the recursion limit, like the heat death of the universe. ;) – PM 2Ring Oct 12 '17 at 20:52