[Information Index] [Generation Index] [COS homepage]

Information on Subsets of a set

A set is a collection of objects, and a subset is a sub-collection of those objects. For example if the collection consists of the three letter A, B, and C, written as {A,B,C}, then the possible subcollections are {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, and {A,B,C}. The number of subsets of an n element set is 2n since each element is either included in the subset or it isn't.

In the Object Server, the set from which subsets are made is always the set [n] of the first n positive integers (i.e., [n] = {1,2,...,n}). If bitstring output is selected, then each subset S is listed as a bitstring bn···b2b1 where bi = 1 if i is in S and bi = 0 if i is not in S. If subset output is selected, then each subset S (say of size k) is output as an ordered list {s1,s2,...,sk} of its elements.

The number of subsets of an n-set for n = 0,1,2,...,10, is 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. These, of course, are the powers of 2. This is sequence A000079(M1129) in Neil J. Sloane's database of integer sequences.

For lex (lexicographic) order, the algorithm used is well-known, and amounts to simply counting in binary. Far more interesting is Gray code order.

Gray Codes

In Gray code order successive subsets differ by exactly one element. There are many such Gray codes; the one we use is called The Binary Reflected Gray Code (or BRGC). The transition sequence of the BRGC is the sequence of positions of the bits that change. For n = 3 it is 1,2,1,3,1,2,1. Inductively, the sequence is defined as T(n+1) = T(n),n+1,T(n), with T(1) = 1. It is this sequence that is output when "transposition or bit change" output is selected.

Towers of Hanoi

In the towers of Hanoi puzzle, the problem is to move all disks from one peg to some other peg, subject to two rules. First, only one disk can move at each step. Secondly, a larger disk may not be placed atop a smaller disk.

Edouard Lucas invented the Towers of Hanoi in 1883.

There is a surprising connection between the BRGC and optimal (least number of moves) solutions to the Towers of Hanoi problem.

Bitstring
n···321
Subsets Bitchanges Towers of Hanoi
000
{}
1
001
{1}
2
011
{1,2}
1
010
{2}
3
110
{2,3}
1
111
{1,2,3}
2
101
{1,3}
1
100
{3}


This correspondence is best illustrated by looking at an example, such as the table above. Note that the number in the bitchange column corresponds to the the disk being moved, with the convention that the smallest disk is 1, and the largest is 3 (and, in general, that the largest disk is n).

Interesting Links:

Venn Diagrams

An order n Venn diagram is a collection of n simple closed curves in the plane with the following properties. (1) The curves partition the plane into 2n connected regions, and (2) Each subset S of {1,2,...,n} corresponds to a unique region formed by the intersection of the interiors of the curves in S.


Here we show a beautiful symmetric Venn diagram made from 5 congruent ellipses. Branko Grunbaum, a mathematician ot the University of Washington, was the first to show that there are symmetric Venn diagrams made from 5 congruent ellipses. The first diagram labels each region (except the very smallest, where the labels wouldn't fit) with the labels of all the ellipses that contain that region. On the right, the ellipses are colored according to the number of ellipses in which they are contained: grey = 0, yellow = 1, red = 2, blue = 3, green = 4, black = 5. Note that the number of regions colored with a given color corresponds to the appropriate binomial coefficient: #(grey) = #(black) = 1, #(yellow) = #(green) = 5, and #(red) = #(blue) = 10. For more on Venn diagrams see the Venn diagram page.


Programs available: [CAT]
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:13 PDT.
There have been 40342 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.