深度優(yōu)先遍歷-解決排列組合問題

問題1

假設(shè)袋子里有編號(hào)為1,2,…,m這m個(gè)球?，F(xiàn)在每次從袋子中取一個(gè)球記下編號(hào)，放回袋中再取，取n次作為一組，枚舉所有可能的情況。

分析： 每一次取都有m種可能的情況，因此一共有 m n m^n mn種情況。 這里我們?nèi) = 3, n = 4，則有 3 4 3^4 34種不同的情況。

代碼：

import java.util.Stack;
public class Test {
    static int cnt = 0;
    static Stack<Integer> s = new Stack<Integer>();
    /**
     * 遞歸方法，當(dāng)實(shí)際選取的小球數(shù)目與要求選取的小球數(shù)目相同時(shí)，跳出遞歸
     * @param minv - 小球編號(hào)的最小值
     * @param maxv - 小球編號(hào)的最大值
     * @param curnum - 當(dāng)前已經(jīng)確定的小球的個(gè)數(shù)
     * @param maxnum - 要選取的小球的數(shù)目
     */
    public static void kase1(int minv,int maxv,int curnum, int maxnum){
        if(curnum == maxnum){
            cnt++;
            System.out.println(s);
            return;
        }
        for(int i = minv; i <= maxv; i++){
            s.push(i);
            kase1(minv, maxv, curnum+1, maxnum);
            s.pop();
        }
    }
    public static void main(String[] args){
        kase1(1, 3, 0, 4);
        System.out.println(cnt);
    }
}

輸出：

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

問題2

假設(shè)袋子里有編號(hào)為1,2,…,m這m個(gè)球。先后從袋子中取出n個(gè)球，依次記錄編號(hào)，枚舉所有可能的情況。

分析： 這是排列問題，如果取出的球順序不同，也是算不同的情況。因此應(yīng)該有m∗(m−1)∗(m−2)∗...∗(m−n+1)種情況，即

種 這里取m = 5, n = 3。則有5*4*3種。 和問題1相比，唯一的區(qū)別是排列中不可以有重復(fù)。因此開了used數(shù)組用以標(biāo)記是否已經(jīng)訪問。

代碼：

import java.util.Stack;
public class Test {
    static int cnt = 0;
    static Stack<Integer> s = new Stack<Integer>();
    static boolean[] used = new boolean[10000];
    /**
     * 遞歸方法，當(dāng)實(shí)際選取的小球數(shù)目與要求選取的小球數(shù)目相同時(shí)，跳出遞歸
     * @param minv - 小球編號(hào)的最小值
     * @param maxv - 小球編號(hào)的最大值
     * @param curnum - 當(dāng)前已經(jīng)確定的小球的個(gè)數(shù)
     * @param maxnum - 要選取的小球的數(shù)目
     */
    public static void kase2(int minv,int maxv,int curnum, int maxnum){
        if(curnum == maxnum){
            cnt++;
            System.out.println(s);
            return;
        }
        for(int i = minv; i <= maxv; i++){
            if(!used[i]){ //判斷是否已經(jīng)取過
                s.push(i);
                used[i] = true;
                kase2(minv, maxv, curnum+1, maxnum);
                s.pop();
                used[i] = false;
            }
        }
    }
    public static void main(String[] args){
        kase2(1, 5, 0, 3);
        System.out.println(cnt);
    }
}

輸出：

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 2]
[1, 3, 4]
[1, 3, 5]
[1, 4, 2]
[1, 4, 3]
[1, 4, 5]
[1, 5, 2]
[1, 5, 3]
[1, 5, 4]
[2, 1, 3]
[2, 1, 4]
[2, 1, 5]
[2, 3, 1]
[2, 3, 4]
[2, 3, 5]
[2, 4, 1]
[2, 4, 3]
[2, 4, 5]
[2, 5, 1]
[2, 5, 3]
[2, 5, 4]
[3, 1, 2]
[3, 1, 4]
[3, 1, 5]
[3, 2, 1]
[3, 2, 4]
[3, 2, 5]
[3, 4, 1]
[3, 4, 2]
[3, 4, 5]
[3, 5, 1]
[3, 5, 2]
[3, 5, 4]
[4, 1, 2]
[4, 1, 3]
[4, 1, 5]
[4, 2, 1]
[4, 2, 3]
[4, 2, 5]
[4, 3, 1]
[4, 3, 2]
[4, 3, 5]
[4, 5, 1]
[4, 5, 2]
[4, 5, 3]
[5, 1, 2]
[5, 1, 3]
[5, 1, 4]
[5, 2, 1]
[5, 2, 3]
[5, 2, 4]
[5, 3, 1]
[5, 3, 2]
[5, 3, 4]
[5, 4, 1]
[5, 4, 2]
[5, 4, 3]
60

