组合算法Java

Question

我正在尝试编写一个函数：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。

谁能帮我优化一下？

Answer 1

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

}

组合算法Java

Combination algorithm Java

java

combinations