本文主要是介绍Java实现STL中的全排列函数next_permutation(),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、引言
二、全排列函数next_permutation()
三、next_permutation()的使用
四、Java实现next_permutation()
五、使用next_permutation()实现全排列
一、引言
相信很多小伙伴们都做过全排列的算法题,输入一个n,输出1~n的全排列。对于这个问题,最经典的是实现方法应该是通过回溯实现 。
代码如下
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int n;static List<Integer> list = new ArrayList<>();static boolean[] st = new boolean[20];public static void dfs(int u) {if (u == n) {for (int i = 0; i < list.size(); i++) {System.out.printf("%5d", list.get(i));}System.out.println();return;}for (int i = 1; i <= n; i++) {if (!st[i]) {st[i] = true;list.add(i);dfs(u + 1);st[i] = false;list.remove(list.size() - 1);}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(0);sc.close();}
}
但是呢,这个算法存在一定的缺陷。我们以洛谷上的一道全排列的题为例。
我们如果使用递归去实现这个问题的话,当n较大时,例如n==9,这时会因为递归层数太多而出现堆栈内存过大的情况,无法通过测试点,这是我们用Java实现,用c++则不会出现这个问题。
那么我们想用Java解决这个问题,该如何解决呢?
二、全排列函数next_permutation()
学习过STL的小伙伴肯定知道,在algorithm这个头文件中有一个强大的函数next_permutation(),这个函数的作用是求某一个全排列的下一个全排列。
如图,这个是3的全排列,并且是按照字典序排列起来的,假如现在一个序列是1 2 3,那么执行next_permutation()之后,序列将会变成1 3 2,这就是这个函数的作用。
这个函数具体该如何使用呢?
三、next_permutation()的使用
这个函数和sort()函数类似,需要传入起点迭代器和终点后一个迭代器(可以理解为是指针的一种),干说比较抽象,我们看例子。
对于数组来讲,第一个参数传入数组的名字,第二个参数传入数组的名字+数组的大小即可。字符数组和字符串同理
但是问题又来了,Java中并没有现成的这么强大的函数,所以我参考next_permutation()的源码,用java语言实现了一下。
四、Java实现next_permutation()
函数的功能是:如果当前序列存在下一个序列,将序列原地变为下一个全排列,并且返回true,否则返回false;
代码的思路就是
1. 检查序列长度,如果元素个数少于1,则没有下一个全排列,return fasle
2. 找到第一组不满足降序的连续两个数
3. 如果找不到这样的数,说明此时的全排列已经是最后一个,return false
4. 寻找i之后满足大于arr[i]的最小的数
5. 找到后交换i和k-1 位置的数
6. 然后i后位置升序即可
package algorithm.permutation;import java.util.Arrays;public class Permutation {public static void main(String[] args) {int[] arr = { 1, 4, 3, 2 };if(next_permutation(arr)){System.out.println(Arrays.toString(arr));}//System.out.println(Arrays.toString(arr));}public static boolean next_permutation(int[] arr) {//1. 元素个数少于1,没有下一个全排列if(arr.length<=1){return false;}//2. 找到第一组不满足降序的连续两个数int i=arr.length-2;while(i>=0&&arr[i]>arr[i+1])i--;//如果找不到这样的数,说明此时的全排列已经是最后一个if(i==-1){return false;}//3. 寻找i之后 满足大于arr[i]的最小的数int k=i+1;while(k<arr.length&&arr[k]>arr[i])k++;//4. 找到后交换i和k-1 位置的数swap(arr,i,k-1);//5. 然后i后位置升序即可Arrays.sort(arr,i+1,arr.length);return true;}static void swap( int[] arr,int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
写出这个函数之后我们就可以在不使用递归的前提下,实现n的全排列啦!
五、使用next_permutation()实现全排列
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Arrays;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr=new int[n];for(int i=0;i<n;i++){arr[i]=i+1;}do{for(int i=0;i<n;i++){System.out.printf("%5d",arr[i]);}System.out.println();}while(next_permutation(arr));}static boolean next_permutation(int[] arr) {//元素个数少于1,没有下一个全排列if(arr.length<=1){return false;}//找到第一组不满足降序的连续两个数int i=arr.length-2;while(i>=0&&arr[i]>arr[i+1])i--;//如果找不到这样的数,说明此时的全排列已经是最后一个if(i==-1){return false;}//寻找i之后 满足大于arr[i]的最小的数int k=i+1;while(k<arr.length&&arr[k]>arr[i])k++;//找到后交换i和k-1 位置的数swap(arr,i,k-1);//然后i后位置升序即可Arrays.sort(arr,i+1,arr.length);return true;}static void swap( int[] arr,int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}
我们提交后终于ac啦!!!
今天的分享就到这里啦,希望对各位小伙伴有所帮助!
这篇关于Java实现STL中的全排列函数next_permutation()的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!