[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]
----
Here's a shorter version:

 proc subsets {l} {
     set subsets [list [list]]
     foreach e $l {
         foreach subset $subsets {
             lappend subsets [lappend subset $e]
         }
     }
     return $subsets
 }

----

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]
 }
----
There's also a neat iterative solution:

 proc subsets2 {l n} {
     set subsets [list [list]]
     set result [list]
     foreach e $l {
         foreach subset $subsets {
             lappend subset $e
             if {[llength $subset] == $n} {
                 lappend result $subset
             } else {
                 lappend subsets $subset
             }
         }
     }
     return $result
 }
----
[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:

   * In 3D, I have the set of all points (x,y,z) that fulfill all of the following conditions:

   x+y+z  >= 1
   2x-y+z >= 0
   y-z    >= 1  
   x+2z   >= 0

   * Does this set of conditions specify something like a tetraeder or not? How easy is it to determine if it does or not?

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 Hellstrom: 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.)

''[DKF] notes that:'' Four inequalities is the minimum number to get a finite space, and will form a (usually irregular) tetrahedron if a solution exists at all...

----
[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
 }
----
The power set of    {a b c d e}

will give rise to:

   {{a} {b} {c} {d} {e} {0} }
   {{a b} {a c} {a d} {a e} {b c} {b d} {b e} {c d} {c e} {d e} {a b c d e
----
[TV] Just as a remark because some ideas would seem relevant, but I'm sure some would easily lead astray: the linear programming area may be of inportance to supercomputer programmers, and in that are I'm only 

In physicist sense, every reasonable informed physicist is not going to waste all too much attention practically doing group considerations, about which a lot of literature exists, much not all too practical for real interesting or hip problems. The whole idea of using many of such mathematical constructs or 'tools' comes from a century ago, when pen and paper were physicists only aid. Proofwise in the are of computers I wouldn't expect the holy grail from it anywhere, and certainly not when the subject in question has no understanding idea of turing machines and von Neumann, which is of later date, and practical computer use. That is what it was made for. After groups came Schoedinger eq solving stuff I'd sum up, and after computational geometry integral calculus, which are both imo interestin. Unless of course it is about taking mind set to think about hyperplane divided multidimensional spaces, but then I'd say that often problems boil down to traveling salesman kind of considerations in practice, because then the integer coordinated would often act as a sort of network links. Then again a good algebraic manipulator and a good mind using may be interesting.

[Category Mathematics]