| ||||||||
| A little amusing post about language syntax: http://cadrlife.blogspot.com/2008/03/re "Suppose you want a function to find all subsequences of a list with a certain length. For instance, the subsequences of (1...5) with length 2 are as follows." (1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5)In a lisp dialect: (def subn (n li)
(if (is 0 n) '(())
(no li) '()
(join (map [cons (car li) _] (subn (- n 1) (cdr li)))
(subn n (cdr li)))))
Haskell:subn 0 _ = [[]] subn _ [] = [] subn n (x:xs) = map (x:) (subn (n-1) xs) ++ subn n xsPython: def subn(n, a):
if not n: return [[]]
if not a: return []
return [[a[0]] + sub for sub in subn(n-1, a[1:])] + subn(n, a[1:])
The Scala version too uses pattern matching, showing how much it can be useful (it may be useful for D language too):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)
}
D version using my libs:import d.func: putr, map, not, range, xrange, select, BaseType, array;
T[][] subn(T)(int n, T[] a) {
if (!n) return new T[][](1, 0);
if (not(a)) return new T[][0];
return map((T[] s){return a[0..1] ~ s;}, subn(n-1, a[1..$])) ~ subn(n, a[1..$]);
}
If you want shorter lines you can use select (reverted from the 'list' name):T[][] subn2(T)(int n, T[] a) {
if (!n) return new T[][](1, 0);
if (not(a)) return new T[][0];
T[] s;
return select(a[0..1] ~ s, s, subn2(n-1, a[1..$])) ~ subn2(n, a[1..$]);
}
This version is able to digest any iterable:BaseType!(TyIter)[][] subn3(TyIter)(int n, TyIter iter) {
auto a = array(iter);
alias BaseType!(TyIter) T;
if (!n) return new T[][](1, 0);
if (not(a)) return new T[][0];
return map((T[] s){return a[0..1] ~ s;}, subn3(n-1, a[1..$])) ~ subn3(n, a[1..$]);
}
void main() {
putr( subn(2, range(5)) );
// Output: [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4],
// [2, 3], [2, 4], [3, 4]]
putr( subn2(3, range(5)) );
// [[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4],
// [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
putr( subn3(2, xrange(5)) );
// Output: [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4],
// [2, 3], [2, 4], [3, 4]]
} | ||||||||
comments: Leave a comment   |