Java實(shí)現(xiàn)STL中的全排列函數(shù)next_permutation()
一、引言
相信很多小伙伴們都做過(guò)全排列的算法題,輸入一個(gè)n,輸出1~n的全排列。對(duì)于這個(gè)問(wèn)題,最經(jīng)典的是實(shí)現(xiàn)方法應(yīng)該是通過(guò)回溯實(shí)現(xià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(); } }
但是呢,這個(gè)算法存在一定的缺陷。我們以洛谷上的一道全排列的題為例。
我們?nèi)绻褂眠f歸去實(shí)現(xiàn)這個(gè)問(wèn)題的話,當(dāng)n較大時(shí),例如n==9,這時(shí)會(huì)因?yàn)檫f歸層數(shù)太多而出現(xiàn)堆棧內(nèi)存過(guò)大的情況,無(wú)法通過(guò)測(cè)試點(diǎn),這是我們用Java實(shí)現(xiàn),用c++則不會(huì)出現(xiàn)這個(gè)問(wèn)題。
那么我們想用Java解決這個(gè)問(wèn)題,該如何解決呢?
二、全排列函數(shù)next_permutation()
學(xué)習(xí)過(guò)STL的小伙伴肯定知道,在algorithm這個(gè)頭文件中有一個(gè)強(qiáng)大的函數(shù)next_permutation(),這個(gè)函數(shù)的作用是求某一個(gè)全排列的下一個(gè)全排列。
如圖,這個(gè)是3的全排列,并且是按照字典序排列起來(lái)的,假如現(xiàn)在一個(gè)序列是1 2 3,那么執(zhí)行next_permutation()之后,序列將會(huì)變成1 3 2,這就是這個(gè)函數(shù)的作用。
這個(gè)函數(shù)具體該如何使用呢?
三、next_permutation()的使用
這個(gè)函數(shù)和sort()函數(shù)類似,需要傳入起點(diǎn)迭代器和終點(diǎn)后一個(gè)迭代器(可以理解為是指針的一種),干說(shuō)比較抽象,我們看例子。
對(duì)于數(shù)組來(lái)講,第一個(gè)參數(shù)傳入數(shù)組的名字,第二個(gè)參數(shù)傳入數(shù)組的名字+數(shù)組的大小即可。字符數(shù)組和字符串同理
但是問(wèn)題又來(lái)了,Java中并沒有現(xiàn)成的這么強(qiáng)大的函數(shù),所以我參考next_permutation()的源碼,用java語(yǔ)言實(shí)現(xiàn)了一下。
四、Java實(shí)現(xiàn)next_permutation()
函數(shù)的功能是:如果當(dāng)前序列存在下一個(gè)序列,將序列原地變?yōu)橄乱粋€(gè)全排列,并且返回true,否則返回false;
代碼的思路就是
1. 檢查序列長(zhǎng)度,如果元素個(gè)數(shù)少于1,則沒有下一個(gè)全排列,return fasle
2. 找到第一組不滿足降序的連續(xù)兩個(gè)數(shù)
3. 如果找不到這樣的數(shù),說(shuō)明此時(shí)的全排列已經(jīng)是最后一個(gè),return false
4. 尋找i之后滿足大于arr[i]的最小的數(shù)
5. 找到后交換i和k-1 位置的數(shù)
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. 元素個(gè)數(shù)少于1,沒有下一個(gè)全排列 if(arr.length<=1){ return false; } //2. 找到第一組不滿足降序的連續(xù)兩個(gè)數(shù) int i=arr.length-2; while(i>=0&&arr[i]>arr[i+1])i--; //如果找不到這樣的數(shù),說(shuō)明此時(shí)的全排列已經(jīng)是最后一個(gè) if(i==-1){ return false; } //3. 尋找i之后 滿足大于arr[i]的最小的數(shù) int k=i+1; while(k<arr.length&&arr[k]>arr[i])k++; //4. 找到后交換i和k-1 位置的數(shù) 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; } }
寫出這個(gè)函數(shù)之后我們就可以在不使用遞歸的前提下,實(shí)現(xiàn)n的全排列啦!
五、使用next_permutation()實(shí)現(xiàn)全排列
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) { //元素個(gè)數(shù)少于1,沒有下一個(gè)全排列 if(arr.length<=1){ return false; } //找到第一組不滿足降序的連續(xù)兩個(gè)數(shù) int i=arr.length-2; while(i>=0&&arr[i]>arr[i+1])i--; //如果找不到這樣的數(shù),說(shuō)明此時(shí)的全排列已經(jīng)是最后一個(gè) if(i==-1){ return false; } //尋找i之后 滿足大于arr[i]的最小的數(shù) int k=i+1; while(k<arr.length&&arr[k]>arr[i])k++; //找到后交換i和k-1 位置的數(shù) 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啦!??!
到此這篇關(guān)于Java實(shí)現(xiàn)STL中的全排列函數(shù)next_permutation()的文章就介紹到這了,更多相關(guān)Java STL全排列函數(shù)next_permutation()內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringSecurit鹽值加密的密碼驗(yàn)證以及強(qiáng)密碼驗(yàn)證過(guò)程
在密碼加密過(guò)程中,鹽值的使用可以增強(qiáng)密碼的安全性,如果忘記存儲(chǔ)鹽值,將無(wú)法驗(yàn)證密碼,強(qiáng)密碼應(yīng)包含數(shù)字、字母和特殊字符,長(zhǎng)度應(yīng)在8到30位之間,以提高賬戶安全2023-03-03Spring MVC 攔截器 interceptor 用法詳解
這篇文章主要介紹了Spring MVC 攔截器 interceptor 用法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07Java 中ConcurrentHashMap的實(shí)現(xiàn)
本文主要介紹Java 中ConcurrentHashMap的實(shí)現(xiàn),這里整理了詳細(xì)的資料,及簡(jiǎn)單實(shí)例代碼,有興趣的小伙伴可以參考下2016-09-09