原文地址見(jiàn)文末
個(gè)人感覺(jué)這篇文章(原文地址見(jiàn)文章尾)寫的排列組合問(wèn)題,非常的好,而且是一步一步引出排列組合問(wèn)題,我也是看了這篇文章,一步一步按照這個(gè)思路來(lái),最后會(huì)了自己的一套排列組合
也因此在算法競(jìng)賽中,兩次用到了,成功解決了問(wèn)題.
第一個(gè)問(wèn)題:
首先,先讓我們來(lái)看第一個(gè)問(wèn)題, 有1,2,3,4這4個(gè)數(shù)字.可以重復(fù)的在里面選4次,問(wèn)能得到多少種結(jié)果.easy
1 1 1 1
1 1 1 2
1 1 1 3
1 1 1 4
1 1 2 1
1 1 2 2
.......
4 4 4 3
4 4 4 4
代碼實(shí)現(xiàn)其實(shí)也很簡(jiǎn)單,大家可以看下代碼,理解一下,再自己敲一下,應(yīng)該可以很快敲出來(lái)
import?java.util.Stack;
public?class?Main {
????public?static?Stack stack =?new?Stack<Integer>();
????public?static?void?main(String[] args) {
????????int?shu[] = {1,2,3,4};
????????f(shu,4,0);
????}
????/**
?????*
?????* @param shu?? 待選擇的數(shù)組
?????* @param targ? 要選擇多少個(gè)次
?????* @param cur?? 當(dāng)前選擇的是第幾次
?????*/
????private?static?void?f(int[] shu,?int?targ,?int?cur) {
????????// TODO Auto-generated method stub
????????if(cur == targ) {
????????????System.out.println(stack);
????????????return;
????????}
????????for(int?i=0;i<shu.length;i++) {
????????????stack.add(shu[i]);
????????????f(shu, targ, cur+1);
????????????stack.pop();
????????}
????}
}
輸出:
[1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 1, 4]
[1, 1, 2, 1]
[1, 1, 2, 2]
............
............
[4, 4, 3, 2]
[4, 4, 3, 3]
[4, 4, 3, 4]
[4, 4, 4, 1]
[4, 4, 4, 2]
[4, 4, 4, 3]
[4, 4, 4, 4]
得到了想要的結(jié)果，此處結(jié)果又很多種4*4*4*4 = 256種結(jié)果。
第二個(gè)問(wèn)題:
同理,? 問(wèn)題來(lái)了,這時(shí)候有點(diǎn)排列組合的意思了 1,2,3,4排列要的到的是
1 2 3 4
1 2 4 3
1 3 4 2
1 3 2 4
......
4 2 1 2
4 3 2 1
有沒(méi)有發(fā)現(xiàn)要的到排列的情況,這里stack里的元素是1,2,3,4都不能重復(fù)
那么我在入棧的時(shí)候加個(gè)判斷,如果比如1,已經(jīng)在stack里面了,就不加進(jìn)去,就不會(huì)得到? 1? 1 1 1 ...的情況了,就得到了排列
import?java.util.Stack;
public?class?Main {
????public?static?Stack stack =?new?Stack<Integer>();
????public?static?void?main(String[] args) {
????????int?shu[] = {1,2,3,4};
????????f(shu,4,0);
????}
????/**
?????*
?????* @param shu?? 待選擇的數(shù)組
?????* @param targ? 要選擇多少個(gè)次
?????* @param cur?? 當(dāng)前選擇的是第幾次
?????*/
????private?static?void?f(int[] shu,?int?targ,?int?cur) {
????????// TODO Auto-generated method stub
????????if(cur == targ) {
????????????System.out.println(stack);
????????????return;
????????}
????????for(int?i=0;i<shu.length;i++) {
????????????if(!stack.contains(shu[i])) {
????????????????stack.add(shu[i]);
????????????????f(shu, targ, cur+1);
????????????????stack.pop();
????????????}
????????}
????}
}
輸出:
[1,?2,?3,?4]
[1,?2,?4,?3]
[1,?3,?2,?4]
[1,?3,?4,?2]
[1,?4,?2,?3]
[1,?4,?3,?2]
[2,?1,?3,?4]
[2,?1,?4,?3]
[2,?3,?1,?4]
[2,?3,?4,?1]
[2,?4,?1,?3]
[2,?4,?3,?1]
[3,?1,?2,?4]
[3,?1,?4,?2]
[3,?2,?1,?4]
[3,?2,?4,?1]
[3,?4,?1,?2]
[3,?4,?2,?1]
[4,?1,?2,?3]
[4,?1,?3,?2]
[4,?2,?1,?3]
[4,?2,?3,?1]
[4,?3,?1,?2]
[4,?3,?2,?1]
這就是想要的排列結(jié)果了..? ?4 * 3 * 2 * 1 = 24種結(jié)果。
第三個(gè)問(wèn)題:
那么組合問(wèn)題來(lái)了，在1,2,3,4,中選3個(gè)有多少種組合方式
1?2?3
1?2?4
1?3?4
2?3?4
共4種
import?java.util.Stack;
public?class?Main {
????public?static?Stack stack =?new?Stack<Integer>();
????public?static?void?main(String[] args) {
????????int?shu[] = {1,2,3,4};
????????f(shu,3,0,0);?// 從這個(gè)數(shù)組4個(gè)數(shù)中選擇三個(gè)
????}
????/**
?????*
?????* @param shu? 元素
?????* @param targ? 要選多少個(gè)元素
?????* @param has?? 當(dāng)前有多少個(gè)元素
?????* @param cur?? 當(dāng)前選到的下標(biāo)
?????*
?????* 1??? 2?? 3???? //開(kāi)始下標(biāo)到2
?????* 1??? 2?? 4???? //然后從3開(kāi)始
?????*/
????private?static?void?f(int[] shu,?int?targ,?int?has,?int?cur) {
????????if(has == targ) {
????????????System.out.println(stack);
????????????return;
????????}
????????for(int?i=cur;i<shu.length;i++) {
????????????if(!stack.contains(shu[i])) {
????????????????stack.add(shu[i]);
????????????????f(shu, targ, has+1, i);
????????????????stack.pop();
????????????}
????????}
????}
}
?輸出:
[1,?2,?3]
[1,?2,?4]
[1,?3,?4]
[2,?3,?4]
https://www.cnblogs.com/zzlback/p/10947064.html
