Return-Path: <akur@indo.net.id>
Received: from server.indo.net.id ([202.159.34.10]) by sby.mega.net.id
          (Netscape Mail Server v1.1) with SMTP id AAA128
          for <yogy-n@sby.mega.net.id>; Thu, 3 Oct 1996 18:35:15 +0700
Received: from akur by server.indo.net.id (SMI-8.6/ED1-ID)
	id SAA13712; Thu, 3 Oct 1996 18:27:26 -0700
Date: Thu, 3 Oct 1996 18:27:26 -0700
Message-Id: <199610040127.SAA13712@server.indo.net.id>
X-Sender: akur@pop.jakarta.indo.net.id
X-Mailer: Windows Eudora Light Version 1.5.2
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: yogy-n@sby.mega.net.id
From: Andy Kurnia <akur@indo.net.id>
Subject: Subsets

I had no time to find and read the original Subsets problem, so I might miss
out some details (ie. using 0 instead of 1 or so).

Following is the rough algorithm I think I based my Internal00 and
Internal01 functions on:

Let's view the subsets as bits (as how they are stored internally in Set Of
0..31), so bit 0 (least significant bit, rightmost bit) is on if 1 is in the
set, etc. Assuming that there are 4 elements, we get 16 (= 1 shl 4) subsets:

  Dec = Bin  {Subset}
    0 = 0000 {}
    1 = 0001 {1}
    2 = 0010 {2}
    3 = 0011 {1,2}
    4 = 0100 {3}
    5 = 0101 {1,3}
    6 = 0110 {2,3}
    7 = 0111 {1,2,3}
    8 = 1000 {4}
    9 = 1001 {1,4}
   10 = 1010 {2,4}
   11 = 1011 {1,2,4}
   12 = 1100 {3,4}
   13 = 1101 {1,3,4}
   14 = 1110 {2,3,4}
   15 = 1111 {1,2,3,4}

Chronologically sorting the list, we get:

  Dec = Bin  {Subset}  Pattern
    0 = 0000 {}         0
    1 = 0001 {1}        1
    3 = 0011 {1,2}      2
    7 = 0111 {1,2,3}    3
   15 = 1111 {1,2,3,4}  4
   11 = 1011 {1,2,4}    5
    5 = 0101 {1,3}      6
   13 = 1101 {1,3,4}    7
    9 = 1001 {1,4}      8
    2 = 0010 {2}        9
    6 = 0110 {2,3}     10
   10 = 1010 {2,4}     11
   14 = 1110 {2,3,4}   12
    4 = 0100 {3}       13
   12 = 1100 {3,4}     14
    8 = 1000 {4}       15

Now examine the bits more closely. We have 16 subsets, so lets say S = 16.
Starting at the rightmost bit (remember that this stands for {1}) from top
to bottom, we have a 0, 8 1's, and 7 0's. Examining bit 1 (second rightmost
bit) of the patterns 1-8 (those who have {1}), we have a 0, 4 1's, and 3
0's. Getting further, we examine bit 2 of the patterns 2-5 (those who do
have {1,2}). We get a 0, 2 1's, and one 0. Let's examine bit 3 of patterns
3-4 (having {1,2,3}). We get a 0, one 1, and no 0.

The conclusion? If we have S subsets (where S is a whole even number), the
first one and the last (S/2 - 1) doesn't include the element, but the other
subsets (the second up to S/2) includes it. So we may split our S elements
into three parts: (1) The zero part (pattern 0), which is exactly ONE subset
and includes no further element, (2) the include part (patterns 1..S/2),
which is exactly S/2 subsets, includes the element we are currently
interested to, and may include more elements as if the part itself (1..S/2)
was processed from the root, and (3) the exclude part (patterns (S/2 +
1)..(S - 1)), which is exactly (S/2 - 1) subsets, excludes (does not
include) the element we are currently interested to, and may include more
elements as if the (S/2..(S - 1)) part was processed from the root.

Confused? My goal is achieved then.

Just kidding. Let's try a completely different method of understanding. The
above statement is indeed correct, but they aren't designed to be
immediately understood if read only once. So let's recapitulate what you
have read:

* LEVEL 1: Process(0..15)

Assume that we have four elements. Then we have (1 shl 4) subsets, or 16
subsets. So let's assume, at the first level, that S1 = 16. And also at the
first level we have nothing yet, or {}.

S1 = 16 may be divided into three part.

Part 1: The zero part, which is a single subset contains no other element
than what we have collected, or {}.

From this part we have 0 = {}.

Part 2: The include part, which are S/2 subsets containing the element we
are interested of, {1}, as the first element (remember that we are at the
first level). The remaining elements can be determined by going deeper and
processing the part.

This part gives us 1..8 = {1} + process(1..8).

Part 3: The exclude part, which are the remaining (S/2 - 1) subsets that
does not contain the element {1} but contains further elements, determined
by going deeper and processing (S/2..S) part.

This part gives us 9..15 = process(8..15), of course without {1}.

So level 1 gives us:

0 = {}
1..8 = {1} + process(1..8)
9..15 = process(8..15)

* LEVEL 2

