Today on Ray Myers Blog, (cadr life), he posted about returning lists of n-sized subsequences of a larger list. He used Java and tried to implement the recursive solution that he would normally write in Lisp or Haskell. He also issued a challenge to write this function without recursion. Well, my implementation is certainly not clean, but it is iterative, and is significantly faster for large lists (up to 10x). You can download my Java source file (with a main setup to time my version vs. his recursive version) here.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | private static <T> List<List<T>> mysubn(int n, List<T> li) { List<List<T>> ret = new ArrayList<List<T>>(); int size = li.size(); if (n == 0) { ret.add(new ArrayList<T>()); return ret; } if (li.isEmpty()) { return ret; } if (size < n) { return ret; } if (size == n) { ret.add(li); return ret; } /* I use counters to actually keep track of where I am in the list, * but iterators to actually get the elements. This is because we can't * assume what type of list we are accessing. list.get(n) is O(1) for * ArrayList, but O(n) for LinkedList, so we'd like to minimize these * as much as possible. * The reason we need to keep the counters and ending array, * instead of going until the iterators run out of elements, * is we only want them to the point where they could still make a * subsequence. */ ArrayList<ListIterator<T>> iters = new ArrayList<ListIterator<T>>(n); ArrayList<T> currElems = new ArrayList<T>(n); int[] counters = new int[n]; int[] endings = new int[n]; // Set up our initial values for(int i = 0; i < n; i++) { iters.add(li.listIterator(i)); currElems.add(iters.get(i).next()); counters[i] = i; endings[i] = size - n + i; } // Go until the we don't have enough elements left to make a subsequence while(counters[0] <= endings[0]) { List<T> sub = new ArrayList<T>(); for(int i = 0; i < n; i++) { sub.add(currElems.get(i)); } ret.add(sub); int c = n - 1; // Here we figure out how many of the counters (indexes) need updating. while(c > 0) { if(counters[c] < endings[c]) break; else c--; } // Update the left-most counter (index) counters[c]++; if(iters.get(c).hasNext()) currElems.set(c, iters.get(c).next()); c++; // Starting from the next left-most counter (if there is one), // set counter to be 1 more than previous counter, and reset // the iterator to start there as well. while(c < n) { // Reset the counter, and reset the iterator // to the new starting position. counters[c] = counters[c-1] + 1; iters.set(c, li.listIterator(counters[c])); // We make sure the iterator has another element. // The only time this will return false is when we are completely done // and the outer while is over. if(iters.get(c).hasNext()) currElems.set(c, iters.get(c).next()); c++; } } return ret; } |
