Prev: The Muse of Musatov 'Mu'
Next: Musatov is using others' intelelctual property?. Come clean.
From: Peter Webb on 5 Oct 2009 21:19
None of this actually explicitly describes an enumeration, ie a bijection
between all possible combinations and the natural numbers 1 ... M! / N!
(K!)^N, which is what the poster asked for.

They do give a clue as to how this enumeration may be generated, but its not
trivial to extend it to an explicit bijection.



"Steve C" <smallpond(a)juno.com> wrote in message
news:hadrbn$q8h$1(a)news.eternal-september.org...
> James Dow Allen wrote:
>> On Oct 5, 8:35 pm, dvholten <i...(a)dvholten.de> wrote:
>>> makes sense. unfortunatly there a more than those meager 12 elements...
>>> i have 256 in 64 groups of 4. the large numbers themselves dont scare
>>> me -
>>
>> More generally suppose N groups of K.
>> The number you seek is
>> (KN)! / N!(K!)^N
>> ... I think! :-)
>>
>> James D. Allen
>
>
> Yes. A similar formulation is to choose N subsets of size K
> from a set of M, where M >= N K.
>
> M! / N! (K!)^N

From: Jussi Piitulainen on 6 Oct 2009 05:48
Peter Webb writes:

> None of this actually explicitly describes an enumeration, ie a
> bijection between all possible combinations and the natural numbers
> 1 ... M! / N! (K!)^N, which is what the poster asked for.
>
> They do give a clue as to how this enumeration may be generated, but
> its not trivial to extend it to an explicit bijection.

The following Python code implements exactly and completely the
algorithm that I described in my post. If that is not explicit enough,
it can be run with a given combination length and a list of objects to
print an extremely explicit representation of such a bijection, shown
partially below.

You may have some other sense of "explicit" in mind, and that is most
likely not trivial, as you say. A constant time formula to get the nth
partition would be interesting to programmers, too. Still, the Python
program below may well be what the OP wants, or they may be happy with
the earlier hints already. BigInteger sounds to me like they might be
using Java; Java does not have "yield" so one has to maintain state by
hand; can be done, is mere tedium.

I am aware that this is "not mathematics" though I am not clear on
what exactly that means. I also know that this "can be done in other
programming languages" but that is surely totally beside the point.

Python commands:

g = partitions(4, ['a','b','c','d','e','f','g','h','i','j','k','l'])
k = numbers(1)
for p in g: print k.next(), p

Function names may need to be qualified with a module name, depends on
how you run it. I sent the code to Python straight from Emacs.

Printed output:

1 [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'h'], ['i', 'j', 'k', 'l']]
2 [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'i'], ['h', 'j', 'k', 'l']]
3 [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'j'], ['h', 'i', 'k', 'l']]
.... snipped 5769 lines ...
5773 [['a', 'j', 'k', 'l'], ['b', 'f', 'g', 'i'], ['c', 'd', 'e', 'h']]
5774 [['a', 'j', 'k', 'l'], ['b', 'f', 'h', 'i'], ['c', 'd', 'e', 'g']]
5775 [['a', 'j', 'k', 'l'], ['b', 'g', 'h', 'i'], ['c', 'd', 'e', 'f']]

Code follows.

# generates partitions, into combinations of a requested length,
# of a given list; the last combination can be shorter
def partitions(length, objects):
if length >= len(objects):
yield [objects]
elif length > 0:
for comb, rest in combinations_from(1, length - 1, objects):
comb.insert(0, objects[0])
for combs in partitions(length, rest):
combs.insert(0, comb)
yield combs

# generates combinations of a requested length from a given list,
# together with the rest of the list
def combinations(length, objects):
for comb, rest in combinations_from(0, length, objects):
yield comb, rest

# generates combinations from a tail of a given list,
# together with the rest of the tail
def combinations_from(start, length, objects):
if length == 0 and len(objects) >= start:
yield [], objects[start:]
elif length > 0 and len(objects) > start:
for comb, rest in combinations_from(start + 1, length - 1, objects):
comb.insert(0, objects[start])
yield comb, rest
for comb, rest in combinations_from(start + 1, length, objects):
rest.insert(0, objects[start])
yield comb, rest

# drains a generator and returns the length of the sequence
def count(g):
length = 0
for whatever in g:
length += 1
return length

# generaters numbers
def numbers(start):
while True:
yield start
start += 1
From: Jim Ferry on 6 Oct 2009 10:03
On Oct 5, 6:18 pm, Steve C <smallp...(a)juno.com> wrote:
> James Dow Allen wrote:
> > On Oct 5, 8:35 pm, dvholten <i...(a)dvholten.de> wrote:
> >> makes sense. unfortunatly there a more than those meager 12 elements....
> >> i have 256 in 64 groups of 4. the large numbers themselves dont scare me -
>
> > More generally suppose N groups of K.
> > The number you seek is
> >   (KN)! / N!(K!)^N
> > ... I think!  :-)
>
> > James D. Allen
>
> Yes. A similar formulation is to choose N subsets of size K
> from a set of M, where M >= N K.
>
> M! / N! (K!)^N

Actually it's M! / ((M - NK)! N! K!^N).
From: Steve C on 6 Oct 2009 14:21
Jim Ferry wrote:
> On Oct 5, 6:18 pm, Steve C <smallp...(a)juno.com> wrote:
>> James Dow Allen wrote:
>>> On Oct 5, 8:35 pm, dvholten <i...(a)dvholten.de> wrote:
>>>> makes sense. unfortunatly there a more than those meager 12 elements...
>>>> i have 256 in 64 groups of 4. the large numbers themselves dont scare me -
>>> More generally suppose N groups of K.
>>> The number you seek is
>>> (KN)! / N!(K!)^N
>>> ... I think! :-)
>>> James D. Allen
>> Yes. A similar formulation is to choose N subsets of size K
>> from a set of M, where M >= N K.
>>
>> M! / N! (K!)^N
>
> Actually it's M! / ((M - NK)! N! K!^N).

My bad.

First  |  Prev  | 
Pages: 1 2 3
Prev: The Muse of Musatov 'Mu'
Next: Musatov is using others' intelelctual property?. Come clean.