如何在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和脱粒比较，因为python处理循环索引的方式不同。

Answer 1

首先，如果您打算对列表进行随机访问，则应选择一个可以有效支持列表的列表实现。从LinkedList上的javadoc：

所有操作均按双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的位置为准。

ArrayList不仅空间效率更高，而且随机访问速度更快。实际上，由于您事先知道了长度，因此甚至可以使用普通数组。

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

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

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

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

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

但是在对大型集合进行调用之前，请记住，子集的数量可能会快速增长。