Nest for-loop n-times, recursive calls, and beyond
It is easy to write the code to nest the for-loop n-times if you know the value of n. For example, if you know n=3, then the code is as follows:
for(int i=0; i<length; i++){
for(int j=0; j<length; j++){
for(int k=0; k<length; k++){
}
}
}
But what if the value of n is just a variable? How to write code for this?
It can be solved using recursive function. The basic code is as follows:
public void func(int count, int n){
if( count == n){
return;
}
for(int i=0; i<length; i++){
func(count+1,n);
}
}
And you just need to call func(0,n);
The basic idea here is to pass the count number as an argument to the next recursive call. And the
next recursive call can determine if to finish or continue based on that value.
Here we only pass the count number to the subsequent call. We can also pass other values in the arguments to the next
recursive call and solve some quite complex problems! If we make some twists in the actual body of the function, this
code can be even more powerful!
We show several algorithms here.
N-Queen Problem
Problem: Position n queens on a chessboard so that no two are in the same row, column, or diagonal.
Inputs: positive integer n.
Outputs: All possible ways n queens can be placed on an n*n chessboard so that no two queens threaten each other.
Solution: We use col[i] to denote the column position of the queen in i-th row. We will pass col[] as an argument to the next recursive call so it can be used to check if the positions are valid.
public void func(int count, int[] col){
if ( count == col.length){
printOutResult(col);
return;
}
for(int i=0; i<col.length; i++){
col[count] = i;
if ( goodSoFar(col, count)){
func(count+1, col);
}
}
}
private void printOutResult(int[] col){
for(int i=0; i<col.length; i++){
System.out.println(" " + col[i]);
}
}
private boolean goodSoFar(int[] col, int count){
for(int i=0; i<count; i++){
if ( col[i] == col[count]){ // same column
return false;
}
if ( Math.abs(col[i] - col[count]) == count - i){ // diagonal
return false;
}
}
return true;
}
public void solve(int n){
int[] col = new int[n];
func(0, col);
}
Test Results:
Given n=4, it will give the answers: 2 4 1 3 and 3 1 4 2
Notes:
- We pass the intermediate value in col[] to the next call.
- col[] also holds the final results.
- Algorithm books call the functions like "goodSoFar" as backtracking.
Permutation Problem
Problem: Print out all the permutations of some letters.
Inputs: An array of characters inChars of length n, where n is a positive integer
Outputs: All possible permutations of these characters.
Solution 1:
public void func(int count, boolean[] used, char[] chs, StringBuilder sb){
if ( count == used.length){
System.out.println(sb.toString());
}
for(int i=0; i<chs.length; i++){
if( !used[i]){
sb.append(chs[i]);
used[i] = true;
func(count+1, used, chs, sb);
used[i] = false;
sb.setLength(count);
}
}
}
public void solve(char[] inChars){
boolean[] used = new boolean[inChars.length];
StringBuilder sb = new StringBuilder();
func(0, used, inChars, sb);
}
Test Results:
For inChars = {'a','b','c'}, the output is
abc acb bac bca cab cba
Notes:
- The above code for permutation is a little different from the n-Queens problem. In the n-Queens problem, each subsequent loop still goes throug all the positions, whereas here, the subsequent loops only go through partial values. They use the used[] array to check if a value has already been used.
Solution 2: Solution 1 is good but a little bit convoluted. We can actually use the exact same pattern as in the n-Queens problem to sovle the problem. The code is below:
public void func(int count, int[] result, char[] chs) {
if (count == result.length) {
printResult(result, chs);
return;
}
for (int i = 0; i < chs.length; i++) {
result[count] = i;
if (goodSoFar(count, result)) {
func(count + 1, result, chs);
}
}
}
private boolean goodSoFar(int count, int[] used) {
for (int i = 0; i < count; i++) {
if (used[i] == used[count]) {
return false;
}
}
return true;
}
private void printResult(int[] result, char[] chs) {
for (int i = 0; i < result.length; i++) {
System.out.print(chs[result[i]]);
}
System.out.println();
}
public void solve(char[] inChars) {
int[] result = new int[inChars.length];
for (int i = 0; i < result.length; i++) {
result[i] = -1;
}
func(0, result, inChars);
}
Test Results:
For inChars = {'a','b','c'}, the output is
abc
acb
bac
bca
cab
cba
Notes:
- The code is very similar to the n-Queens problem. We store the intermediate results in the array "result" and pass it to the next recursive call. The "result" array stores the index of the char in the original input "inChars" array.
- Again, the "goodSoFar" method is our pruning method. It can be modified for other variations of permutation. For example, if no duplicate character is allowd, we can change the code.
- This algo is a little bit less efficient than solution 1 because the method "goodSoFar" needs to go through an array to check values. But the code is very clear and easy to understand.
Combination Problem
Inputs: An array of characters inChars of length n, where n is a positive integer
Outputs: All subsets except the empty subset. There should be 2^n - 1 subsets.
Solution:
public void func(int count, boolean[] flags, char[] chs){
if ( count == flags.length){
printResult(flags, chs);
return;
}
flags[count] = true;
func(count + 1, flags, chs);
flags[count] = false;
func(count + 1, flags, chs);
}
private void printResult(boolean[] flags, char[] chs){
for(int i=0; i<flags.length; i++){
if ( flags[i]){
System.out.print(chs[i]);
}
}
System.out.println();
}
public void solve(char[] inChars){
boolean[] flags = new boolean[inChars.length];
func(0,flags, inChars);
}
Test Results:
For inChars = {'a','b','c'}, the output is
abc ab ac a bc b c
Notes:
- To form a subset, an element in the original set is either selected or not selected. We use "flags" in the code to denote whether each element is selected or not.
- The "func" method does not have a for-loop as in the previous examples. But essentially it is looping through the array {true, false}.
Knapsack Problem
Problem: Given a collection of items, each with its weight and value, find a subset of these items so that the total value of the items in this subset is a max value under the condition that their total weight does not exceed a given limit.
Inputs: int[] weights, int[] values, int weightLimit
Output: int maxValue and the items shosen
Solution: This is essentially a combination problem. The code is below.
public class Knapsack(){
private int currentMaxValue;
private boolean[] chosen;
private boolean[] selected;
public void func(int count, final int weightLimit, final int[] weights,
final int[] values, int weightSoFar, int valueSoFar,
boolean[] selected) {
if (count == selected.length) {
if (valueSoFar > currentMaxValue) {
updateResult(valueSoFar, selected);
}
return;
}
selected[count] = true;
// if next item makes it overweight,stop
if (weightSoFar + weights[count] > weightLimit) {
if (valueSoFar > currentMaxValue) {
updateResult(valueSoFar, selected);
}
} else {
func(count + 1, weightLimit, weights, values, weightSoFar
+ weights[count], valueSoFar + values[count], selected);
}
selected[count] = false;
func(count + 1, weightLimit, weights, values, weightSoFar, valueSoFar,
selected);
}
private void updateResult(int valueSoFar, boolean[] flags) {
this.currentMaxValue = valueSoFar;
// can also use the following System.arraycopy instead of the for-loop
// System.arraycopy(flags, 0, chosen, 0, flags.length);
for (int i = 0; i < flags.length; i++) {
chosen[i] = flags[i];
}
}
public void solve(int[] weights, int[] values, int weightLimit) {
Assert.isTrue(weights != null && values != null
&& weights.length == values.length);
currentMaxValue = Integer.MIN_VALUE;
chosen = new boolean[weights.length];
selected = new boolean[weights.length];
func(0, weightLimit, weights, values, 0, 0, selected);
System.out.println("The max value is " + currentMaxValue + " chosen is "
+ Arrays.toString(chosen));
}
}
Test Result:
public void testKnapSack() {
int limit = 20;
int[] weights = { 2, 5, 23, 10, 6, 7, 1 };
int[] values = { 2, 343, 234, 1, 21, 6, 8 };
solve(weights, values, limit);
}
Output:
Max values is 378 chosen is [false, true, false, false, true, true, true]
The above results mean that items at the positions 2,5,6,7 are chosen.
