Nested loop conversion to recursive function in Java

Question

I can't seem to figure out properly how to convert this nested loop into a recursive function in Java?

ArrayList<House[]> houseList = new ArrayList<House[]>();
        for (House h0 : houses) {
            if (h0.getPosition() == 0) {
                for (House h1 : houses) {
                    if (h1.getPosition() == 1) {
                        for (House h2 : houses) {
                            if (h2.getPosition() == 2) {
                                for (House h3 : houses) {
                                    if (h3.getPosition() == 3) {
                                        for (House h4 : houses) {
                                            if (h4.getPosition() == 4) {
                                                House[] list = new House[]{h0,h1,h2,h3,h4};
                                                houseList.add(list);
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

At this moment the houses object contains 133 elements, and the combinations given after the nested loop execution gives me 9810801 possibilities. How would this has to be written recursively to be usable for more than 5 times?

Answer 1

Acctually @Wilson answer wasn't correct after all. After a bit of trial and error I came up with a solution myself. Here's the recursive function of the code:

private void recursiveFunc(ArrayList<House> houses,ArrayList<House[]> resultList,House[] tempList, int pos, int maxPos) {
        for (House h : houses) {
            if (h.getPosition() == pos) {
                tempList[pos] = h;
                if (pos < maxPos-1) {
                    recursiveFunc(houses,resultList,tempList,pos+1,maxPos);
                }
                else if (pos == maxPos-1) {
                    House[] resultHouse = new House[maxPos];
                    for (int i=0; i<maxPos; i++) resultHouse[i] = tempList[i];
                    resultList.add(resultHouse);
                }
            }
        }
}

And I execute the function as follows:

recursiveFunc(houses,solutionList,new House[numberOfPositions],0,numberOfPositions);

Answer 2

Since @Wilson asked how I'd do it, here's a way that will work for any assortment of position values in the input, even if they're not contiguous. Call with something like:

List<House[]> houseTupleList = new HouseTupleListBuilder()
    .addAll(houses)
    .build();

The output tuples will contain values for the populated positions in ascending order.

Note that if a position number is missing entirely in the input (e.g. in the example there were only houses with positions 0,1,3,4), this code will happily produce tuples using only the present values (e.g. in my example, they would be 4-tuples). If you don't want that, you should call the builder's method expectPosition(i) for all expected positions i. Then if the input is lacking any position, the output will be empty, just as the OP's version.

class HouseTupleListBuilder {
  private final NavigableMap<Integer, List<House>> housesByPosition = new TreeMap<>();

  HouseTupleListBuilder addAll(Collection<House> houses) {
    for (House house : houses) {
      expectPosition(house.getPosition());
      housesByPosition.get(house.getPosition()).add(house);
    }
    return this;
  }

  HouseTupleListBuilder expectPosition(int i) {
    housesByPosition.putIfAbsent(i, new ArrayList<>());
    return this;
  }

  List<House[]> build() { return new TupleEnumerator().enumeration(); }

  private class TupleEnumerator {
    private final Map<Integer, House> houseByPosition = new TreeMap<>();
    private final List<House[]> tuples = new ArrayList<>();

    private void enumerateFor(NavigableSet<Integer> positions) {
      if (positions.isEmpty()) {
        tuples.add(houseByPosition.values().toArray(new House[0]));
        return;
      }
      int first = positions.first();
      for (House house : housesByPosition.get(first)) {
        houseByPosition.put(first, house);
        enumerateFor(positions.tailSet(first, false));
      }
    }

    private List<House[]> enumeration() {
      enumerateFor(housesByPosition.navigableKeySet());
      return tuples;
    }
  }
}

Answer 3

You have a list of House with position with either 0, 1, 2, 3, 4. Let me use a annotation of H{i} to represent a House with position i which 0 <= i <= 4.

If your input list is

[ H{0}, H{1}, H{2}, H{3}, H'{3}, H{4}, H'{4} ] 

which H' is another house

the result is

[
  [ H{0}, H{1}, H{2}, H{3}, H{4} ], 
  [ H{0}, H{1}, H{2}, H{3}, H'{4} ],
  [ H{0}, H{1}, H{2}, H'{3}, H{4} ],
  [ H{0}, H{1}, H{2}, H'{3}, H'{4} ],
]

This give me following information:

1. When iterate to H{3}, it find a House with next position, i.e. 4.
2. When iterate to H{4}, it will create the 1st list and store the houses with a position of 0, 1, 2, 3 iterated previously.
3. After reach H{4}, it will find another House with position 4, i.e. H'{4}, and create 2nd list and store the houses iterate previously except H{4}.
4. When reach the end of the list, it is back to H'{3} and iterate the list again to create 3rd and 4th list.

From #2, we know that:

1. We need to create a list to store the House if house position = 4
2. There should be a buffer to store the House with position 0, 1, 2, 3, iterated before. buffer[0] will store H{0}, buffer[1] will store H{2}, etc.

From #3, we know that:

If reach House with position 4, the list will further iterate until reach the end of the list.

We can have a base function as follows:

public static List<House[]> foo(House[] houses, List<House> buffer) {
    List<House[]> list = new ArrayList<House[]>();
    for (House house : houses) {
        if (house.getPosition() == buffer.size()) {
            buffer.add(house);
            if (house.getPosition() == 4) { 
                list.add(buffer.toArray(new House[buffer.size()]));
                buffer.remove(buffer.size() - 1);
            } 
        }
    }
    return list;
}

What the above do?

for (House house : houses) {
    if (house.getPosition() == buffer.size()) {
        buffer.add(house);

At the very beginning, buffer is empty with size = 0. If it find a House with position 0, it will be stored into the buffer and the buffer size becomes 1. When the list iterate to next House with position = 1 (the buffer size), it will be stored. Otherwise, find another House that match the condition.

if (house.getPosition() == 4) { 
    list.add(buffer.toArray(new House[buffer.size()]));
    buffer.remove(buffer.size() - 1);
} 

As mentioned, a list will be created to store the House in the buffer if there is a House with position 4. buffer.remove(buffer.size() - 1) is to remove the last House with position 4 such that another House can be stored into buffer.

So far, no recursive call is in our function since the case for House with position 4 do not need it.

Let's look back to #1 and #4. We know that:

If reach a House with position other than 4, it find a House with next position and create a list when iterate to House with position 4.

It means that our base function will be called if a House with position other than 4. So, we can modify our function as follows:

public static List<House[]> foo(House[] houses, List<House> buffer) {
    List<House[]> list = new ArrayList<House[]>();
    for (House house : houses) {
        if (house.getPosition() == buffer.size()) {
            buffer.add(house);
            if (house.getPosition() == 4) { // base case, no recursive call
                list.add(buffer.toArray(new House[buffer.size()]));
                buffer.remove(buffer.size() - 1);
            } else { // recursive case
                list.addAll(foo(houses, buffer));
            }
        }
    }
    if (buffer.size() > 0) {
        buffer.remove(buffer.size() - 1);
    }
    return list;
}

In summary, we have 2 case for the problem. One is the base case to handle House with position 4 and another case is to handle House with position other than 4 which need a recursive call.

Recursive function normally divide problem into cases. The function calls itself recursively on a smaller list of Houses until reaching the base case. Hope this can help.