0 = {} stays the way it was.
1..8 = {1} + process(1..8) gets processed as follows:
    1 =    {1} + {} = {1}
    2..5 = {1} + {2} + process(2..5) = {1,2} + process(2..5)
    6..8 = {1} + process(5..8)
9..15 = process(8..15) yields:
    8 = {} -> ignore! this never happens in real world, 8 gets processed above
    9..12 = {2} + process(9..12)
    13..15 = process(12..15)

* LEVEL 3

0 = {}, 1 = {1} stays.
2..5 = {1,2} + process(2..5) is:
    2 =    {1,2} + {} = {1,2}
    3..4 = {1,2} + {3} + process(3..4) = {1,2,3} + process(3..4)
    5 =    {1,2} + process(4..5)
6..8 = {1} + process(5..8) is:
    5 = {1} + {} -> ignore
    6..7 = {1} + {3} + process(6..7) = {1,3} + process(6..7)
    8 = {1} + process(7..8)
9..12 = {2} + process(9..12) is:
    9 = {2}
    10..11 = {2} + {3} + process(10..11) = {2,3} + process(10..11)
    12 = {2} + process(11..12)
13..15 = process(12..15) is:
    12 = {} -> ignore
    13..14 = {3} + process(13..14)
    15 = process(14..15)

* LEVEL 4 (at last!)

0 = {}, 1 = {1}, 2 = {1,2} stays so.
3..4 = {1,2,3} + process(3..4)
    3 = {1,2,3} + {} = {1,2,3}
    4 = {1,2,3} + {4} = {1,2,3,4} -> no further!! S5 = 1 is NOT even.
    no exclude part, already using zero part
5 = {1,2} + process(4..5)
    4 = {1,2} + {} -> ignore, as usual
    5 = {1,2} + {4} = {1,2,4}
6..7 = {1,3} + process(6..7)
    6 = {1,3}
    7 = {1,3,4}
8 = {1} + process(7..8)
    8 = {1,4}
9 = {2} stays unmodified.
10..11 = {2,3} + process(10..11)
    10 = {2,3}
    11 = {2,3,4}
12 = {2} + process(11..12)
    12 = {2,4}
13..14 = {3} + process(13..14)
    13 = {3}
    14 = {3,4}
15 = process(14..15)
    15 = {4}

So we get the chronological order!! To get subset #n, simply keep
subdividing 0..(1 shl x)-1 and entering the include/exclude part where n
belongs in the currently examined subrange until you get either to the zero
part or to the last element where Sx = 1.

To get the n from a subset, just keep subdividing the full range 0..(1 shl
x)-1, entering the corresponding subrange (include/exclude part) until you
get to the zero part or the last element. By then you should be examining
the subrange n..n, just get n from either the 'low' or 'high' argument.

Any questions? Please reply.



He got upset when I make fun of him for using chronologic
instead of lexicographic, then he sent me this mail :

Return-Path: <akur@indo.net.id>
Received: from server.indo.net.id ([202.159.34.10]) by sby.mega.net.id
          (Netscape Mail Server v1.1) with SMTP id AAA131
          for <yogy-n@sby.mega.net.id>; Mon, 7 Oct 1996 22:45:16 +0700
Received: from akur by server.indo.net.id (SMI-8.6/ED1-ID)
	id WAA04018; Mon, 7 Oct 1996 22:37:06 -0700
Date: Mon, 7 Oct 1996 22:37:06 -0700
Message-Id: <199610080537.WAA04018@server.indo.net.id>
X-Sender: akur@pop.jakarta.indo.net.id
X-Mailer: Windows Eudora Light Version 1.5.2
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: yogy-n@sby.mega.net.id
From: Andy Kurnia <akur@indo.net.id>
Subject: My solution

Add these lines in front of my e-mail.

I use the term CHRONOLOGIC for two reasons. One, I rarely use the word
LEXICOGRAPHIC and second, LEXICOGRAPHIC is defined as: CHRONOLOGICALly found 
in dictionaries... :)

Whatever you say, Andy... 



Yet he's not satisfied and sent me another mail :

Return-Path: <akur@indo.net.id>
Received: from server.indo.net.id ([202.159.34.10]) by sby.mega.net.id
          (Netscape Mail Server v1.1) with SMTP id AAA152
          for <yogy-n@sby.mega.net.id>; Tue, 8 Oct 1996 14:42:42 +0700
Received: from akur by server.indo.net.id (SMI-8.6/ED1-ID)
	id OAA01810; Tue, 8 Oct 1996 14:34:31 -0700
Date: Tue, 8 Oct 1996 14:34:31 -0700
Message-Id: <199610082134.OAA01810@server.indo.net.id>
X-Sender: akur@pop.jakarta.indo.net.id
X-Mailer: Windows Eudora Light Version 1.5.2
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: yogy-n@sby.mega.net.id
From: Andy Kurnia <akur@indo.net.id>
Subject: Re: My solution

Correction to: Add these lines in front of my e-mail.

I use the term CHRONOLOGIC for two reasons. One, I rarely use the word
LEXICOGRAPHIC and second, LEXICOGRAPHIC is defined as: CHRONOLOGICALly found
in dictionaries if you read it in the proper sequence (ie. from the first
entry to the last entry)... btw, Length('CHRONOLOGIC') <
Length('LEXICOGRAPHIC') :)

Can you believe this guy?