正文 

当前位置： 首页 > 代码 > java教程

算法设计：全排列算法代码实现(代码片段)

sunriseblogs sunriseblogs     2023-01-13     127

关键词：

在上星期的算法设计课程的学习中，我们学习了两种全排列算法，该算法用于求出数组1,2,3,...,n的所有可能的排列，今天我们就来看看这个算法的具体代码实现。

 

1. 第一种算法

第一种算法和我们现实生活中习惯的方法较为相似，以1,2,3为例，我们先写出第一种排列123，然后将2与3交换，得到132；再回到123，交换1与2得到213，再将1与3交换.....直到得到所有的排列。

技术分享图片

 

该算法伪码如下：

PERMUTATIONS1(int n)：

  1. for j←1 to n
  2. 　　a[j]←j
  3. end for
  4. perm1(1)

perm1(int m):

  1. if m = n then output a[1...n]
  2. else
  3. 　　for j←m to n
  4. 　　　　互换a[j]和a[m]
  5. 　　　　perm1(m+1)
  6. 　　　　互换a[j]和a[m]
  7. 　　end for
  8. end if

 

具体代码实现如下:

 

 1 //第一种排列生成算法
 2 public class Permutations1 
 3     private int a[] = new int[50];    //声明存放数据的数组
 4     private int length = 0;
 5     //构造函数
 6     public Permutations1(int length)
 7     
 8         this.length = length;
 9         for(int i=1;i<=length;i++)
10             a[i] = i;
11     
12     
13     //执行全排列算法
14     public void perm1(int n)
15     
16         if(n == length)
17             this.dispArray();    //到最底层时输出排列结果
18         else 
19         
20             for(int i=n;i<=length;i++)
21             
22                 this.swap(i, n);  //交换两数的值
23                 perm1(n + 1);    //递归执行perm1
24                 this.swap(i, n);    //恢复位置
25             
26         
27     
28     
29     //交换数组中两数的值
30     public void swap(int x, int y)
31     
32         int t = a[x];
33         a[x] = a[y];
34         a[y] = t;
35     
36     
37     //输出排列
38     public void dispArray()
39     
40         for(int i=1;i<=length;i++)
41             System.out.print(a[i]);
42         System.out.println();
43     
44

 

 

2. 第二种算法

第二种算法比较类似于我们中学学的排列组合，还是以1,2,3为例，我们先确定第一个位置的数字3，再确定第二个位置的数字2，再确定最后一个位置的数字1，然后我们再向前恢复，再次确定第二个位置的数字....直到得到所有的排列。

技术分享图片

 

该算法伪码如下：

PERMUTATIONS2(int n):

  1. for j←1 to n
  2. 　　a[j]←0
  3. end for
  4. perm2(n)

perm2(int m):

  1. if m=0 then output a[1...n]
  2. else
  3. 　　for j←1 to n
  4. 　　　　if a[j]=0 then
  5. 　　　　　　a[j]←m
  6. 　　　　　　perm2(m-1)
  7. 　　　　　　a[j]←0
  8. 　　　　end if
  9. 　　end for
  10. end if

具体代码如下：

 1 //第二种排列生成算法
 2 public class Permutations2 
 3     private int a[] = new int[50];    //声明存放数据的数组
 4     private int length = 0;    //声明数组长度
 5     
 6     //构造函数
 7     public Permutations2(int length)
 8     
 9         this.length = length;
10         for(int i = 1;i<=length;i++)
11             a[i] = 0;    //将所有元素记为零
12     
13     
14     public void perm2(int n)
15     
16         if(n == 0)
17             this.dispArray();
18         else 
19         
20             for(int i=1;i<=length;i++)
21             
22                 if(a[i] == 0)    //如果该位为空
23                     
24                         a[i] = n;    //将n的值赋给该位
25                         perm2(n - 1);    //递归执行
26                         a[i] = 0;    //恢复
27                     
28             
29         
30     
31     
32     //输出排列
33     public void dispArray()
34     
35         for(int i=1;i<=length;i++)
36             System.out.print(a[i]);
37         System.out.println();
38     
39

 

全排列算法实现(代码片段)

全排列算法实现方法1：插入法，取字符串的第一个元素放到集合res，后面将字符串的其余元素依次插入到当前集合res的前，中，后。importjava.util.ArrayList;publicclassFullPermutation1publicstaticArrayList<String>f(Strings)Ar 查看详情

算法习题---字符串的全排序列(代码片段)

...，比如下图为1,2,3的排列枚举树，此树和我们这里介绍的算法完全一致；二：全排列实现思路(1)n个元素的全排列=（n-1个元素的全排列 查看详情

全排列(代码片段)

全排列回溯算法之排列树一问题描述给出一串字符的全排列二问题分析采用回溯算法之排列树三代码实现packagebacktracking_perm;importjava.io.BufferedWriter;importjava.io.FileWriter;importjava.io.IOException;importjava.util.Arrays;importjava.util.LinkedList 查看详情

