(1 2) (1 3) (1 4) (1 5)This is not a red-herring example cooked up just to make Java look bad. This actually came up at work! I did something along these lines. Yuck.
(2 3) (2 4) (2 5)
(3 4) (3 5)
(4 5)
private static <T> List<List<T>> subn(int n, List<T> li) {
List<List<T>> ret = new ArrayList<List<T>>();
if (n == 0) {
ret.add(new ArrayList<T>());
return ret;
}
if (li.isEmpty()) {
return ret;
}
T x = li.get(0);
List<T> xs = li.subList(1, li.size());
for (List<T> sub : subn(n-1, xs)) {
sub.add(0, x);
ret.add(sub);
}
ret.addAll(subn(n, xs));
return ret;
}However, that was not the way my thoughts originally took shape. I think in Lisp.(def subn (n li)Then I moved it to Haskell for greater clarity.
(if (is 0 n) '(())
(no li) '()
(join (map [cons (car li) _] (subn (- n 1) (cdr li)))
(subn n (cdr li)))))
subn 0 _ = [[]]With great pain, I converted those three lines of Haskell into the ugly splatter of Java you saw above. Later on, I started playing around with Scala and gradually compacted the Java into something strikingly similar to its Haskell ancestor.
subn _ [] = []
subn n (x:xs) = map (x:) (subn (n-1) xs) ++ subn n xs
def subn[T](n: int, li : List[T]) : List[List[T]] = (n,li) match {
case (0,_) => List(Nil)
case (_,Nil) => Nil
case (_,x::xs) => (subn(n-1, xs) map (x :: _)) ::: subn(n, xs)
}The title of today's post refers to the inordinate amount of trouble it is to simply return "The list containing the empty list" in Java. I tried such monstrosities as these:Collections.singletonList(Collections.EMPTY_LIST) // List<List>The last option does give the correct type, but it causes a compiler warning and is not much less cumbersome than the naive approach, i.e.:
Arrays.asList(Collections.emptyList()) // List<List<Object>>
Collections.singletonList(new ArrayList<T>()) // List<ArrayList<T>>
Collections.singletonList((List<T>)new ArrayList<T>()) // List<List<T>>
List<List<T>> ret = new ArrayList<List<T>>();So here's a challenge for you Java developers out there. What would you change about the admittedly sloppy Java code at the beginning of this post? I'm issuing an all points bulletin to the refactoring mavericks (Mike, James), the simple-design visionaries (Steve), and the speed-freak optimizers (Dan). I wouldn't even mind seeing a C# version (Ethan), or an improvement on the Haskell (Eric).
ret.add(new ArrayList<T>());
return ret;
Incidentally, I know some people think recursion is hard to read. I'd love to see an iterative solution as well.
P.S. I realize that the comment boxes don't hold code blocks very well. Feel free to link to a solution.
Updates:
Based on your input, I am now happy to give three different ways of returning '(()) in one line. I am only including ways that would work in the context I gave (i.e. the inner list must be mutable). The last is my favorite because the others cause compiler warnings.
return Arrays.<List<T>>asList(new ArrayList<T>());Eric has blessed us with a version in Factor (not to be confused with my aversion to Factor). He also added a Haskell version using list comprehensions to achieve better laziness properties.
// Type safety : A generic array of ArrayListis created for a varargs parameter
return new ArrayList<List<T>>() {{add(new ArrayList<T>());}};
// The serializable class does not declare a static final serialVersionUID...
// Ricky points out that this is an "Eclipse warning".
return Collections.<List<T>>singletonList(new ArrayList<T>());
// No warnings :)
Meanwhile, back in Javaland, Dan suggested using SortedSet, particularly the subSet method. This seems to be a dead end in this case, but is certainly a useful corner of the Collection hierarchy.
After briefly attaining List Enlightenment, Thomas produced an implementation in Java with no recursion. Aside from being much longer and totally opaque, it also has worse performance charactoristics. It essentially produces every subsequence and then filters by length, similar to the Haskell one-liner suggested in the comments.
