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

java subset

2022-09-02 02:49:03

我正在研究一个难题，涉及分析所有大小的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和thresh比较，因为python处理循环索引的方式不同。

答案 1

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

所有操作的执行方式都与双链表的预期一样。索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引者为准。

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 的所有子集都可以通过生成大小 k - 1 的所有子集来生成，并且对于其中每个子集，以及每个大于子集中最大值的值，将该值添加到集合中。在代码中：

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

但是在大型集合上调用它之前，请记住，子集的数量可以增长得相当快。

答案 2

您可以使用 org.apache.commons.math3.util.Combinations。

例：

import java.util.Arrays;
import java.util.Iterator;

import org.apache.commons.math3.util.Combinations;

public class tmp {
    public static void main(String[] args) {
        for (Iterator<int[]> iter = new Combinations(5, 3).iterator(); iter.hasNext();) {
            System.out.println(Arrays.toString(iter.next()));
        }
    }

}

输出： [0， 1， 2] [0， 1， 3] [0， 2， 3] [1， 2， 3] [0， 1， 4] [0， 2， 4] [1， 2， 4] [0， 3， 4] [1， 3， 4] [2， 3， 4]