java - 如何在java中从一组大小为n的集合中迭代生成k个元素子集？

Question

我正在研究一个难题，该难题涉及分析所有大小为 k 的子集并找出哪个是最优的。我写了一个解决方案，当子集的数量很少时，它可以工作，但是对于更大的问题，它会耗尽内存。现在我正在尝试将用 python 编写的迭代函数转换为 java，以便我可以在创建每个子集时对其进行分析，并仅获取表示其优化程度的值，而不是整个集合，这样我就不会用完内存。这是我到目前为止所拥有的，即使对于非常小的问题，它似乎也没有完成:

public static LinkedList<LinkedList<Integer>> getSets(int k, LinkedList<Integer> set)
{
    int N = set.size();
    int maxsets = nCr(N, k);
    LinkedList<LinkedList<Integer>> toRet = new LinkedList<LinkedList<Integer>>();

    int remains, thresh;
    LinkedList<Integer> newset; 
    for (int i=0; i<maxsets; i++)
    {
        remains = k;
        newset = new LinkedList<Integer>();
        for (int val=1; val<=N; val++)
        {
            if (remains==0)
                break;
            thresh = nCr(N-val, remains-1);
            if (i < thresh)
            {
                newset.add(set.get(val-1));
                remains --;
            }
            else 
            {
                i -= thresh;
            }
        }
        toRet.add(newset);
    }

    return toRet;

}

谁能帮我调试这个函数或建议另一种算法来迭代生成大小 k 个子集？

编辑:我终于让这个函数工作了，我必须创建一个与 i 相同的新变量来进行 i 和 thresh 比较，因为 python 处理循环索引的方式不同。

Answer 1

首先，如果您打算对列表进行随机访问，您应该选择一个能够有效支持该操作的列表实现。来自 LinkedList 上的 javadoc:

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

ArrayList 更节省空间，而且随机访问速度更快。其实，既然你事先知道长度，你甚至可以使用一个普通的数组。

到算法:让我们从简单的开始:你将如何生成大小为 1 的所有子集？大概是这样的:

for (int i = 0; i < set.length; i++) {
    int[] subset = {i};
    process(subset);
}

其中 process 是一种对集合执行某些操作的方法，例如检查它是否比目前处理的所有子集“更好”。

现在，您将如何扩展它以适用于大小为 2 的子集？大小为 2 的子集和大小为 1 的子集之间有什么关系？好吧，任何大小为 2 的子集都可以通过删除其最大元素变成大小为 1 的子集。换句话说，每个大小为 2 的子集可以通过获取大小为 1 的子集并添加一个比集合中所有其他元素大的新元素来生成。在代码中:

processSubset(int[] set) {
    int subset = new int[2];
    for (int i = 0; i < set.length; i++) {
        subset[0] = set[i];
        processLargerSets(set, subset, i);
    }
}

void processLargerSets(int[] set, int[] subset, int i) {
    for (int j = i + 1; j < set.length; j++) {
        subset[1] = set[j];
        process(subset);
    }
}

对于任意大小为 k 的子集，观察任何大小为 k 的子集都可以通过切分最大元素变成大小为 k-1 的子集。也就是说，可以通过生成所有大小为 k - 1 的子集来生成大小为 k 的所有子集，并且对于其中的每一个，以及大于子集中最大值的每个值，将该值添加到集合中。在代码中:

static void processSubsets(int[] set, int k) {
    int[] subset = new int[k];
    processLargerSubsets(set, subset, 0, 0);
}

static void processLargerSubsets(int[] set, int[] subset, int subsetSize, int nextIndex) {
    if (subsetSize == subset.length) {
        process(subset);
    } else {
        for (int j = nextIndex; j < set.length; j++) {
            subset[subsetSize] = set[j];
            processLargerSubsets(set, subset, subsetSize + 1, j + 1);
        }
    }
}

测试代码:

static void process(int[] subset) {
    System.out.println(Arrays.toString(subset));
}


public static void main(String[] args) throws Exception {
    int[] set = {1,2,3,4,5};
    processSubsets(set, 3);
}

但在对大型集合调用此方法之前，请记住子集的数量可能会增长得相当快。