如何找到指定长度的所有子集？

Question

我在 previous question 中问过这个问题。我想找到指定长度的所有子集。

Damien 用 C++ 给我写了一个 nice answer，我正在尝试转换它，但没有成功。这是我的尝试：

import java.util.*;

public class Subset {
    void getSubsetAux(ArrayList<ArrayList<Integer>> s, int n, int k, int i,
                      ArrayList<Integer> dom, ArrayList<Integer> cs) {
        if(n<k) return;
        if(k == 0) {
            s.add(cs);
            return;
        }

        getSubsetAux(s, n-1, k, i+1, dom, cs);
        cs.add(dom.get(i));
        getSubsetAux(s, n-1, k-1, i+1, dom, cs);
        cs.remove(cs.size() -1);
    }

    void getSubset(ArrayList<ArrayList<Integer>> s, int l, ArrayList<Integer> dom) {
        ArrayList<Integer> cs = new ArrayList<>();
        getSubsetAux(s, dom.size(), l, 0, dom, cs);
    }

    public void print(ArrayList<ArrayList<Integer>> l) {
        for (ArrayList<Integer> el: l) {
            System.out.println(el);
        }
    }

    public void run(String[] args) {
        ArrayList<Integer> dom = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();

        getSubset(ret, 3, dom);

        print(ret);
    }

    public static void main(String [] args) {
        Subset s = new Subset();
        s.run(args);
    }
}

输出：

[]
[]
[]
[]
[]
[]
[]
[]
[]
[]

预期输出：（不一定是这个顺序）

[3, 4, 5]
[2, 4, 5] 
[2, 3, 5] 
[2, 3, 4] 
[1, 4, 5] 
[1, 3, 5] 
[1, 3, 4] 
[1, 2, 5] 
[1, 2, 4] 
[1, 2, 3]

我认为这与我不了解 Java

中的输出参数有关

Answer 1

如果您只对结果而不是算法本身感兴趣，您可以使用像 CombinatoricsLib, Guava or Apache Commons 这样的库：

使用 CombinatoricsLib，代码可以像这样简单：

List<Integer> dom = Arrays.asList(1,2,3,4,5);
Generator.combination(dom)
         .simple(3)
         .stream()
         .forEach(System.out::println);

得到输出：

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

但是如果你有兴趣自己实现算法，可能这个post是神读：https://www.baeldung.com/java-combinations-algorithm

Answer 2

如here所述，您正在多次向外部列表添加对同一内部 ArrayList 的引用。因此，当您更改内部列表时，您会在所有内部列表中看到它。

要获得您想要的结果，您应该创建一个新的临时内部列表：

if(k == 0) {
      ArrayList<Integer> temp = new ArrayList<Integer>(cs); 
      s.add(temp);
      return;
}

如何找到指定长度的所有子集？

How to find all subsets of a specified length?

java

list

set

subset