CODEWITHSUNDEEP
java
Unknown user
Unknown user

Reputation: 45321

Creating a set of sub-sets of size K from a given interval- using Set In Java

I'd love your help with this following problem:

I want to write in Java a method that will gets three values: first, last and K, so and creates all the sub-sets of size L of numbers within the bounded interval [first,last],

For example: If first=1, last=3 and K=2, so the result will be {1,2},{1,3},{2,3}.

Ok, So I decided that the result value of the function will be Set<Set<Integer>> , But I'm not sure of how exactly I need to do that, What is the algorithm and the right way to write it.

public static Set<Set<Integer>> generateKsubsets( 
int first, int last, int K){
Set<Set<Integer>> result = new HashSet<Set<Integer>>();

question 1: Is this the right Implemention of set to use in this case? To be honest, I'm not sure why do I use it here. Can I use here HasgTree? Is there any difference between theme in this case?

If(K==0) {

question 2: So here I would Like to return an empty set of the type that I defined, How should I do that?Can I add an empty set into the result set? 

return result;
}

And now the main question(3): I can't understand how my algorithm should work and how should I write it using this set.

Thank you for the help.

Upvotes: 0

Views: 61

Answers (1)

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37960

This sounds like homework (if it is, please tag it as such), so I'll only give a few hints:

  1. HashSet should do the job. However, note that in order for HashSet to work like a mathematical set (i.e. it cannot contain multiple occurrences of the same element), the element type (in this case, Set<Integer>) must have equals() and hashCode() implementations that tell the HashSet when two elements are equal. Most Set implementations do not have these methods implemented the way you'd expect, but you probably don't need it here. Just remember to not add the same set several times.
  2. new HashSet<Set<Integer>>() is an empty set. If you add a set to it, it is no longer empty.
  3. A set can be considered to be a binary number. If your range is 2-5, the elements you can select from are {2, 3, 4, 5}. Any subset of this set can be represented as a binary number with four digits, each digit corresponding to an element in the main set, and being 1 if the element is in the subset, and 0 if it is not. So the subset {3, 5} is 0101 (2 is absent, 3 is present, 4 is absent, 5 is present), and {2, 3, 4} is 1110. So if you can find a way of creating all binary numbers with the correct number of digits, and how to create a subset based on each number, you have your algorithm.

Upvotes: 1

Related Questions