# Programming Challenges

18 Jul 2013

## Permutations and combinations

To illustrate how to generate all combinations, see the following code that prints out all possible subsets of the Teenage Mutant Ninja Turtles.

``````public class TMNTDemo {
String[] tmnt = { "donatello", "leonardo", "michaelangelo", "raphael" };
int nTmnt = tmnt.length;

/*
* Prints all 2^n subsets of the Teenage Mutant Ninja Turtles
*/
public static void main(String[] args) {
new TMNTDemo().run();
}

public void run() {
}
}

StringBuilder sb = new StringBuilder();

for (int i = 0; i < nTmnt; i++) {
if ((mask & (1 << i)) != 0) {
sb.append(String.format(" %15s", tmnt[i]));
} else {
sb.append(String.format(" %15s", ""));
}
}

return sb.toString();
}

}
``````

Here is the Java code for the next permutation. Feel free to treat it as a black box, but if you’d like to learn more check here or here.

``````private boolean nextPerm(int[] a) {
if (a.length <= 1) return false;
int i = a.length - 1;
while (a[i - 1] >= a[i]) {
if (--i == 0) return false;
}
int j = a.length;
while (a[j - 1] <= a[i - 1]) {
if (--j == 0) return false;
}
swap(a, i - 1, j - 1);
i++;
j = a.length;
while (i < j) {
swap(a, i - 1, j - 1);
i++; j--;
}
return true;
}
``````

## For next class

• Read sections 3.1 and 3.2

Assigned problems:

• Lotto – Hints: