python非递归全排列实现方法

当我们需要对一个列表进行全排列时,通常会使用递归的方法,但是递归的深度随着列表长度的增加而增加,可能会导致栈溢出的问题。因此,我们可以使用非递归的方法实现列表的全排列。

下面是使用Python实现非递归全排列的完整攻略:

问题描述

给定一个列表nums,求出它的全排列。列表中元素不重复,且元素个数小于等于10。

示例输入:[1,2,3]

示例输出:

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

解决方法

1.交换法

我们可以用交换的方式对列表进行全排列。

具体实现步骤如下:

  1. 初始化一个res列表用来存储全排列结果,初始化一个stack列表用来模拟递归栈。

  2. 把初始列表nums入栈(列表中的元素均未交换)

  3. 当栈不为空时,弹出一个元素,初始化一个used集合,表示当前所取过的元素。

  4. 对于弹出的元素,从0开始遍历到最后一个元素,如果这个元素没有被取过,那么就交换元素并把它入栈,否则跳过。

  5. 如果遍历到了列表的末尾,把当前元素存储到res列表中。

  6. 重复执行3-5步,直到栈为空。

def permute(nums):
    res = []
    stack = [(nums, 0)]
    while stack:
        lst, i = stack.pop()
        if i == len(lst):
            res.append(lst)
        else:
            used = set()
            for j in range(i, len(lst)):
                if lst[j] not in used:
                    used.add(lst[j])
                    lst[i], lst[j] = lst[j], lst[i]
                    stack.append((lst[:], i + 1))
                    lst[i], lst[j] = lst[j], lst[i]
    return res

2. 迭代法

迭代法相对于交换法来说实现代码更加简洁。

具体实现步骤如下:

  1. 定义一个生成器函数gen(nums)。

  2. 首先定义一个长度为n(n为nums中元素个数)的数组p,用来存储当前输出排列。

1) 首先将每个元素的前一个元素下标存入p,并把p[0]设置为-1,指示结束排列。

2) 将每个元素i前面的所有元素集合A放入字典D中,并用0初始化,用于记录集合A已输出排列的数量。

例如,对于列表[1,2,3],字典D应该为{1:0, 2:0, 3:0}。

  1. 在gen函数中使用while循环遍历,每次得到一个排列,然后在p中查找字典D对应集合已经输出的排列数量加一,然后再继续查找,依次类推直到数字排列结束。
def gen(nums):
    n = len(nums)
    p = [-1] + list(range(n-1))
    D = {i:0 for i in nums}
    yield [nums[p[i+1]] for i in range(n-1)]
    i = 0
    while i < n-1:
        D[nums[p[i+1]]] += 1
        while p[i+1] < i + 1:
            p[i+1] += 1
        if D[nums[p[i+1]]] < i + 1:
            p[i+1], p[i+D[nums[p[i+1]]]+1] = p[i+D[nums[p[i+1]]]+1], p[i+1]
            yield [nums[p[i+1]]] + [nums[p[j+1]] for j in range(i)]
            i = 0
        else:
            p[i+1:] = [p[i]] + p[i+1:-1]
            i += 1

def permute(nums):
    return [x for x in gen(nums)]

示例说明

例如,对于列表[1,2,3],我们可以分别使用上述的两个方法来得到全排列。

使用交换法:

nums = [1,2,3]
print(permute(nums))

输出:

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

使用迭代法:

nums = [1,2,3]
print(permute(nums))

输出:

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

可以看到,输出结果都是正确的。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python非递归全排列实现方法 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • vue draggable组件实现拖拽及点击无效问题的解决

    Vue Draggable 组件实现拖拽及点击无效问题的解决攻略 标题 在这个攻略中,我们将详细讲解如何使用 Vue Draggable 组件实现拖拽功能,并解决由此引发的点击无效问题。 示例说明1: 基本拖拽功能 首先,我们需要安装 Vue Draggable 组件。可以通过以下命令在项目中进行安装: npm install vuedraggable 安装…

    other 2023年6月28日
    00
  • Elasticsearch属性单词常用解析说明

    首先我们需要了解Elasticsearch中文本字段索引的概念。在Elasticsearch中,文本字段需要通过分析器进行预处理,生成数字或字符串类型数据才能进行索引和查询。分析器会将文本字段拆分成多个单词,然后对这些单词进行解析、标准化,最后生成索引的词条。 以下是常用的属性单词和它们的解析说明: analyzer:指定分析器,用于预处理文本。默认值是 s…

    other 2023年6月25日
    00
  • 分享6个Go处理字符串的技巧小结

    分享6个Go处理字符串的技巧小结 在Go语言中,字符串是经常使用的数据类型,因此掌握一些处理字符串的技巧可以提高工作效率。以下是我总结出来的6个处理字符串的技巧,希望能够对你有所帮助。 技巧1:获取字符串长度 获取字符串长度可以使用len()函数,示例代码如下: str := "hello" length := len(str) fmt.…

    other 2023年6月20日
    00
  • Simple Java Mail邮件发送实现过程解析

    Simple Java Mail邮件发送实现过程解析 Simple Java Mail是一个用于发送电子邮件的Java库。它提供了简单易用的API,可以轻松地实现邮件发送功能。下面是使用Simple Java Mail发送邮件的完整攻略。 步骤1:添加依赖 首先,你需要在你的Java项目中添加Simple Java Mail的依赖。你可以在你的项目的构建文件…

    other 2023年7月28日
    00
  • [转]dev C++编写windows程序遇到问题

    [转]dev C++编写windows程序遇到问题 在使用dev C++编写Windows程序的过程中,有一些常见的问题需要注意。 无法打开头文件 如果在代码中引入了头文件,但是编译时却提示无法找到该头文件,可能是因为dev C++没有正确设置头文件路径。 解决方法: 打开dev C++,点击菜单栏的“Tools”,选择“Compiler Options”。…

    其他 2023年3月28日
    00
  • codevs 2602 最短路径问题——良心题解

    下面是“codevs 2602 最短路径问题——良心题解”的完整攻略,包括题目描述、解题思路和两个示例等方面。 题目描述 给定一个 $n$ 个点 $m$ 条边的有向图,每条边有一个非负权值。请你求出从起点 $s$ 到终点 $t$ 的最短路径长度。 解题思路 本题可以使用 Dijkstra 算法来解决。具体来说,我们可以使用一个数组 dist 来记录起点到各个…

    other 2023年5月5日
    00
  • Go单元测试工具gomonkey的使用

    Go单元测试工具gomonkey的使用攻略 简介 gomonkey是一个用于Go语言的单元测试工具,它可以帮助开发者在测试过程中模拟和修改函数的行为,以便更好地进行单元测试。本攻略将详细介绍gomonkey的使用方法,并提供两个示例说明。 安装 首先,你需要使用go get命令安装gomonkey包: go get github.com/agiledrago…

    other 2023年7月29日
    00
  • MySQL left join操作中on和where放置条件的区别介绍

    MySQL 的 left join 操作中,on 和 where 都可以放置条件,但二者有一定的区别。 on 语句是在连接两个表的时候使用的,用来指定连接的条件;where 语句则是在连接之后对结果进行筛选的过程中使用的,用来指定筛选条件。 具体来说,常见的使用场景是:两个表之间有一个公共字段关联,通过 left join 进行连接,right table …

    other 2023年6月27日
    00
合作推广
合作推广
分享本页
返回顶部