Latest content was relocated to https://bintanvictor.wordpress.com. This old blog will be shutdown soon.

Friday, April 2, 2010

recursive -> iterative -- level 2

In this example, first call's job need 2nd call's result. We build up another stack while depleting the args stack. This emulates the recursive descend->ascend.

` static List elements = new ArrayList(); static {  elements.add('a');  elements.add('b');  elements.add('c');  elements.add('d'); } static List combinations = new LinkedList(); static LinkedList> stack1 = new LinkedList>(); static LinkedList stack2 = new LinkedList(); static void interativePrintCombinations() {  stack1.add(elements);  while (!stack1.isEmpty()) {   List chars = stack1.removeLast();   char firstChar = chars.get(0);   System.out.println("stack2 = " + stack2);   if (chars.size() == 1) {    combinations.add("");    combinations.add("" + firstChar);    continue;   }   stack2.add(firstChar);   stack1.add(chars.subList(1, chars.size()));  }    while (!stack2.isEmpty()) {   append1CharToEveryString(stack2.removeLast());   System.out.println(combinations);  }   } private static void append1CharToEveryString(char firstChar) {  List tmp = new LinkedList();  for (String s : combinations) {   tmp.add(s + firstChar);  }  combinations.addAll(tmp); } static void getCombinations(List letters) {  if (letters.size() == 1) {   combinations.add("");   combinations.add("" + letters.get(0));   return;  }  getCombinations(letters.subList(1, letters.size()));    // here we absolutely need the nested call to complete before we proceed  List tmp = new LinkedList();  for (String s : combinations) {   tmp.add(s + letters.get(0));  }  combinations.addAll(tmp);    System.out.println(combinations); }`