Arjen Markus asked how to generate the set of subsets containing 1, 2, 3 ... elements. For example:
{a b c d e}will give rise to:
{{a} {b} {c} {d} {e}}
{{a b} {a c} {a d} {a e} {b c} {b d} {b e} {c d} {c e} {d e}}
...It does not seem quite trivial.
Kevin Kenny replies:
It's not quite clear from your question whether you need the entire power set (the set of all subsets) - organized by size, or whether you simply want, for some k, to enumerate the elements of a given list taken k at a time.
If you want the entire power set, you can enumerate it by counting up to 2**[llength list]:
proc subsets { list } {
# Check list size
if { [llength $list] > 32 } {
error "You don't really expect to list all 2**[llength $list] subsets, do you?"
}
# Calculate total number of subsets
set n [expr { 1 << [llength $list] }]
# Enumerate the subsets. If the list is { a b c }, then element
# 0 is the empty set, 1 is the set { a }, 2 is the set { b },
# 3 is { a b }, 4 is { c }, 5 is { a c }, 6 is { b c }, and 7
# is { a b c }.
for { set i 0 } { $i < $n } { incr i } {
set subset {}
for { set j 0 } { $j < [llength $list] } { incr j } {
if { $i & ( 1 << $j ) } {
lappend subset [lindex $list $j]
}
}
# Markus asks for subsets to be sorted out by size. Collate
# them into arrays.
lappend subsets([llength $subset]) $subset
}
set retval {}
for { set k 0 } { $k <= [llength $list] } { incr k } {
lappend retval $subsets($k)
}
return $retval
}
puts [join [subsets { a b c d }] \n]If you want to enumerate the combinations of the elements of $list taken $size at a time, then it is fairly trivial to enumerate them recursively:
proc subsets2 { list size } {
if { $size == 0 } {
return [list [list]]
}
set retval {}
for { set i 0 } { ($i + $size) <= [llength $list] } { incr i } {
set firstElement [lindex $list $i]
set remainingElements [lrange $list [expr { $i + 1 }] end]
foreach subset [subsets2 $remainingElements [expr { $size - 1 }]] {
lappend retval [linsert $subset 0 $firstElement]
}
}
return $retval
}
for { set i 0 } { $i <= 4 } { incr i } {
puts [subsets2 {a b c d} $i]
}Arjen Markus My question had to do with the second possibility. I had thought of a similar piece of code, but had found no time yet to test it and I was a bit troubled over some aspects - hence my remark that it did not seem quite trivial.
The background to this (again just something I have been playing with) is the following question: given a number of half-spaces, is it then possible to determine if the intersection of these is a finite volume or not?
Possibly this is too obscure, but look at it this way:
x+y+z >= 1 2x-y+z >= 0 y-z >= 1 x+2z >= 0
One way (I thought) the question can be solved is inspecting all subsets of 3 inequalities (because we have a 3D space). Just a puzzle to keep me occupied - I should consult a book about this type of problems first.
As I saw the Wiki page on the cartesian product of lists, I thought it might be nice to add the above question.
Lars Hellstr�m: It would not be possible to solve the problem quite that easy. Consider as a simple case that the inequalities define the unit cube in R^3. Then you need six inequalities (one for each side). Any 5-subset of the inequalities will however define a set with infinite volume.
I would recommend looking in a book on linear programming. An enormous amount of ingenuity has gone in to considering questions about sets defined by linear inequalities over the years and there are surprisingly many ways in which problems can be reformulated; I suspect that with the right twist to it your problem will be quickly solved by e.g. the simplex algorithm or Karmarkar's algorithm. (The ellipsiod method is fun too, but the cases in which that is best are rather odd.)
Arjen Markus A book I have right now focuses on "computational geometry". A few chapters deal with linear programming. I do realise that the problem is not simple, certainly not if you want to use a purely geometrical method.
Arjen Markus The method I was thinking about is discussed on the Geometry page...
KBK notes: If you have a set of constraint inequalities of the form
ax + by + cz >= d
then you can certainly use any linear-programming method to test each of the six problems
Minimize x subject to constraints; maximize x subject to constraints; minimize y subject to constraints; maximize y subject to constraints; minimize z subject to constraints; maximize z subject to constraints.
If any of the six programs is insoluble, all six are, and the constraints are inconsistent.
If any of the six problems is unbounded, the constraints fail to define a polytope, and the insoluble problem identifies an axis along which the constrained region is infinite in extent.
Otherwise, the constraints form a polytope and the bounding parallelipiped is defined by the solutions to the six linear problems. (And you probably have uses for the bounding parallelipiped, I suspect!)
For the special case of pairs, RS has this minicode:
proc pairs L {
set res {}
foreach i $L {
foreach j $L {
if {$i != $j} {lappend res $i-$j}
}
}
set res
}