## subsequences

RS 2013-06-28 -- We can treat a list as a "sequence" of elements, and it can sometimes be useful to enumerate all subsequences of a sequence.

The code for the subseq function in Tally: a string counter gadget produces only contiguous subsequences, e.g. for the sequence A B C it returns

``` A
A B
B
B C
A B C```

Note that "A C" is missing.

The following code produces both contiguous and incontiguous subsequences. It basically assigns N bits to the N elements of the sequence, and uses each element if the bit is 1. The iteration can be done by counting from 1 to pow(2,N)-1, avoiding both trivial cases of the empty and the full sequence.

``` proc subseq lst {
set res {}
set max [expr pow(2,[llength \$lst])-1]
for {set i 1} {\$i < \$max} {incr i} {
set tmp {}
foreach bit [bits \$i [llength \$lst]] el \$lst {
if \$bit {lappend tmp \$el}
}
lappend res \$tmp
}
lsort \$res
}
#-- helper function
proc bits {x n} {
set res ""
while {[llength \$res] < \$n} {
set res "[expr {\$x%2}] \$res"
set x [expr {\$x/2}]
}
return \$res
}```

Testing:

``` % bits 15 5
0 1 1 1 1

% subseq {a b c d}
a {a b} {a b c} {a b d} {a c} {a c d} {a d} b {b c} {b c d} {b d} c {c d} d```

 Category Algorithm