一、概念
以a、b、c三个字符来举例。
1）排列：全排列即字符不能重复，第一位有3种选择，第二位有2种选择，第三位有1种选择，所以最后有3*2*1=6种结果。
2）组合：组合不要求三个字符都必须加入结果。
求所有组合也就是abc各个位是否选取的问题，第一位2种可能，第二位2种可能，以此类推，一共有2^n种可能。用0表示不取，1表示选取，这样可以用110这样的形式表示ab。
abc一共的表示形式从0到2^3-1。然后按位与运算，如果结果为1就输出当前位，为0则不输出。
二、代码
1）排列
public Permutation {
public static void main(String[] args) {
char[] array = {'a','b','c'};
backtrace(array, 0, array.length);
}
public static void backtrace(char[] array, int start, int len){
if(start == len-1){
for(int i=0; i<array.length; ++i)
System.out.print(array[i]);
System.out.println();
return;
}
for(int index=start; index<len; ++index){
//交换start与index位置对应的值
swap(array, start, index);
//继续回溯
backtrace(array, start+1, len);
//将交换复原
swap(array,start,index);
}
}
//交换array字符数组中索引为i和j位置的元素
private static void swap(char[] array, int i, int j) {
if (i != j) {
char t = array[i];
array[i] = array[j];
array[j] = t;
}
}
}
2）组合
public Combination {
public static void main(String[] args) {
//待组合的元素
char[] array = {'a','b','c'};
//调用获取组合结果函数
combination(array);
}
//求组合结果
public static void combination(char[] array) {
int len = array.length;
//临时变量从0到nbits-1
int nbits = 1 << len;
for (int i = 0; i < nbits; ++i) {
int t;
for (int j = 0; j < len; j++) {
t = 1 << j;
//若t和i的字符相与不为0，则取j位置的字符
if ((t & i) != 0) {
System.out.print(array[j]);
}
}
System.out.println();
}
}
}
致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。
若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。
