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
