1

I asked about this in my previous question. I want to find all subsets of a specified length.

Damien wrote me a nice answer in C++, and I'm trying to convert that, but with no luck. Here is my attempt:

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

Output:

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

Expected output: (Not necessarily this order)

[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]

I assume this has something to do with me not understanding output parameters in Java

klutt
  • 30,332
  • 17
  • 55
  • 95

2 Answers2

1

If you are only interested in the results and not the algorithm itself, you could use a library like CombinatoricsLib, Guava or Apache Commons :

Using CombinatoricsLib the code could be as simple as:

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

to get the out put:

[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]

But if you are interested in implementing the algorithm by yourself, may be this post is a god read: https://www.baeldung.com/java-combinations-algorithm

Abra
  • 19,142
  • 7
  • 29
  • 41
Eritrean
  • 15,851
  • 3
  • 22
  • 28
  • Thanks a lot, but I cannot use 3rd party libraries. At least not if they are that big. :) – klutt Feb 03 '22 at 19:27
1

As explained here, you are adding a reference to the same inner ArrayList several times to the outer list. Therefore, when you are changing the inner list, you see it in all inner lists.

To get your desired result, you should create a new temporary inner list :

if(k == 0) {
      ArrayList<Integer> temp = new ArrayList<Integer>(cs); 
      s.add(temp);
      return;
}
Damien
  • 4,809
  • 4
  • 15
  • 20