在Java中高效地创建组合而不存在内存问题

Question

一些背景

我正在解决一个问题，我将集合存储在hashmap中，其中键是集合名，即Set1--

该程序的目的是从用户那里取一个值作为“阈值”，即2，它用于集合之间的最小共性。如果达到或超过阈值，程序建议集合之间合并。

我已经创建了一个组合生成器，它将生成集合名称之间的所有可能组合，以便与未考虑的顺序进行比较，即（Set1，Set2，），（Set1，Set3），（Set2，Set3），（Set1，Set2，Set3）。

然后使用这些组合集来实际比较这些集合。如果满足阈值，该组合将存储在单独的列表中，以作为可能的合并输出给用户。在输出之前，这些是删除子组合的逻辑，也就是说，如果（Set1，Set2，Set3）是一个可能的合并，那么你可以忽略其他3个子组合，因为这个超级组合已经覆盖了它。然后输出建议的合并。

问题所在

当我们达到一定数量的集合进行比较时，比如说超过17个集合，我们就会出现内存不足的问题，因为有数百万个组合正在被创建。我希望您能帮助我理解其他方法，或者我们如何改进这种方法。它可以工作，但效率不够：(

组合创建者

/**
 * Iterates through the setsToBeCompared ArrayList and gets all the combinations
 *
 * @return - ArrayList with all the possible combinations
 */
public ArrayList<String> generateCombinations(ArrayList<String> setsToBeCompared) {
    List<List<String>> temp = new ArrayList<>();
    ArrayList<String> a = new ArrayList<>();
    for (int i = 2; i <= 3; i++) {
        temp = calculateCombinations(setsToBeCompared, i);
        for (List<String> list : temp) {
            a.add(list.toString());
        }                       
    }
    return a;
        }

/**
 * Calculates all the combination given by the parameters
 *
 * @param values - the names of the sets to be compared
 * @param size   - where to start from
 * @return - List of all possible calculated combinations
 */
private List<List<String>> calculateCombinations(List<String> values, int size) {

    if (0 == size) {
        return Collections.singletonList(Collections.<String>emptyList());
    }

    if (values.isEmpty()) {
        return Collections.emptyList();
    }

    List<List<String>> combination = new LinkedList<List<String>>();

    String actual = values.iterator().next();
    List<String> subSet = new LinkedList<String>(values);
    subSet.remove(actual);
    List<List<String>> subSetCombination = calculateCombinations(subSet, size - 1);
    for (List<String> set : subSetCombination) {
        List<String> newSet = new LinkedList<String>(set);
        newSet.add(0, actual);
        combination.add(newSet);
    }

    combination.addAll(calculateCombinations(subSet, size));

    return combination;
}

Answer 1

所以，总结一下我作为评论发表的观点。

在您的情况下，生成集合的所有子集绝对不是一个选项，因为此类子集的数量将为~2^N。当N=50时，它比地球在纳秒内存在的时间还要长。

我假设从集合的子集切换到它们的项的子集。比如说，M子集有N不同的项，合并阈值是T。因此，您需要尝试大小的~N^Tk-组合，看看哪些子集可以通过项的组合合并，这对于小T是可以接受的。

算法将如下：

let D - collection of initial sets
let S - collection of distinct elements in sets across D

for each k-combination c over S {
   M = new M(c)          // merge object, which stores subset of merged sets and k-combination by which they are merged
   for each (s in D) {
      if (s.containsAll(c))
         M.sets.add(s)
   }
   if (M.sets.size > 0)  // some sets was merged through c
       merges.add(M)
} 

之后，获取所有可能的合并对，删除那些被其他合并完全覆盖的：

for each m in merges {
    for each m1 in merges {
        if (m.sets.containsAll(m1.sets))
            m1.markDeleted()
    }
}

Answer 2

像这样的东西怎么样（将使用更少的内存，但仍然需要检查大量的值-2^N）

import static java.util.stream.IntStream.range;

public class Subsets implements Iterator<List<Integer>> {

    private final int level;
    private final LinkedList<List<Integer>> queue = new LinkedList<>();


    public Subsets(int level) {
        this.level = level;
        range(0, level).forEach(i -> queue.add(Arrays.asList(i)));
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    public List<Integer> next() {
        List<Integer> list = queue.removeFirst();
        int maxValue = list.get(list.size() - 1);

        if(list.size() < level) {

            for (int k = maxValue+1; k < level; k++) {
                List<Integer> newList = new ArrayList<>(list);
                newList.add(k);
                queue.addFirst(newList);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Subsets s4 = new Subsets(4);
        while (s4.hasNext()) {
            System.err.println(s4.next());

        }
    }
}

要使用它，您需要将集合（键）的名称映射为整数。示例输出：

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