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