Prev: The Muse of Musatov 'Mu'
Next: Musatov is using others' intelelctual property?. Come clean.
From: dvholten on 5 Oct 2009 09:18
hi folks,

here is a combinatorics question for the experts:
lets assume we have a set of objects
a b c d e f g h i j k l
these shall be put in sets of equal size (3 sets of 4 for example) how
can i enumerate(generate) the combinations of sets?
that is
abcd efgi hjkl
abcd efgj hikl
and so on.

'abcd' and 'dbca' are equal
and
'abdc' 'efkl'
is the same as
'klef' 'dbca'

how many enumerations are there? to see if the generator is correct..

i found a lot of examples giving answers to _similar_ questions, but
none is useful enough for me. unfortunately i cant put together the
pieces which are obviously in front of me.

any literature links are welcome.

many thanks
dvholten
From: bert on 5 Oct 2009 09:25
On 5 Oct, 14:18, dvholten <i...(a)dvholten.de> wrote:
> hi folks,
>
> here is a combinatorics question for the experts:
> lets assume we have a set of objects
>      a b c d  e f g h  i j k l
> these shall be put in sets of equal size (3 sets of 4 for example) how
> can i enumerate(generate) the combinations of sets?
> that is
>      abcd efgi hjkl
>      abcd efgj hikl
> and so on.
>
>      'abcd' and 'dbca' are equal
> and
>      'abdc' 'efkl'
> is the same as
>      'klef' 'dbca'
>
> how many enumerations are there? to see if the generator is correct..
>
> i found a lot of examples giving answers to _similar_ questions, but
> none is useful enough for me. unfortunately i cant put together the
> pieces which are obviously in front of me.
>
> any literature links are welcome.

Choose the first set in one of
(12*11*10*9)/(4*3*2*1) ways.

Then choose the second, in one
of (8*7*6*5)/(4*3*2*1) ways.

The third set is what's left.

Multiply together those first
two numbers, then divide by 6
to allow for the fact that the
same three sets would appear in
each of six different orders.
--
From: dvholten on 5 Oct 2009 09:35
thanks so far.
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 -
i have BigInteger - but to enumerate that will take a few moments..

greetings
dvh

bert schrieb:
> On 5 Oct, 14:18, dvholten <i...(a)dvholten.de> wrote:
>> hi folks,
>>
>> here is a combinatorics question for the experts:
>> lets assume we have a set of objects
>> a b c d e f g h i j k l
>> these shall be put in sets of equal size (3 sets of 4 for example) how
>> can i enumerate(generate) the combinations of sets?
>> that is
>> abcd efgi hjkl
>> abcd efgj hikl
>> and so on.
>>
>> 'abcd' and 'dbca' are equal
>> and
>> 'abdc' 'efkl'
>> is the same as
>> 'klef' 'dbca'
>>
>> how many enumerations are there? to see if the generator is correct..
>>
>> i found a lot of examples giving answers to _similar_ questions, but
>> none is useful enough for me. unfortunately i cant put together the
>> pieces which are obviously in front of me.
>>
>> any literature links are welcome.
>
> Choose the first set in one of
> (12*11*10*9)/(4*3*2*1) ways.
>
> Then choose the second, in one
> of (8*7*6*5)/(4*3*2*1) ways.
>
> The third set is what's left.
>
> Multiply together those first
> two numbers, then divide by 6
> to allow for the fact that the
> same three sets would appear in
> each of six different orders.
> --
From: The Qurqirish Dragon on 5 Oct 2009 09:41
On Oct 5, 9:18 am, dvholten <i...(a)dvholten.de> wrote:
> hi folks,
>
> here is a combinatorics question for the experts:
> lets assume we have a set of objects
>      a b c d  e f g h  i j k l
> these shall be put in sets of equal size (3 sets of 4 for example) how
> can i enumerate(generate) the combinations of sets?
> that is
>      abcd efgi hjkl
>      abcd efgj hikl
> and so on.
>
>      'abcd' and 'dbca' are equal
> and
>      'abdc' 'efkl'
> is the same as
>      'klef' 'dbca'
>
> how many enumerations are there? to see if the generator is correct..
>
> i found a lot of examples giving answers to _similar_ questions, but
> none is useful enough for me. unfortunately i cant put together the
> pieces which are obviously in front of me.
>
> any literature links are welcome.
>
> many thanks
> dvholten

The easiest way to avoid duplicates, if you are enumerating the
choices is this way:
1) to avoid abcd <=> bcad, be certain to always list entries in each
group in alphabetical order.

2) to avoid abcd,efgh <=> efgh, abcd, be certain to always list the
groups in alphabetical order.

note that this means the first element of the first group will always
be "a"

As a pseudocode program to list, try this:
group 1, entry 1 = a
let group 1, entry 2 = b, c, ... , j
let group 1, entry 3 = successor(group 1, entry 2),...,k
let group 1, entry 4 = successor(group 1, entry 3),...,l
group 2, entry 1 = least of unchosen
let group 2, entry 2 = successor(group 2, entry 1),...,j ; skip
those used in group 1
let group 2, entry 3 = successor(group 2, entry 2),...,k ; skip
those used in group 1
let group 2, entry 4 = successor(group 2, entry 3),...,l ; skip
those used in group 1
group 3 = remaining 4 letters, ordered
output groups and entries in order.

each indent is a nested loop.
The way of looping forces condition (1) above
The assignments for entry 1 of groups 1 and 2 force condition (2)
above.

If you want other (fixed) size groups, then you should see how to
rework the code. Note that you do not even need to have equal-sized
groups for this method. In that case I would choose to have the last
group be the one with the largest number of elements to reduce
completion time, and note that you could not assume group 1, entry 1
is "a" in that case either.
From: Jussi Piitulainen on 5 Oct 2009 09:57
dvholten writes:

> hi folks,
>
> here is a combinatorics question for the experts:
> lets assume we have a set of objects
> a b c d e f g h i j k l
> these shall be put in sets of equal size (3 sets of 4 for example) how
> can i enumerate(generate) the combinations of sets?
> that is
> abcd efgi hjkl
> abcd efgj hikl
> and so on.
>
> 'abcd' and 'dbca' are equal
> and
> 'abdc' 'efkl'
> is the same as
> 'klef' 'dbca'

To generate, put the least object in the first group and then add any
three of the remaining objects, C(12 - 1, 3) ways to do this. For each
of these ways, put the least of the remaining 8 objects in the second
group, and add any 3 of the remaining, C(8 - 1, 3) ways to do this.
Put the least of the remaining 4 elements in the last group and add
any 3 of the remaining 3, only C(4 - 1, 3) ways = 1 way.

> how many enumerations are there? to see if the generator is
> correct..

This agrees with bert's way to count the results:

(11*10*9/(3*2*1)) * (7*6*5/(3*2*1))

= 3 * 5^2 * 7 * 11

= (12*11*10*9/(4*3*2*1) * (8*7*6*5/(4*3*2*1)) / (3*2*1)

Unless I made a clerical error. Often happens.

This should be straightforward to turn into code, with some tedium
involved. There may be other more efficient algorithms: my implied
recursion above seems to lead to repetitive work when there are many
groups, which can be bad.
 |  Next  |  Last
Pages: 1 2 3
Prev: The Muse of Musatov 'Mu'
Next: Musatov is using others' intelelctual property?. Come clean.