快捷導(dǎo)航

Java實(shí)現(xiàn)STL中的全排列函數(shù)next_permutation()

更新時(shí)間：2024年09月25日 10:53:49 作者：mjh_yylx

在算法競(jìng)賽中,全排列問(wèn)題是一個(gè)經(jīng)典且常見(jiàn)的題目,傳統(tǒng)的遞歸方法在處理較大的n時(shí)會(huì)遇到堆棧內(nèi)存限制的問(wèn)題,本文介紹了一種避免遞歸,使用next_permutation函數(shù)實(shí)現(xiàn)全排列的方法,感興趣的朋友跟隨小編一起看看吧

一、引言

相信很多小伙伴們都做過(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中并沒(méi)有現(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，則沒(méi)有下一個(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，沒(méi)有下一個(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，沒(méi)有下一個(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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: