首页 文章

在python中使用递归查找list int的排列时考虑索引？

提问于
浏览 次
2

我试图使用递归找到特定范围内的整数列表的所有排列 . 例如，如果 lst = [0,1,2] ，那么对 def permute(lst, 0, 1) 的调用应该以该格式返回 [[0,1], [1,0]] . 同样，对 permute(lst, 0, 2) 的调用应该返回 [[0,1,2], [0,2,1]...] .

到目前为止，我的代码只能查找整个列表的排列，从索引0到len（lst）：

def permute(lst, low, high):
    if low == high:
        print(lst)
    for index in range(low, high + 1):
            lst[index], lst[low] = lst[low], lst[index]
            permute(lst, low + 1, high)
            lst[index], lst[low] = lst[low], lst[index]

low = 0 和 high 是 len(lst) .

如果我更改此代码中的索引，我得不到正确的输出 . 关于如何考虑指数的任何建议？

python algorithm recursion

2 回答

  • 0

    你可以用内部递归函数来做到这一点，例如：

    def permute(lst, start, end):
    def permutations(l):
        if len(l) <= 1:
            return [l]
        a = []
        for p in permutations(l[:-1]):
            for i in range(len(l)):
                a.append(p[i:] + [l[-1]] + p[:i])
        return a
    return permutations(lst[start:end+1])

In []
lst = [0,1,2,3,4]
permute(lst, 0, 1)

Out[]:
[[0, 1], [1, 0]]

In []
permute(lst, 0, 2)

Out[]:
[[0, 1, 2], [1, 2, 0], [2, 0, 1], [1, 0, 2], [0, 2, 1], [2, 1, 0]]
    回复于
  • 0

    这是您的代码版本，它使用额外的参数来记住列表的起始位置 . 我将您的函数更改为递归生成器，因此它生成值，而不是打印它们 . 我还将 high 更改为 stop ，这与Python的切片中使用的约定一致，例如 seq[start:stop] 和 range(start, stop) .

    def permute(lst, start, stop, low=None):
    if low == stop - 1:
        yield lst[start:stop]
    if low is None:
        low = start
    for index in range(low, stop):
            lst[index], lst[low] = lst[low], lst[index]
            for t in permute(lst, start, stop, low + 1):
                yield t
            lst[index], lst[low] = lst[low], lst[index]

# Test
lst = list(range(5))
print(list(permute(lst, 1, 4)))

for t in permute(lst, 0, 3):
    print(t)

    output

    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 1, 0]
[2, 0, 1]

    该代码在Python 2和3上的工作方式相同，但在Python 3中，通过使用 yield from 语法可以使其更高效（并且更紧凑） . 将 for t in permute ...循环替换为

    yield from permute(lst, start, stop, low + 1)

    在Python 3中，您还可以以更紧凑的方式创建值列表：

    [*permute(lst, 1, 4)]

    最后，这是根据您的算法构建的另一个递归生成器，但它会置换整个列表 . 当然，您可以使用接口函数调用它来置换子列表 .

    def permuter(lst):
    if not lst:
        yield lst
    for index in range(len(lst)):
        lst[index], lst[0] = lst[0], lst[index]
        first = lst[:1]
        for t in permuter(lst[1:]):
            yield first + t
        lst[index], lst[0] = lst[0], lst[index]

def permute(lst, start, stop):
    yield from permuter(lst[start:stop])

lst = list(range(5))
print(list(permute(lst, 1, 4)))
    回复于

相关问题