Date: Fri, 10 Oct 1997 16:24:20 -0500
From: [Permission pending]
To: rusin@math.niu.edu
Subject: a practical problem

Dave:
    Here is a small problem that I have encounterd in my
research that I could use some help on.  I have about 100
corn lines, numbered consecutively 1 to 100.  I have a
program that puts them into groups of various sizes.  I need
a way to uniquely identify each group, regardless of the
order in which group members are listed.  Up to 10 minutes
ago I was identifying each group with 3 numbers:  the number
of members in the group, the sum of the line numbers, and
the sum of the squared line numbers.  Thus a group with
members 6, 3, and 14 would be identified by 3 (number of
members), 23 (sum of line numbers) and 241 (sum of squares).
 However, after 6 months of doing this I just hit upon a
problem combination:  4, 9, 11 and 5, 7, 12 both add to 24
and their sum of squares is 218.  This made a mess of my
program, and the existence of one such combination means
there are surely others.  So, here's the problem:  how can I
uniquely code groups of this type (individual members
labeled 1 to 100, in groups of any size, regardless of the
order of the numbers) with a small number of code numbers (3
would be wonderful)?  To me this sounds like a fairly
standard cryptography problem, but I certainly haven't a
clue about its solution.  Let me know if anything crosses
your mind.  Thanks a lot.

[Permission pending]

==============================================================================
Date: Sat, 11 Oct 1997 00:55:56 -0500 (CDT)
From: Dave Rusin <rusin>
To: T80MAJ1@WPO.CSO.NIU.EDU
Subject: Re:  a practical problem

>I have about 100
>corn lines, numbered consecutively 1 to 100.  I have a
>program that puts them into groups of various sizes.  I need
>a way to uniquely identify each group, regardless of the
>order in which group members are listed.  

So your group could be absolutely any subset of {1, 2, ..., 100}?
There are  2^100  such subsets. If you want to assign every one
of them a unique label, you need  2^100  different labels (over 10^30).
When you say you'd like to do this
> with a small number of code numbers (3 would be wonderful)? 
do you mind if those code numbers were large? Three 10-digit numbers
allow precisely 10^30 combinations; five 6-digit numbers would be
easier to read, I imagine. (If this is in a program which, for example,
restricts integers to  2^16, you'd need  7  code numbers to store this.)

There is a very easy way to identify each of your groups with a distinct
number smaller than 2^30. Simply associate to a set  S = {a, b, c, ...}
the number  2^a + 2^b + 2^c + ...  So for example
	{ }               <-->  1
	{4,9,11}          <--> 2^4 + 2^9 + 2^11 = 2576
	{5,7,12}          <--> 2^5 + 2^7 + 2^12 = 4256
	{1, 2, ..., 100}  <--> 2^100 - 1 = 1267650600228229401496703205375

(which you might prefer to write e,g, as 1267650 600228 229401 496703 205375,
say  -- five 6-7 digit codes.) Note that in this system, the inclusion of a 
single element with a very large number will give the set a very large code.
Decoding is easy, since the members of a given group are read off from the
bit pattern of the group label. (XOR commands might even be available in
the programming language.)

dave