代码之家 › 专栏 › 技术社区 › Thomas

存储递归结果

recursion performance algorithm python

Thomas · 技术社区 · 7 年前

我有这个代码,它将打印列表的所有排列:

def permute(iterable,fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            print iterable
        permute(iterable,fixed+1)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

现在我想返回这个结果而不是打印它,我发现最好的方法是将打印的内容存储在文件中,然后读取文件,提取数据并将其放回我返回的列表中:

import string
from random import *
import os

def randString(minLen=16,maxLen=32,charset=string.ascii_letters+string.digits):
    if(minLen>=maxLen):
        maxLen=minLen+1
    return "".join(choice(charset) for x in range(randint(minLen, maxLen)))

def permutations(iterable):
    def permute(iterable,f,fixed=0):
        for i in range(fixed,len(iterable)):
            iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
            if fixed==len(iterable)-1:
                f.write(''.join(iterable)+" ")
            permute(iterable,f,fixed+1)
            iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

    filename="."+randString()+".txt"
    f=open(filename,"w+")
    permute(list(iterable),f)
    f=open(filename,"r+")
    result=[]
    for i in f.read().split():
        result.append([])
        for j in i:
            result[-1].append(j)
    os.remove(filename)
    return result

问题是:这会使代码更长,速度至少慢3倍,因为我将所有排列存储在文件中,然后我必须再次遍历每个排列,将其存储回列表中。

我试图通过使用全局变量或通过在函数中传递结果列表作为参数来解决这个问题,但它不起作用(因为递归)。

以下代码不起作用:

列表为参数

def permute2(iterable,fixed=0,permutations=[]):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            return iterable
        permutation = permute2(iterable,fixed+1)
        if permutation:
            permutations.append(permutation)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]
    return permutations

全局变量

第一

def permute(iterable,fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            global perms
            perms.append(iterable)
        permute(iterable,fixed+1)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

def permutations(iterable):
    global perms
    perms=[]
    permute(list(iterable))
    return perms

第二

def permute(iterable,fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            addPermutation(iterable)
        permute(iterable,fixed+1)
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

def addPermutation(item):
    addPermutation.perms.append(item)

def permutations(iterable):
    addPermutation.perms=[]
    permute(list(iterable))
    return addPermutation.perms

这三个错误代码几乎都做了相同的事情:它们返回一个包含n!乘以第一次排列。

有没有办法解决这个问题,或者我必须在文件中使用代码?

编辑: 在@DavidKemp和@uwain12345的评论之后,我尝试使用一个类。

def permutations(iterable):
    class Permut:
        def __init__(self, iterable):
            self.iterable = list(iterable)
            self.permutations = []
            self.permute()

        def permute(self,fixed=0):
            for i in range(fixed,len(self.iterable)):
                self.iterable[fixed:] = [self.iterable[i]] + self.iterable[fixed:i] + self.iterable[i+1:]
                if fixed==len(self.iterable)-1:
                    self.permutations.append(self.iterable)
                self.permute(fixed+1)
                self.iterable[fixed:] = self.iterable[fixed+1:i+1] + [self.iterable[fixed]] + self.iterable[i+1:]

    p = Permut(list(iterable))
    return p.permutations

然而,我仍然得到了与上面没有工作的代码完全相同的结果(n!次第一次排列)。

2 回复 | 直到 7 年前

Patrick Haugh 7 年前

你的问题是改变列表 iterable 这是一个糟糕的策略。对所做的更改 iterbale 将始终被反射,因为它们都是相同的对象。如果我们改用元组,就可以避免这种情况。下面是我想到的递归置换代码:

def permute(iterable):
    iterable = tuple(iterable)
    if len(iterable) <= 1:
        yield iterable
        return
    for i, x in enumerate(iterable):
        for sub_permutation in permute(iterable[:i] + iterable[i+1:]):
            yield (x,) +  sub_permutation

Hai Vu 7 年前

除非这是一个练习,否则我建议你遵循Patrick Haugh的建议并使用 itertools.permutations 。然而,如果你仍然坚持自己滚动,那么 print ,使用 yield 关键词:

def permute(iterable, fixed=0):
    for i in range(fixed,len(iterable)):
        iterable[fixed:] = [iterable[i]] + iterable[fixed:i] + iterable[i+1:]
        if fixed==len(iterable)-1:
            yield iterable
        for e in permute(iterable,fixed+1):
            yield e
        iterable[fixed:] = iterable[fixed+1:i+1] + [iterable[fixed]] + iterable[i+1:]

# Test out
for e in permute(['a', 'b', 'c']):
    print(e)

输出:

['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['b', 'c', 'a']
['c', 'a', 'b']
['c', 'b', 'a']

注释

这个 产量 语句将一次“返回”一项,但不会退出函数。此函数返回一个生成器,因此请阅读Python生成器以了解更多信息。

考虑以下块:

for element in permute(iterable, fixed + 1):
    yield element

如果您使用的是Python 3,那么可以将该块替换为

yield from permute(iterable, fixed + 1)