CODEWITHSUNDEEP
python
Jakub M.
Jakub M.

Reputation: 33827

Permutations, iterator, recursion and double loop

Here is a function that iterates over permutations of letters in a string:

def permutations(items):
    for x in _permutations_rec('', items, len(items)):
        yield x

def _permutations_rec(current, items, n):
    if len(current) == n:
        yield current
    else:
        for item, other_items in pick_item(items):
            for next_ in _permutations_rec(current+item, other_items, n):
                yield next_

def pick_item(items):
    for i, item in enumerate(items):
        yield item, items[:i] + items[i+1:]

# print permutations
for x in permutations('abc'):
    print x

In _permutations_rec in else part, I have two loops. In the first one I pick the next item that I append to the current string. The second loop iterates the next partial results and yields them. So, the second for is only to handle the iterator for the recursive call and "bubble-up" its results. I have found this pattern frequently when yielding results from recursive calls, e.g. when working with backtracking.

Question:

Is there an idiomatic, elegant way to use only one loop there, instead of two? Although I know there is nothing wrong there with those two loops, maybe there is some iterator kung-fu that would allow me to use only one (the simpler, the better).

Edit:

Upvotes: 1

Views: 276

Answers (3)

Eastsun
Eastsun

Reputation: 18859

A shorter version of your, almost the same:

In [1]: def permutations(items):
   ....:     if len(items) == 0:
   ....:         yield items
   ....:     else:
   ....:         for n in range(len(items)):
   ....:             for ps in permutations(items[:n]+items[n+1:]):
   ....:                 yield ps + items[n:n+1]
   ....:

In [2]: list(permutations('abc'))
Out[2]: ['cba', 'bca', 'cab', 'acb', 'bac', 'abc']

In [3]: list(permutations(list('abc')))
Out[3]:
[['c', 'b', 'a'],
 ['b', 'c', 'a'],
 ['c', 'a', 'b'],
 ['a', 'c', 'b'],
 ['b', 'a', 'c'],
 ['a', 'b', 'c']]

BTW: The equivalent code in Scala as following:

scala> def perm[T](xs: List[T]): Iterator[List[T]] = xs match {
     |   case Nil => Iterator(Nil)
     |   case _ => for(x <- xs.iterator; ys <- perm(xs diff Seq(x))) yield x::ys
     | }
perm: [T](xs: List[T])Iterator[List[T]]
scala> val itr = perm(List.range(0,100))
itr: Iterator[List[Int]] = non-empty iterator

scala> itr.next
res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56,
 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86,
 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99)
scala> perm(1::2::3::Nil) foreach println
List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)

Upvotes: 0

aldeb
aldeb

Reputation: 6828

Because "simple is better than complex", you can simply use itertools.permutations:

from itertools import permutations

for p in permutations('abc'):
    print(p)

Output:

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

If you still want to use your function, yo can use the new python3's yield from statement as @DSM explained.

Upvotes: 3

DSM
DSM

Reputation: 353059

In modern Python, you can use yield from to avoid the innermost loop. Time to upgrade? :^)

    for item, other_items in pick_item(items):
        yield from _permutations_rec(current+item, other_items, n)

Upvotes: 4

Related Questions