public static List<List<String>> distrib( int n, int k, int p ) { if (p > n) ret

Question

public static List<List<String>> distrib( int n, int k, int p ) {
if (p > n) return new ArrayList<List<String>>();
if (k ==1) return new ArrayList<List<String>>(){{add(new ArrayList<String>(){{add(String.valueOf(n));}});}};
List<List<String>> L1 = distrib(n,k,p+1);
List<List<String>> L2 = distrib(n-p,k-1,0);
for (List<String> list : L2) list.add(String.valueOf(p));
L1.addAll(L2);
return L1;
}

Explain in plain English the logic for enumerating distributions.

Explanation / Answer

The value n represents the sum of digits of a list
The value k represents the number of digits of a list
The value p represent that last digit of any digit will be greater or equal to p

The output of the code will give all possible enumerations such that last digit of any enumeration is greater or equal to p, the number of digits in enumeration is equal to k and the sum is equal to n.

Now, the border cases are handled as

1) The p>n condition returns an empty list of lists( trivial)

2) The k==1 condition returns a list of lists which contains only 1 list, and that list contains only 1 value which is n = p.

Now, the list of lists are made-

1) L1 returns all possible such that the last digit is greater than p

2) L2 returns all possible such that the last digit is equal to p

2) is achieved by making all enumerations of sum n-p and digit k-1, so that we can add p as the last digit in each place.

All the lists are appended and returned.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.