Permutations, iterator, recursion and double loop

Question

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:

I know itertools.permutations, my permutations is just a toy example

About your edit: sorry, that was just for saying in case you didn't know... — aldeb
– aldeb, Commented Apr 21, 2013 at 0:05
Sorry me, I should have made it clear earlier in my question — Jakub M.
– Jakub M., Commented Apr 21, 2013 at 0:06

DSM · Accepted Answer · 2013-04-20 23:51:03Z

4

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)

answered Apr 20, 2013 at 23:51

DSM

355k67 gold badges606 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jakub M. Over a year ago

When I was young, python2.7 was sufficient for everything! What this world turned to! :)

Community · Accepted Answer · 2017-05-23 11:50:15Z

3

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.

edited May 23, 2017 at 11:50

CommunityBot

11 silver badge

answered Apr 20, 2013 at 23:45

aldeb

6,8667 gold badges28 silver badges49 bronze badges

Comments

Eastsun · Accepted Answer · 2013-04-21 02:16:05Z

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)

bterwijn · Accepted Answer · 2025-04-22 18:09:38Z

Some optimizations on the suggestion by @Eastsun are:

Use a single mutable list to store each permutation. This is faster than repeatedly copying immutable strings as a result of the '+' operator, even when converting the list to string at the end.
Swap values in the items list to avoid expensive items[:i]+items[i+1:] copies with O(n) complexity, and then an undo-swap is required when backtracking.

from typing import Iterator

def permutations(items: str) -> Iterator[list[str]]:
    yield from _permutations_rec(list(items), 0)

def _permutations_rec(items: list[str], index: int) -> Iterator[list[str]]:
    if index == len(items):
        yield items
    else:
        for i in range(index, len(items)):
            items[index], items[i] = items[i], items[index]  # swap
            yield from _permutations_rec(items, index + 1)
            items[index], items[i] = items[i], items[index]  # backtrack

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

Collectives™ on Stack Overflow

Permutations, iterator, recursion and double loop

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related