有放回的有序抽样

Question

我真的在这方面陷入了困境。

我想生成所有组合，以便有替换的有序采样（我认为这就是它的名称，请参见我的示例）并且结果输出到数组数组（二维数组）中。

例如

public static int[][] combinations(int n, int k)

输入 n=3，k=2 会给出：

[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2 ,1],[2,2]]

我真的不确定如何有效地做到这一点。感谢任何指点！

Answer 1

这里我们有一个包含 n 个元素的集合，我们想从该集合中抽取 k 个样本，以便允许排序和重复。

这里是代码：

public static void main(String[] args) {
    int n = 4;
    int k = 2;
    int[][] result = combinations(n, k);
    System.out.println(Arrays.deepToString(result));
    //this will print:
    //[[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3],[3,0],[3,1],[3,2],[3,3]]
}

public static int[][] combinations(int n, int k) {
    int[] nArray = IntStream.range(0, n).toArray();
    List<String> list = new ArrayList<String>();
    combinationStrings(k, nArray, "", list);
    return fromArrayListToArray(list, k);
}

private static void combinationStrings(int k, int[] nArray, String currentString, List<String> list) {
    if (currentString.length() == k) {
        list.add(currentString);
    } else {
        for (int i = 0; i < nArray.length; i++) {
            String oldCurrent = currentString;
            currentString += nArray[i];
            combinationStrings(k, nArray, currentString, list);
            currentString = oldCurrent;
        }
    }
}

private static int[][] fromArrayListToArray(List<String> list, int k) {
    int[][] result = new int[list.size()][k];
    for (int i=0;i<list.size();i++) {
        String[] split = list.get(i).split("\B");
        for (int j = 0; j < split.length; j++) {
            result[i][j] = Integer.parseInt(split[j]);
        }
    }
    return result;
}

有放回的有序抽样

Ordered Sampling with Replacement

java

combinatorics