正套所有可能的组合 [英] all possible combination of n sets
本文介绍了正套所有可能的组合的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有n个。每一套都有不同数量的元素。我想编写一个算法,给我从套所有可能的组合。 例如: 比方说,我们有:
I have n Sets. each Set has different number of elements. I would like to write an algorithm which give me all possible combinations from the sets. for example: Lets say we have:
S1={1,2}, S2={A,B,C}, S3={$,%,£,!}
组合应该像
C1={1,A,$}
C2={1,A,%}
....等等可能的组合数量将 2 * 3 * 4 = 24
请帮我写这个算法的Java。
Please Help me to write this algorithm in Java.
提前感谢
推荐答案
递归是你的朋友:
public class PrintSetComb{
public static void main(String[] args){
String[] set1 = {"1","2"};
String[] set2 = {"A","B","C"};
String[] set3 = {"$", "%", "£", "!"};
String[][] sets = {set1, set2, set3};
printCombinations(sets, 0, "");
}
private static void printCombinations(String[][] sets, int n, String prefix){
if(n >= sets.length){
System.out.println("{"+prefix.substring(0,prefix.length()-1)+"}");
return;
}
for(String s : sets[n]){
printCombinations(sets, n+1, prefix+s+",");
}
}
}
在响应从OP质疑它推广到集对象:
In response to question from OP about generalizing it to sets of Objects:
import java.util.Arrays;
public class PrintSetComb{
public static void main(String[] args){
Integer[] set1 = {1,2};
Float[] set2 = {2.0F,1.3F,2.8F};
String[] set3 = {"$", "%", "£", "!"};
Object[][] sets = {set1, set2, set3};
printCombinations(sets, 0, new Object[0]);
}
private static void printCombinations(Object[][] sets, int n, Object[] prefix){
if(n >= sets.length){
String outp = "{";
for(Object o: prefix){
outp = outp+o.toString()+",";
}
System.out.println(outp.substring(0,outp.length()-1)+"}");
return;
}
for(Object o : sets[n]){
Object[] newPrefix = Arrays.copyOfRange(prefix,0,prefix.length+1);
newPrefix[newPrefix.length-1] = o;
printCombinations(sets, n+1, newPrefix);
}
}
}
和最后一个迭代变量。它是基于当它到达集的大小增加的计数器,其中所述计数器重叠并携带的阵列
And finally an iterative variant. It is based on increasing an array of counters where the counter wraps and carries when it reaches the size of the set:
import java.util.Arrays;
public class PrintSetCombIterative{
public static void main(String[] args){
String[] set1 = {"1","2"};
String[] set2 = {"A","B","C"};
String[] set3 = {"$", "%", "£", "!"};
Object[][] sets = {set1, set2, set3};
printCombinations(sets);
}
private static void printCombinations(Object[][] sets){
int[] counters = new int[sets.length];
do{
System.out.println(getCombinationString(counters, sets));
}while(increment(counters, sets));
}
private static boolean increment(int[] counters, Object[][] sets){
for(int i=counters.length-1;i>=0;i--){
if(counters[i] < sets[i].length-1){
counters[i]++;
return true;
} else {
counters[i] = 0;
}
}
return false;
}
private static String getCombinationString(int[] counters, Object[][] sets){
String combo = "{";
for(int i = 0; i<counters.length;i++){
combo = combo+sets[i][counters[i]]+",";
}
return combo.substring(0,combo.length()-1)+"}";
}
}
这篇关于正套所有可能的组合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文