Re: Unique sets from {1..n} ?
- From: rem642b@xxxxxxxxx (Robert Maas, see http://tinyurl.com/uh3t)
- Date: Mon, 11 Jul 2005 04:49:27 -0700
> From: "TC" <aatcbbtccctc@xxxxxxxxx>
> I need to generate every unique set of numbers, of the integer numbers
> 1 thru n inclusive.
The above is slightly ambiguous, but you included an example:
> Eg. if n=3 (to take a small example), I need to generate the 7 unique
> sets:
> {1} {2} {3} {1,2} {2,3} {1,3} {1,2,3}
Very good. That was one of the possible interpretations of
what you wrote, and shows that what you meant was that you want
to generate all subsets of {1, 2, 3} except not the empty set.
Why not the empty set? Why do you exclude it? Any practical reason?
Generating the set or list of subsets is trivial. (In fact if you are
using a language where a bitmask is a valid representation of a set,
then simply listing the integers from 1 to 7, together with including a
legend that says what object corresponds to which bit in the bitmask,
is a complete solution. Lisp is one such language, with built-in
functions to treat integers as bitmasks to represent sets, and also
other built-in functions to treat ordinary linked-lists as representing
sets.)
The hard part is expressing the sets in whatever way is required for
the user of this program. Is a bitmap sufficient, or does the bitmap
need to be converted to some other representation? In an implementation
of IP (InterNet Protocol), in the part of the code that deals with ACKs
of various packets, in fact a bitmap is exactly what is appropriate for
saying which set of packets have been acknowledged, so your program
might be a test rig that generates all possible combinations of of ACKs
of packets (but why omit the empty set??) and checks that the
packet-retransmit code does the right thing in each case. Or if you are
trying to generate pseudo-English sentences, and each bit represents a
feature, such as bit#1 is on if the Subject has an adjective in
addition to the article, bit#2 is on if the verb has a preposition with
an object as opposed to a preposition alone acting as adverb, bit#3 is
on if the verb has a regular adverb, so {1, 3} would generate a
sentence like:
The tiny mouse is always in.
whereas {2} would generate a sentence like:
The mouse is in the house.
(Sorry, that episode of 'Friends' came into my mind just now, you know
which one, right?)
So for the algorithm itself, you have two modes of doing it (recursive
and iterative), and two sequences to generate (lexicographic and Gray
code). I suggest you write a program that can do it all four possible
ways, not by writing four programs, but by writing two functions, one
iterative and one recursive, each of which takes a parameter specifying
whether to generate the results lexicographically or per Gray code.
Then you can have meta-program test-rig that generates all four
possible subsets of {recursive, GrayCode} to generate all four possible
program modes.
Oh, you didn't say whether the various subsets had to be generated in
any particular order. Another choice is to shuffle them into
pseudo-random sequence. There are 7! different sequences possible for
the 7 subsets. The mapping from any such sequence to any other is a
permutation on the 7 elements. These permuations form a GROUP.
So please tell us the intended application of this program you want.
.
- Follow-Ups:
- Re: Unique sets from {1..n} ?
- From: TC
- Re: Unique sets from {1..n} ?
- References:
- Unique sets from {1..n} ?
- From: TC
- Unique sets from {1..n} ?
- Prev by Date: Re: link error
- Next by Date: Re: Break into the Computer Industry - Get Hired Now
- Previous by thread: Re: Unique sets from {1..n} ?
- Next by thread: Re: Unique sets from {1..n} ?
- Index(es):
Relevant Pages
|
