数字全排列

zoomdong 发布于2019-08-15 15:54 / 943人阅读

摘要：数字全排列问题描述给一个不重复的数字数组，写一个程序，输出全排列。那么两个数字的全排列怎么算呢，以为例，就是第一个数字为的剩下的数的全排列第一个数字为的剩下的数的全排列。依次类推到个数字的全排列设数组，设的全排列为，设。

数字全排列 问题描述

给一个不重复的数字数组，写一个程序，输出全排列。

比如给定数组：

[1, 2, 3]

输出：

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

解决思路

这个问题很经典，接下来尝试使用数学归纳法的思想来解决这个问题。

在中学的时候，我们就知道一个长度为n的数列有n!个排列。因为第一个数字有n种情况，第二个数字有n-1种情况，第三个数字有n-2种情况……第n个数字只有一种情况了，用公式表示就是n*(n-1)*(n-2)….*1 = n!

我们换一个思维来考虑，以数组[1,2,3]为例，它的全排列为：

第一个数字为1的其他两个数字的全排列 + 第一个数字为2的其他两个数字的全排列 + 第一个数字为3的其他两个数字的全排列。

那么两个数字的全排列怎么算呢，以[1,2]为例，就是：

第一个数字为1的剩下的数的全排列 + 第一个数字为2的剩下的数的全排列。

因为剩下的只有一个数，就不用继续了，到这就可以输出了。

依次类推到n个数字的全排列：

设数组 p = {r1, r2, r3, r4, r5…., rn}，设p的全排列为perm(p)，设pn = p - {rn}。

那么perm(p) = { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }。

同样思路，也可以算出perm(p1), perm(p2), perm(p3)……perm(pn)。

继续，就可以使用递归求解了，递归的出口就是perm求的全排列数组里面只有一个值。

代码实现

下面是java的实现代码：

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        Test t = new Test();
        t.perm(arr, 0, arr.length);
    }
    
      //求数组全排列
    public void perm(int[] nums, int start, int len) {
        //判断递归出口，当start == len - 1时，也就是要做的全排列只有一个值 ，那么就可以输出了
        if(start == len - 1) {
            System.out.println(Arrays.toString(nums));
        }else {
            /*
             * 没有到递归出口时，这一段代码是关键
             * for循环模拟的是：
             * { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }
             * 从r1, r2, r3 一直到 rn 作为第一位，求剩下的全排列
             */
            for(int i = start; i < len; i++) {
                swap(nums, start, i);//通过交换，依次将每个数放在第一位
                perm(nums, start + 1, len);//递归调用
                swap(nums, start, i);//交换回来，保证原数组不会变，以进行下一轮全排列
            }
        }
    }
    
    //交换数组中的两个值
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

输出结果：

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

参考：

http://www.cnblogs.com/nokiag...

https://blog.csdn.net/randyji...

云服务器 GPU云服务器字符串全排列 java 全排列数列字符串全排列算法最快的全排列算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69313.html

[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0
javascript解三阶幻方谜题

摘要：谜题三阶幻方。试将这个不同整数填入一个的表格，使得每行每列以及每条对角线上的数字之和相同。列出所有的整数填充方案，然后进行过滤。 /* * 谜题--三阶幻方。 * 试将1~9这9个不同整数填入一个3×3的表格，使得每行、每列以及每条对角线上的数字之和相同。 * 策略 * 穷举搜索。列出所有的整数填充方案，然后进行过滤。 * 亮点为递归函数getPermut...

Render 2019-08-21 10:24 评论0 收藏0
Python秒算24点，行还是不行？

摘要：周末闲来无事，看到隔壁家的老王在和隔壁家的媳妇玩点，就进屋看了看。发现老王是真不行啊，那不行，这也不行。什么是点我们先来约定下老王和他媳妇玩的点规则给定个任意数字，然后通过，将这个数字计算出。 showImg(https://segmentfault.com/img/remote/1460000019900384?w=472&h=200); 周末闲来无事，看到隔壁家的老王在和隔壁家的媳...

saucxs 2019-07-31 11:31 评论0 收藏0
[Leetcode] Permutations 全排列

摘要：每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...

scq000 2019-08-14 12:31 评论0 收藏0