组合算法Java
Combination algorithm Java
我正在尝试编写一个函数:private static ArrayList<boolean[]> Combo(int i, int j)
它是 iCj
在数学中的一种“具体”实现:
Combo(4,2)
将 return 为 {true, true, false, false}, {true, false, true, false}, {false, true, true, false}, {false, true, false, true}, {false, false, true, true}
的数组列表(无特定顺序)。
目前,我有这样的递归算法:
private static ArrayList<boolean[]> Combo(int i, int j) {
ArrayList<boolean[]> k = new ArrayList<boolean[]>();
if (i == 1 && j == 0) {
k.add(new boolean[]{false});
} else if (i == 1 && j ==1) {
k.add(new boolean[]{true});
} else if (j>i) {
;
} else {
ArrayList<boolean[]> a1 = Combo((byte) i/2,1);
ArrayList<boolean[]> a2 = Combo((byte) i/2,2);
ArrayList<boolean[]> a3 = Combo((byte) i/2,3);
ArrayList<boolean[]> a4 = Combo((byte) i/2,4);
ArrayList<boolean[]> a5 = Combo((byte) i/2,5);
ArrayList<boolean[]> a6 = Combo((byte) i/2,6);
ArrayList<boolean[]> a7 = Combo((byte) i/2,7);
ArrayList<boolean[]> a8 = Combo((byte) i/2,8);
ArrayList<boolean[]> a9 = Combo((byte) i/2,9);
k.addAll(merge(a1,a9,j));
k.addAll(merge(a2,a8,j));
k.addAll(merge(a3,a7,j));
k.addAll(merge(a4,a6,j));
k.addAll(merge(a5,a5,j));
}
return k;
}
private static ArrayList<boolean[]> merge(ArrayList<boolean[]> a1, ArrayList<boolean[]> a2, int tot) {
ArrayList<boolean[]> k = new ArrayList<boolean[]>();
for (boolean[] b : a1) {
for (boolean[] b1: a2) {
boolean[] c = new boolean[tot];
for (int i = 0 ; i< b.length; i++) {
c[i] = b[i];
}
for (int i = b.length; i<b.length+b1.length; i++) {
c[i] = b1[i-b.length];
}
k.add(b);
}
}
return k;
}
但是我在第 129 行得到 Exception in thread "main" java.lang.WhosebugError
。
谁能帮我优化一下?
Jave 方法名称应始终以小写字母开头。
您还应该使用 java.util.List
作为方法 return 值。
我不喜欢写递归代码,所以我写了一个迭代解决方案。我使用了一个小技巧来生成所有组合。从0到2^N的所有整数的位模式给出了N个长度的所有组合。
在此代码中,我测试了您要查找的真实值的数量。
这是我对 4,2 和 6,2 的测试结果。我对结果进行了格式化以适合答案。
[[true, true, false, false], [true, false, true, false],
[false, true, true, false], [true, false, false, true],
[false, true, false, true], [false, false, true, true]]
[[true, true, false, false, false, false],
[true, false, true, false, false, false],
[false, true, true, false, false, false],
[true, false, false, true, false, false],
[false, true, false, true, false, false],
[false, false, true, true, false, false],
[true, false, false, false, true, false],
[false, true, false, false, true, false],
[false, false, true, false, true, false],
[false, false, false, true, true, false],
[true, false, false, false, false, true],
[false, true, false, false, false, true],
[false, false, true, false, false, true],
[false, false, false, true, false, true],
[false, false, false, false, true, true]]
这是完整的可运行代码。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationAlgorithm {
public static void main(String[] args) {
CombinationAlgorithm ca = new CombinationAlgorithm();
List<boolean[]> comboList = ca.combo(4, 2);
ca.printList(comboList);
comboList = ca.combo(6, 2);
ca.printList(comboList);
}
public List<boolean[]> combo(int elementCount, int trueCount) {
List<boolean[]> comboList = new ArrayList<>();
if (elementCount < trueCount) {
// Return empty list
return comboList;
}
int limit = (int) Math.pow(2.0, elementCount);
for (int index = 0; index < limit; index++) {
if (Integer.bitCount(index) == trueCount) {
boolean[] values = new boolean[elementCount];
for (int bit = 0; bit < elementCount; bit++) {
if (getBit(index, bit) == 0) {
values[bit] = false;
} else {
values[bit] = true;
}
}
comboList.add(values);
}
}
return comboList;
}
private int getBit(int value, int bit) {
return (value >> bit) & 1;
}
private void printList(List<boolean[]> comboList) {
System.out.print("[");
for (int index = 0; index < comboList.size(); index++) {
boolean[] values = comboList.get(index);
System.out.print(Arrays.toString(values));
if (index < (comboList.size() - 1)) {
System.out.print(", ");
}
}
System.out.println("]");
}
}
我正在尝试编写一个函数:private static ArrayList<boolean[]> Combo(int i, int j)
它是 iCj
在数学中的一种“具体”实现:
Combo(4,2)
将 return 为 {true, true, false, false}, {true, false, true, false}, {false, true, true, false}, {false, true, false, true}, {false, false, true, true}
的数组列表(无特定顺序)。
目前,我有这样的递归算法:
private static ArrayList<boolean[]> Combo(int i, int j) {
ArrayList<boolean[]> k = new ArrayList<boolean[]>();
if (i == 1 && j == 0) {
k.add(new boolean[]{false});
} else if (i == 1 && j ==1) {
k.add(new boolean[]{true});
} else if (j>i) {
;
} else {
ArrayList<boolean[]> a1 = Combo((byte) i/2,1);
ArrayList<boolean[]> a2 = Combo((byte) i/2,2);
ArrayList<boolean[]> a3 = Combo((byte) i/2,3);
ArrayList<boolean[]> a4 = Combo((byte) i/2,4);
ArrayList<boolean[]> a5 = Combo((byte) i/2,5);
ArrayList<boolean[]> a6 = Combo((byte) i/2,6);
ArrayList<boolean[]> a7 = Combo((byte) i/2,7);
ArrayList<boolean[]> a8 = Combo((byte) i/2,8);
ArrayList<boolean[]> a9 = Combo((byte) i/2,9);
k.addAll(merge(a1,a9,j));
k.addAll(merge(a2,a8,j));
k.addAll(merge(a3,a7,j));
k.addAll(merge(a4,a6,j));
k.addAll(merge(a5,a5,j));
}
return k;
}
private static ArrayList<boolean[]> merge(ArrayList<boolean[]> a1, ArrayList<boolean[]> a2, int tot) {
ArrayList<boolean[]> k = new ArrayList<boolean[]>();
for (boolean[] b : a1) {
for (boolean[] b1: a2) {
boolean[] c = new boolean[tot];
for (int i = 0 ; i< b.length; i++) {
c[i] = b[i];
}
for (int i = b.length; i<b.length+b1.length; i++) {
c[i] = b1[i-b.length];
}
k.add(b);
}
}
return k;
}
但是我在第 129 行得到 Exception in thread "main" java.lang.WhosebugError
。
谁能帮我优化一下?
Jave 方法名称应始终以小写字母开头。
您还应该使用 java.util.List
作为方法 return 值。
我不喜欢写递归代码,所以我写了一个迭代解决方案。我使用了一个小技巧来生成所有组合。从0到2^N的所有整数的位模式给出了N个长度的所有组合。
在此代码中,我测试了您要查找的真实值的数量。
这是我对 4,2 和 6,2 的测试结果。我对结果进行了格式化以适合答案。
[[true, true, false, false], [true, false, true, false],
[false, true, true, false], [true, false, false, true],
[false, true, false, true], [false, false, true, true]]
[[true, true, false, false, false, false],
[true, false, true, false, false, false],
[false, true, true, false, false, false],
[true, false, false, true, false, false],
[false, true, false, true, false, false],
[false, false, true, true, false, false],
[true, false, false, false, true, false],
[false, true, false, false, true, false],
[false, false, true, false, true, false],
[false, false, false, true, true, false],
[true, false, false, false, false, true],
[false, true, false, false, false, true],
[false, false, true, false, false, true],
[false, false, false, true, false, true],
[false, false, false, false, true, true]]
这是完整的可运行代码。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationAlgorithm {
public static void main(String[] args) {
CombinationAlgorithm ca = new CombinationAlgorithm();
List<boolean[]> comboList = ca.combo(4, 2);
ca.printList(comboList);
comboList = ca.combo(6, 2);
ca.printList(comboList);
}
public List<boolean[]> combo(int elementCount, int trueCount) {
List<boolean[]> comboList = new ArrayList<>();
if (elementCount < trueCount) {
// Return empty list
return comboList;
}
int limit = (int) Math.pow(2.0, elementCount);
for (int index = 0; index < limit; index++) {
if (Integer.bitCount(index) == trueCount) {
boolean[] values = new boolean[elementCount];
for (int bit = 0; bit < elementCount; bit++) {
if (getBit(index, bit) == 0) {
values[bit] = false;
} else {
values[bit] = true;
}
}
comboList.add(values);
}
}
return comboList;
}
private int getBit(int value, int bit) {
return (value >> bit) & 1;
}
private void printList(List<boolean[]> comboList) {
System.out.print("[");
for (int index = 0; index < comboList.size(); index++) {
boolean[] values = comboList.get(index);
System.out.print(Arrays.toString(values));
if (index < (comboList.size() - 1)) {
System.out.print(", ");
}
}
System.out.println("]");
}
}