今天遇到需要編寫“排列組合算法”驾胆，雖然懂?dāng)?shù)學(xué)原理涣澡，但是真正寫的時(shí)候，還是吃不透丧诺。最后結(jié)合網(wǎng)上的代碼入桂，整理了出來(lái)。
Tip：文章最后關(guān)聯(lián)知乎一個(gè)帖子驳阎，介紹了什么是“排列組合”抗愁，如果不懂馁蒂，建議看看。
首先貼上js代碼：（原貼沒有任何注明蜘腌，所以也不知道出自哪位大佬）
package com.test;
public class Pailie {
public static void main(String[] args) {
? ? ? ? int[] ia = {1, 2, 3, 4,5,6,7,8,9,10};
? ? ? ? int n = 4;
? ? ? ? System.out.println("排列結(jié)果 : ");
? ? ? ? permutation("",ia, n);
// ? ? ? ? System.out.println("組合結(jié)果 : ");
// ? ? ? ? combination(ia, n);
? ? }
? ? public static void permutation(String s, int[] ia, int n) {
? ? ? ? if(n == 1) {
? ? ? ? ? ? for(int i = 0; i < ia.length; i++) {
? ? ? ? ? ? ? ? System.out.println(s+ia[i]);
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? for(int i = 0; i < ia.length; i++) {
? ? ? ? ? ? ? ? String ss = "";
? ? ? ? ? ? ? ? ss = s+ia[i]+"";
? ? ? ? ? ? ? ? //建立沒有第i個(gè)元素的子數(shù)組
? ? ? ? ? ? ? ? int[] ii = new int[ia.length-1];
? ? ? ? ? ? ? ? int index = 0;
? ? ? ? ? ? ? ? for(int j = 0; j < ia.length; j++) {
? ? ? ? ? ? ? ? ? ? if(j != i) {
? ? ? ? ? ? ? ? ? ? ? ? ii[index++] = ia[j];
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? permutation(ss, ii, n-1);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? public static void combination(int[] ia, int n) {
? ? ? ? combination("", ia, n);
? ? }
? ? public static void combination(String s, int[] ia, int n) {
? ? ? ? if(n == 1) {
? ? ? ? ? ? for(int i = 0; i < ia.length; i++) {
? ? ? ? ? ? ? ? System.out.println(s+ia[i]);
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? for(int i = 0; i < ia.length-(n-1); i++) {
? ? ? ? ? ? ? ? String ss = "";
? ? ? ? ? ? ? ? ss = s+ia[i]+", ";
? ? ? ? ? ? ? ? //建立從i開始的子數(shù)組
? ? ? ? ? ? ? ? int[] ii = new int[ia.length-i-1];
? ? ? ? ? ? ? ? for(int j = 0; j < ia.length-i-1; j++) {
? ? ? ? ? ? ? ? ? ? ii[j] = ia[i+j+1];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? combination(ss, ii, n-1);
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
我項(xiàng)目用的TypeScript語(yǔ)言沫屡，所以我自己做了一遍翻譯，并且稍微改進(jìn)了一下撮珠，更加適配我的項(xiàng)目需要沮脖。
/** * 排列算法 * @param targetList 目標(biāo)列表(源數(shù)據(jù)列表) * @param step 步數(shù)(取幾個(gè)值,例如"Pm取n"中的"n") * @param totalList 總列表(總的數(shù)據(jù)列表) * @param pmtList 臨時(shí)排列列表(子列表) */ public static permutation<T>(targetList: T[], step: number, totalList: T[][], pmtList: T[] = []): void { if (step == 1) { for (let i = 0; i < targetList.length; i++) { let newPmtList: T[] = []; newPmtList = ObjectUtils.deepClone(pmtList, newPmtList); newPmtList.push(targetList[i]); totalList.push(newPmtList); //Tip：到這里代表一次結(jié)束。newPmtList就是排列出來(lái)的一種情況芯急。 } } else { for (let i = 0; i < targetList.length; i++) { let newPmtList: T[] = []; newPmtList = ObjectUtils.deepClone(pmtList, newPmtList); newPmtList.push(targetList[i]); //建立沒有第i個(gè)元素的子數(shù)組 let newTargetList: T[] = []; for (let j = 0; j < targetList.length; j++) { if (j != i) { newTargetList.push(targetList[j]); } } this.permutation(newTargetList, step - 1, totalList, newPmtList); } } }
??重新編輯帖子, 代碼就不能換行了, 自行修復(fù)一下吧.
排列算法使用方式:
let targetList = ["1", "2", "3", "a", "b", "c"];
let totalList = [];
permutation(targetList, 2, totalList);
console.log(">>>>? 測(cè)試總列表:", totalList);
/** * 組合算法 * @param targetList 目標(biāo)列表(源數(shù)據(jù)列表) * @param step 步數(shù)(取幾個(gè)值,例如"Cm取n"中的"n") * @param totalList 總列表(總的數(shù)據(jù)列表) * @param pmtList 臨時(shí)排列列表(子列表) */ public static combination<T>(targetList: T[], step: number, totalList: T[][], cbnList: T[] = []): void { if (step == 1) { for (let i = 0; i < targetList.length; i++) { let newCbnList: T[] = []; newCbnList = ObjectUtils.deepClone(cbnList, newCbnList); newCbnList.push(targetList[i]); totalList.push(newCbnList); //Tip：到這里代表一次結(jié)束勺届。newCbnList就是組合出來(lái)的一種情況。 } } else { for (let i = 0; i < targetList.length - (step - 1); i++) { let newCbnList: T[] = []; ObjectUtils.copyProperty(cbnList, newCbnList); newCbnList.push(targetList[i]); //建立從i開始的子數(shù)組 let newTargetList: T[] = []; for (let j = 0; j < targetList.length - i - 1; j++) { newTargetList.push(targetList[i + j + 1]); } this.combination(newTargetList, step - 1, totalList, newCbnList); } } }
??重新編輯帖子, 代碼就不能換行了, 自行修復(fù)一下吧.
組合算法使用方式:
let targetList = ["1", "2", "3", "a", "b", "c"];
let totalList = [];
combination(targetList, 2, totalList);
console.log(">>>>? 測(cè)試總列表:", totalList);
其實(shí)也沒修改什么特別的內(nèi)容志于，原作者是組合一串string輸出涮因，而我是需要取出各組結(jié)果废睦，所以改用泛型標(biāo)志伺绽，可以做成公用的工具類。
（Tip：大家可以參考嗜湃，結(jié)合自己需要另外改奈应，代碼要合適才好用。）
最后貼上一個(gè)介紹“排列組合”的帖子购披，個(gè)人覺得挺不錯(cuò)的杖挣。有興趣的小伙伴可以去看看，可以讓你很快理解排列組合刚陡。
