gpt4 book ai didi

java - n组所有可能的组合

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:12:02 27 4
gpt4 key购买 nike

我有 n 个集合。每个 Set 都有不同数量的元素。我想编写一个算法,为我提供集合中所有可能的组合。例如,假设我们有:

S1={1,2}, S2={A,B,C}, S3={$,%,£,!}

组合应该是这样的

C1={1,A,$}
C2={1,A,%}
...

……等等。可能的组合数将为 2*3*4 = 24

请帮我用Java写这个算法。

最佳答案

递归是你的 friend :

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 关于将其泛化为对象集的问题时:

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);
}
}
}

最后是迭代变体。它基于增加一个计数器数组,当计数器达到集合的大小时,计数器会进行包装和进位:

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) + "}";
}
}

关于java - n组所有可能的组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16549831/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com