今天遇到需要编写“排列组合算法”，虽然懂数学原理，但是真正写的时候，还是吃不透。最后结合网上的代码，整理了出来。
Tip：文章最后关联知乎一个帖子，介绍了什么是“排列组合”，如果不懂，建议看看。
首先贴上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("排列结果 : ");
permutation("",ia, n);
// System.out.println("组合结果 : ");
// 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个元素的子数组
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开始的子数组
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);
}
}
}
}
我项目用的TypeScript语言，所以我自己做了一遍翻译，并且稍微改进了一下，更加适配我的项目需要。
/** * 排列算法 * @param targetList 目标列表(源数据列表) * @param step 步数(取几个值,例如"Pm取n"中的"n") * @param totalList 总列表(总的数据列表) * @param pmtList 临时排列列表(子列表) */ 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：到这里代表一次结束。newPmtList就是排列出来的一种情况。 } } else { for (let i = 0; i < targetList.length; i++) { let newPmtList: T[] = []; newPmtList = ObjectUtils.deepClone(pmtList, newPmtList); newPmtList.push(targetList[i]); //建立没有第i个元素的子数组 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); } } }
⚠️重新编辑帖子, 代码就不能换行了, 自行修复一下吧.
排列算法使用方式:
let targetList = ["1", "2", "3", "a", "b", "c"];
let totalList = [];
permutation(targetList, 2, totalList);
console.log(">>>> 测试总列表:", totalList);
/** * 组合算法 * @param targetList 目标列表(源数据列表) * @param step 步数(取几个值,例如"Cm取n"中的"n") * @param totalList 总列表(总的数据列表) * @param pmtList 临时排列列表(子列表) */ 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：到这里代表一次结束。newCbnList就是组合出来的一种情况。 } } else { for (let i = 0; i < targetList.length - (step - 1); i++) { let newCbnList: T[] = []; ObjectUtils.copyProperty(cbnList, newCbnList); newCbnList.push(targetList[i]); //建立从i开始的子数组 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); } } }
⚠️重新编辑帖子, 代码就不能换行了, 自行修复一下吧.
组合算法使用方式:
let targetList = ["1", "2", "3", "a", "b", "c"];
let totalList = [];
combination(targetList, 2, totalList);
console.log(">>>> 测试总列表:", totalList);
其实也没修改什么特别的内容，原作者是组合一串string输出，而我是需要取出各组结果，所以改用泛型标志，可以做成公用的工具类。
（Tip：大家可以参考，结合自己需要另外改，代码要合适才好用。）
最后贴上一个介绍“排列组合”的帖子，个人觉得挺不错的。有兴趣的小伙伴可以去看看，可以让你很快理解排列组合。