算法剑指offerii083.没有重复元素集合的全排列｜46.全排列（多语言实现）(代码片段)

非常感谢你阅读本文~欢迎【👍点赞】【⭐收藏】【📝评论】~放弃不难，但坚持一定很酷~希望我们大家都能每天进步一点点~本文由二当家的白帽子：https://le-yi.blog.csdn.net/博客原创~文章目录剑指OfferII083.没有重复... 查看详情

全排列算法（递归）(代码片段)

　　全排列算法是一种经典的递归算法。例如集合a，b，c的全排列为（a，b，c）、（a，c，b）、（b，a，c）、（b，c，a）、（c，b，a）、（c，a，b）共3！种。　　递归法求解的思路是先固定第一个元素，求剩下的全排列，求剩... 查看详情

算法——全排列

全排列的算法，在文章JavaScript全排列的六种算法中介绍了6种，这里我只记录下我已经理解的递归实现的全排列算法。关于递归实现的全排列算法参考了文章全排列算法的JS实现。字符串的全排列算法下面是代码：1functionquanpailie(... 查看详情

常见的算法问题全排列(代码片段)

在我参加蓝桥杯时发现大多数问题都可以采用暴力破解所以这个时候我就想进行一下总结：关于全排列问题的通用解法，比如：（无重复全排列）（有重复的选取）（从N个数中选取m个数然后进行排列的问题）我这里尝试总结一... 查看详情

算法设计与分析5.3数字排列(代码片段)

★题目描述给两个正整数A和B，请问通过重新排列A获得小于或等于B的最大数字是多少(不含前导0)？★输入格式输入的第一行两个数字A和B，保证这两个数字在int范围内。★输出格式输出A重新排列后小于或等于B的最大整数(不含前... 查看详情

算法9-----输出全排列（递归）(代码片段)

1、题目：给定一个字符串，输出所有的字典序。如：输入字符串：‘ac‘，输出：[‘ac‘,‘ca‘]输入字符串：‘abc‘,输出：[‘abc‘,‘acb‘,‘bac‘,‘bca‘,‘cab‘,‘cba‘]输入字符串：‘acc‘，输出：[‘acc‘,‘cac‘,‘cca‘]2、... 查看详情

全排列算法的全面解析(代码片段)

...全排列是一个比较常见问题，如果是一个比较喜欢考算法的公司（貌似一些大公司都比较喜欢考算法），那么估计就会考察应聘者这个全排列的问题了（就算不让你编写完整代码，也会让你描述大致的思路... 查看详情

java与算法之-数字全排列(代码片段)

全排列是指n个数(或其他字符)所有可能的排列顺序，例如123三个数字的全排列是123132213231312321那么问题来了，任意输入一个大于1的数字n，列出1-n这n个数字的全排列。如果尝试手动列举一下123的全排列，会发现通常我们会在头脑... 查看详情

字符串去反复全排列算法(代码片段)

【题目描写叙述】输入一个字符串，打印出该字符串中字符的全部排列。比如输入字符串abc，则输出由字符a、b、c所能排列出来的全部字符串abc、acb、bac、bca、cab和cba。【分析】从集合中依次选出每个元素。作为排列... 查看详情

算法问题寻找全排列的下一个数(代码片段)

寻找全排列的下一个数摘自漫画算法：题目：给出一个正整数，找出这个正整数所有数字全排列的下一个树。说的通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。例子：如果输入12345，则... 查看详情

算法问题寻找全排列的下一个数(代码片段)

寻找全排列的下一个数摘自漫画算法：题目：给出一个正整数，找出这个正整数所有数字全排列的下一个树。说的通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。例子：如果输入12345，则... 查看详情

全排列的实现方法--递归&字典序(代码片段)

...f1a;背景全排列在很多笔试都有应用，是一个很常见的算法，关于这类的题目变化很多。这种算法的得到基于以下的分析思路。 给定一个具有n个元素的集合（n>=1），要求输出这个集合中元素的所有可能... 查看详情

leetcode-46.全排列--回溯算法--python(代码片段)

全排列问题使用回溯算法解决思路：定义res列表存放最后的结果定义track列表构建排列存放每次的排列在backtrack函数中，for循环中1.满足条件，加入res，2.做选择：track.append(nums[i])3.回溯函数：backtrack(nums,trac... 查看详情

next_permutation(全排列算法)(代码片段)

https://blog.csdn.net/c18219227162/article/details/50301513#include<iostream>#include<algorithm>usingnamespacestd;intmain()intans[4]=1,2,3,4;sort(ans,ans+4);/*这个sort可以不用，因为1，2，3，4已经排好 查看详情

leetcode46.全排列（回溯算法解决）(代码片段)

截止到目前我已经写了600多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ提取码：6666全排列... 查看详情