CODEWITHSUNDEEP
javalistsetsubset
klutt
klutt

Reputation: 31379

How to find all subsets of a specified length?

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

Upvotes: 1

Views: 836

Answers (2)

Eritrean
Eritrean

Reputation: 16498

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

Upvotes: 1

Damien
Damien

Reputation: 4864

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

Upvotes: 1

Related Questions