// enumerate the different combinations // for select k objects from the set of
ID: 3702273 • Letter: #
Question
// enumerate the different combinations
// for select k objects from the set of objects given in list L
public static List<List<String>> comb(List<String> L, int k) {
if (k == 0) return new ArrayList<List<String>>(){{add(new ArrayList<String>( ));}};
if (L.size() == k) return new ArrayList<List<String>>(){{add(new ArrayList<String>(L));}};
List<List<String>> L1 = comb(L.subList(1,L.size()),k);
List<List<String>> L2 = comb(L.subList(1,L.size()),k-1);
for (List<String> list : L2) list.add(L.get(0));
L1.addAll(L2);
return L1;
}
Q.Study the given Java codes. Explain in plain English the logic for enumerating combinations of a certain size for a given set.
Explanation / Answer
The logic is:
While choosing K objects from a list of say N objects in the list L, we are excluding the first object and from the remaining N-1 objects, we are choosing K objects in each list of L1, and K-1 objects in each list of L2, and then we are including the first object which we excluded from L into each list of L2 (think of when L2 will be empty), which completes the K objects in each list of L2.
After this, we are concatenating all the objects from L1 and L2 to form a single List<List<String> > Object in which each List<String> consists of K objects.
Let's take a small example for this:
Let L = {"a","b","c"} and K = 2, then our answer should be {{"a","b"},{"b","c"},{"a","c"}} right?
Let's work on the code to find out what the answer is:
Case 1:
L={"a","b","c"}, K=2
K!=0
L.size()=3!=K
L1=comb({"b","c"},2)
Case 1.a:
L={"b","c"},K=2
K!=0
L.size()=2=K therefore this function will return {{"b","c"}}
Therefore, L1={{"b","c"}}
L2=comb({"b","c"},1)
Case 1.b
L={"b","c"},K=1
K!=0
L.size()=2!=K
L1=comb{"c",1)
Case 1.b.a
L={"c"}, K =1
K!=0
L.size()=1=K
Therefore this will return {{"c"}}
Therefore L1={{"c"}}
L2=comb({"c"},0)
Case 1.b.b
K==0, therefore this will return {{}}
Therefore L2={{}}
for(List<String> list: L2) list.add(L.get(0))
Therefore this for loop will modify L2 to {{"b"}}
L1.addAll(L2)
Therefore L1 will become {{"c","b"}}
Therefore L1={{"c","b"}}
Now L2=comb({"b","c"},1)
By similar logic L2 would be {{"b"},{"c"}}
Now we will add L[0] so L2 will become {{"a","b"},{"a","c"}}
Then L1.addAll(L2)
Therefore L1 will return {{"a","b"},{"a","c"},{"b","c"}} which is our required answer.
Hence done.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.