1

这是一个迭代字符串中字母排列的函数：

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

在某种程度上_permutations_rec，else我有两个循环。在第一个中，我选择附加到current字符串的下一个项目。第二个循环迭代下一个部分结果并产生它们。因此，第二个for只是处理递归调用的迭代器并“冒泡”它的结果。在递归调用产生结果时，我经常发现这种模式，例如在使用backtracking时。

问题：

有没有一种惯用的、优雅的方式来只使用一个循环，而不是两个？虽然我知道这两个循环没有任何问题，但也许有一些迭代器功夫可以让我只使用一个（越简单越好）。

编辑：

  • 我知道itertools.permutations，我permutations的只是一个玩具例子
4

3 回答 3

4

在现代 Python 中，您可以使用yield from来避免最内层循环。是时候升级了？:^)

    for item, other_items in pick_item(items):
        yield from _permutations_rec(current+item, other_items, n)
于 2013-04-20T23:51:03.927 回答
3

因为“简单胜于复杂”，您可以简单地使用itertools.permutations：

from itertools import permutations

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

输出：

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

如果你仍然想使用你的函数，你可以使用@DSM 解释yield from的新 python3 的语句。

于 2013-04-20T23:45:01.230 回答
0

您的较短版本，几乎相同：

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

顺便说一句：Scala 中的等效代码如下：

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)
于 2013-04-21T01:52:57.403 回答