2

我正在尝试编写一段代码，它将生成一个排列，或者一些以递归方式都不同的字符系列。

def getSteps(length, res=[]):
    if length == 1: 
        if res == []:
            res.append("l")
            res.append("r")
            return res
        else:
            for i in range(0,len(res)):
                res.append(res[i] + "l")
                res.append(res[i] + "r")
            print(res)
            return res
    else:
        if res == []:
            res.append("l")
            res.append("r")
            return getSteps(length-1,res)
        else:
            for i in range(0,len(res)):
                res.append(res[i] + "l")
                res.append(res[i] + "r")
            print(res)
            return getSteps(length-1,res)

def sanitize(length, res):
    return [i for i in res if len(str(i)) == length]

print(sanitize(2,getSteps(2)))

所以这会返回

“LL”、“LR”、“RR”、“RL”或系列的一些排列。

我可以立即看到这个函数可能运行得很慢，因为我必须遍历整个数组。我试图让这个过程尽可能高效，但这是我能做到的。我知道在跑步过程中会发生一些不必要的事情，但我不知道如何让它变得更好。所以我的问题是：我会做些什么来提高效率并减少这段代码的运行时间？

编辑 = 我希望能够将此代码移植到 java 或其他语言，以便理解递归的概念，而不是使用外部库，并且在不理解的情况下解决我的问题。

4

3 回答 3

2

你的设计坏了。如果你getSteps再次调用res，它不会是一个空列表，它会从最后一次调用中留下垃圾。

我认为您想递归生成排列，但我不明白您将使用该getSteps函数的位置

这是一个简单的递归函数

def fn(x):
    if x==1:
        return 'LR'
    return [j+i for i in fn(x-1) for j in "LR"]
于 2013-09-19T01:21:33.223 回答
1

有没有办法将二进制方法和递归方法结合起来？

是的，@gribbler非常接近附有该评论的帖子中的内容。他只是按照“另一个顺序”将这些碎片拼凑在一起。

如何n按递增顺序（当被视为二进制整数时）构造长​​度的所有位串？好吧，如果你已经拥有了所有长度的位串n-1，你可以在它们前面加上前缀0，然后再在它们前面加上前缀1。就这么容易。

def f(n):
    if n == 0:
        return [""]
    return [a + b for a in "RL" for b in f(n-1)]

print(f(3))

印刷

['RRR', 'RRL', 'RLR', 'RLL', 'LRR', 'LRL', 'LLR', 'LLL']

替换R为0, 和L,1得到从 0 到 7 的 8 个二进制整数，按升序排列。

于 2013-09-19T02:26:08.257 回答
0

你应该看看 itertools。那里有一个名为的函数permutations，它完全符合您在这里想要实现的目标。

于 2013-09-19T01:18:03.053 回答