問題3

從m個(gè)球里（編號(hào)為1,2,3…,m）一次取n個(gè)球，其中m>n，記錄取出球的編號(hào)，枚舉所有的可能性。

分析： 這是組合問題。應(yīng)該有

 種可能性。 這里，如果取m = 8, n = 4. 則有

種可能。

代碼：

import java.util.Stack;
public class Test {
    static int cnt = 0;
    static Stack<Integer> s = new Stack<Integer>();
    /**
     * 遞歸方法，當(dāng)前已抽取的小球個(gè)數(shù)與要求抽取小球個(gè)數(shù)相同時(shí)，退出遞歸
     * @param curnum - 當(dāng)前已經(jīng)抓取的小球數(shù)目
     * @param curmaxv - 當(dāng)前已經(jīng)抓取小球中最大的編號(hào)
     * @param maxnum - 需要抓取小球的數(shù)目
     * @param maxv - 待抓取小球中最大的編號(hào)
     */
    public static void kase3(int curnum, int curmaxv,  int maxnum, int maxv){
        if(curnum == maxnum){
            cnt++;
            System.out.println(s);
            return;
        }
        for(int i = curmaxv + 1; i <= maxv; i++){ // i <= maxv - maxnum + curnum + 1
            s.push(i);
            kase3(curnum + 1, i, maxnum, maxv);
            s.pop();
        }
    }
    public static void main(String[] args){
        kase3(0, 0, 4, 8);
        System.out.println(cnt);
    }
}

輸出：

[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 3, 7]
[1, 2, 3, 8]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 4, 7]
[1, 2, 4, 8]
[1, 2, 5, 6]
[1, 2, 5, 7]
[1, 2, 5, 8]
[1, 2, 6, 7]
[1, 2, 6, 8]
[1, 2, 7, 8]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 4, 7]
[1, 3, 4, 8]
[1, 3, 5, 6]
[1, 3, 5, 7]
[1, 3, 5, 8]
[1, 3, 6, 7]
[1, 3, 6, 8]
[1, 3, 7, 8]
[1, 4, 5, 6]
[1, 4, 5, 7]
[1, 4, 5, 8]
[1, 4, 6, 7]
[1, 4, 6, 8]
[1, 4, 7, 8]
[1, 5, 6, 7]
[1, 5, 6, 8]
[1, 5, 7, 8]
[1, 6, 7, 8]
[2, 3, 4, 5]
[2, 3, 4, 6]
[2, 3, 4, 7]
[2, 3, 4, 8]
[2, 3, 5, 6]
[2, 3, 5, 7]
[2, 3, 5, 8]
[2, 3, 6, 7]
[2, 3, 6, 8]
[2, 3, 7, 8]
[2, 4, 5, 6]
[2, 4, 5, 7]
[2, 4, 5, 8]
[2, 4, 6, 7]
[2, 4, 6, 8]
[2, 4, 7, 8]
[2, 5, 6, 7]
[2, 5, 6, 8]
[2, 5, 7, 8]
[2, 6, 7, 8]
[3, 4, 5, 6]
[3, 4, 5, 7]
[3, 4, 5, 8]
[3, 4, 6, 7]
[3, 4, 6, 8]
[3, 4, 7, 8]
[3, 5, 6, 7]
[3, 5, 6, 8]
[3, 5, 7, 8]
[3, 6, 7, 8]
[4, 5, 6, 7]
[4, 5, 6, 8]
[4, 5, 7, 8]
[4, 6, 7, 8]
[5, 6, 7, 8]
70

到此這篇關(guān)于Java深度優(yōu)先遍歷解決排列組合問題詳解的文章就介紹到這了,更多相關(guān)Java深度優(yōu)先遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論