Combination and maximum sum problem... [Math]

Prev: Lindelof summation?
Next: The puzzle of the honest pirates

From: choi2k on 12 Nov 2009 20:20

Suppose I have 7 symbols, A-B-C-D-E-F-G
for each combination of TWO symbols, I assign a value to it
(e.g. A-B = 10, A-C = 13, B-C = 16)
If I would like to find the combination of THREE symbols which has
maximum sum of it's sub-combinatioin's value (e.g. A-B-C = A-B + A-C
+
B-C is larger than other THREE symbols combination ), is there a best
way to do it?

Thank you in advance :)

From: Mensanator on 13 Nov 2009 00:56

On Nov 12, 7:20 pm, choi2k <rex.0...(a)gmail.com> wrote:
> Suppose I have 7 symbols, A-B-C-D-E-F-G
> for each combination of TWO symbols, I assign a value to it
> (e.g. A-B = 10, A-C = 13, B-C = 16)
> If I would like to find the combination of THREE symbols which has
> maximum sum of it's sub-combinatioin's value (e.g. A-B-C = A-B + A-C
> +
> B-C is larger than other THREE symbols combination ), is there a best
> way to do it?

Sure.

# Python 3.1

import itertools as it
import random

# create combinations of 7 items taken 2 at a time
bytwo = [i for i in it.combinations('ABCDEFG',2)]

# create combinations of 7 items taken 3 at a time
bytwe = [i for i in it.combinations('ABCDEFG',3)]

bytwovalues = {}

# assign random values to the pairs
for i in bytwo:
bytwovalues[i] = random.randint(10,20)
print(i,bytwovalues[i])
print()

# for every set of three, sum all pairs of 3 items taken 2 at a time
for i in bytwe:
the_twe_pairs = [bytwovalues[j] for j in it.combinations(i,2)]
print(i,sum(the_twe_pairs))

## ('A', 'B') 20
## ('A', 'C') 11
## ('A', 'D') 10
## ('A', 'E') 11
## ('A', 'F') 19
## ('A', 'G') 16
## ('B', 'C') 11
## ('B', 'D') 12
## ('B', 'E') 11
## ('B', 'F') 10
## ('B', 'G') 13
## ('C', 'D') 11
## ('C', 'E') 20
## ('C', 'F') 11
## ('C', 'G') 12
## ('D', 'E') 16
## ('D', 'F') 15
## ('D', 'G') 11
## ('E', 'F') 13
## ('E', 'G') 14
## ('F', 'G') 14
##
## ('A', 'B', 'C') 42
## ('A', 'B', 'D') 42
## ('A', 'B', 'E') 42
## ('A', 'B', 'F') 49
## ('A', 'B', 'G') 49
## ('A', 'C', 'D') 32
## ('A', 'C', 'E') 42
## ('A', 'C', 'F') 41
## ('A', 'C', 'G') 39
## ('A', 'D', 'E') 37
## ('A', 'D', 'F') 44
## ('A', 'D', 'G') 37
## ('A', 'E', 'F') 43
## ('A', 'E', 'G') 41
## ('A', 'F', 'G') 49
## ('B', 'C', 'D') 34
## ('B', 'C', 'E') 42
## ('B', 'C', 'F') 32
## ('B', 'C', 'G') 36
## ('B', 'D', 'E') 39
## ('B', 'D', 'F') 37
## ('B', 'D', 'G') 36
## ('B', 'E', 'F') 34
## ('B', 'E', 'G') 38
## ('B', 'F', 'G') 37
## ('C', 'D', 'E') 47
## ('C', 'D', 'F') 37
## ('C', 'D', 'G') 34
## ('C', 'E', 'F') 44
## ('C', 'E', 'G') 46
## ('C', 'F', 'G') 37
## ('D', 'E', 'F') 44
## ('D', 'E', 'G') 41
## ('D', 'F', 'G') 40
## ('E', 'F', 'G') 41

>
> Thank you in advance :)

From: choi2k on 13 Nov 2009 03:30

On 11æ13æ¥, ä¸å1æ56å, Mensanator <mensana...(a)aol.com> wrote:
> On Nov 12, 7:20Â pm, choi2k <rex.0...(a)gmail.com> wrote:
>
> > Suppose I have 7 symbols, A-B-C-D-E-F-G
> > for each combination of TWO symbols, I assign a value to it
> > (e.g. A-B = 10, A-C = 13, B-C = 16)
> > If I would like to find the combination of THREE symbols which has
> > maximum sum of it's sub-combinatioin's value (e.g. A-B-C = A-B + A-C
> > +
> > B-C is larger than other THREE symbols combination ), is there a best
> > way to do it?
>
> Sure.
>
> # Python 3.1
>
> import itertools as it
> import random
>
> # create combinations of 7 items taken 2 at a time
> bytwo = [i for i in it.combinations('ABCDEFG',2)]
>
> # create combinations of 7 items taken 3 at a time
> bytwe = [i for i in it.combinations('ABCDEFG',3)]
>
> bytwovalues = {}
>
> # assign random values to the pairs
> for i in bytwo:
> Â bytwovalues[i] = random.randint(10,20)
> Â print(i,bytwovalues[i])
> print()
>
> # for every set of three, sum all pairs of 3 items taken 2 at a time
> for i in bytwe:
> Â the_twe_pairs = [bytwovalues[j] for j in it.combinations(i,2)]
> Â print(i,sum(the_twe_pairs))
>
> ## Â ('A', 'B') 20
> ## Â ('A', 'C') 11
> ## Â ('A', 'D') 10
> ## Â ('A', 'E') 11
> ## Â ('A', 'F') 19
> ## Â ('A', 'G') 16
> ## Â ('B', 'C') 11
> ## Â ('B', 'D') 12
> ## Â ('B', 'E') 11
> ## Â ('B', 'F') 10
> ## Â ('B', 'G') 13
> ## Â ('C', 'D') 11
> ## Â ('C', 'E') 20
> ## Â ('C', 'F') 11
> ## Â ('C', 'G') 12
> ## Â ('D', 'E') 16
> ## Â ('D', 'F') 15
> ## Â ('D', 'G') 11
> ## Â ('E', 'F') 13
> ## Â ('E', 'G') 14
> ## Â ('F', 'G') 14
> ##
> ## Â ('A', 'B', 'C') 42
> ## Â ('A', 'B', 'D') 42
> ## Â ('A', 'B', 'E') 42
> ## Â ('A', 'B', 'F') 49
> ## Â ('A', 'B', 'G') 49
> ## Â ('A', 'C', 'D') 32
> ## Â ('A', 'C', 'E') 42
> ## Â ('A', 'C', 'F') 41
> ## Â ('A', 'C', 'G') 39
> ## Â ('A', 'D', 'E') 37
> ## Â ('A', 'D', 'F') 44
> ## Â ('A', 'D', 'G') 37
> ## Â ('A', 'E', 'F') 43
> ## Â ('A', 'E', 'G') 41
> ## Â ('A', 'F', 'G') 49
> ## Â ('B', 'C', 'D') 34
> ## Â ('B', 'C', 'E') 42
> ## Â ('B', 'C', 'F') 32
> ## Â ('B', 'C', 'G') 36
> ## Â ('B', 'D', 'E') 39
> ## Â ('B', 'D', 'F') 37
> ## Â ('B', 'D', 'G') 36
> ## Â ('B', 'E', 'F') 34
> ## Â ('B', 'E', 'G') 38
> ## Â ('B', 'F', 'G') 37
> ## Â ('C', 'D', 'E') 47
> ## Â ('C', 'D', 'F') 37
> ## Â ('C', 'D', 'G') 34
> ## Â ('C', 'E', 'F') 44
> ## Â ('C', 'E', 'G') 46
> ## Â ('C', 'F', 'G') 37
> ## Â ('D', 'E', 'F') 44
> ## Â ('D', 'E', 'G') 41
> ## Â ('D', 'F', 'G') 40
> ## Â ('E', 'F', 'G') 41
>
>
>
>
>
> > Thank you in advance :)

Thank you very much!
btw, is it possible to find the maximum without calculate all possible
combination?

From: Mensanator on 13 Nov 2009 14:26

On Nov 13, 2:30Â am, choi2k <rex.0...(a)gmail.com> wrote:
> On 11æ13æ¥, ä¸å1æ56å, Mensanator <mensana...(a)aol.com> wrote:
>
>
>
>
>
> > On Nov 12, 7:20Â pm, choi2k <rex.0...(a)gmail.com> wrote:
>
> > > Suppose I have 7 symbols, A-B-C-D-E-F-G
> > > for each combination of TWO symbols, I assign a value to it
> > > (e.g. A-B = 10, A-C = 13, B-C = 16)
> > > If I would like to find the combination of THREE symbols which has
> > > maximum sum of it's sub-combinatioin's value (e.g. A-B-C = A-B + A-C
> > > +
> > > B-C is larger than other THREE symbols combination ), is there a best
> > > way to do it?
>
> > Sure.
>
> > # Python 3.1
>
> > import itertools as it
> > import random
>
> > # create combinations of 7 items taken 2 at a time
> > bytwo = [i for i in it.combinations('ABCDEFG',2)]
>
> > # create combinations of 7 items taken 3 at a time
> > bytwe = [i for i in it.combinations('ABCDEFG',3)]
>
> > bytwovalues = {}
>
> > # assign random values to the pairs
> > for i in bytwo:
> > Â bytwovalues[i] = random.randint(10,20)
> > Â print(i,bytwovalues[i])
> > print()
>
> > # for every set of three, sum all pairs of 3 items taken 2 at a time
> > for i in bytwe:
> > Â the_twe_pairs = [bytwovalues[j] for j in it.combinations(i,2)]
> > Â print(i,sum(the_twe_pairs))
>
> > ## Â ('A', 'B') 20
> > ## Â ('A', 'C') 11
> > ## Â ('A', 'D') 10
> > ## Â ('A', 'E') 11
> > ## Â ('A', 'F') 19
> > ## Â ('A', 'G') 16
> > ## Â ('B', 'C') 11
> > ## Â ('B', 'D') 12
> > ## Â ('B', 'E') 11
> > ## Â ('B', 'F') 10
> > ## Â ('B', 'G') 13
> > ## Â ('C', 'D') 11
> > ## Â ('C', 'E') 20
> > ## Â ('C', 'F') 11
> > ## Â ('C', 'G') 12
> > ## Â ('D', 'E') 16
> > ## Â ('D', 'F') 15
> > ## Â ('D', 'G') 11
> > ## Â ('E', 'F') 13
> > ## Â ('E', 'G') 14
> > ## Â ('F', 'G') 14
> > ##
> > ## Â ('A', 'B', 'C') 42
> > ## Â ('A', 'B', 'D') 42
> > ## Â ('A', 'B', 'E') 42
> > ## Â ('A', 'B', 'F') 49
> > ## Â ('A', 'B', 'G') 49
> > ## Â ('A', 'C', 'D') 32
> > ## Â ('A', 'C', 'E') 42
> > ## Â ('A', 'C', 'F') 41
> > ## Â ('A', 'C', 'G') 39
> > ## Â ('A', 'D', 'E') 37
> > ## Â ('A', 'D', 'F') 44
> > ## Â ('A', 'D', 'G') 37
> > ## Â ('A', 'E', 'F') 43
> > ## Â ('A', 'E', 'G') 41
> > ## Â ('A', 'F', 'G') 49
> > ## Â ('B', 'C', 'D') 34
> > ## Â ('B', 'C', 'E') 42
> > ## Â ('B', 'C', 'F') 32
> > ## Â ('B', 'C', 'G') 36
> > ## Â ('B', 'D', 'E') 39
> > ## Â ('B', 'D', 'F') 37
> > ## Â ('B', 'D', 'G') 36
> > ## Â ('B', 'E', 'F') 34
> > ## Â ('B', 'E', 'G') 38
> > ## Â ('B', 'F', 'G') 37
> > ## Â ('C', 'D', 'E') 47
> > ## Â ('C', 'D', 'F') 37
> > ## Â ('C', 'D', 'G') 34
> > ## Â ('C', 'E', 'F') 44
> > ## Â ('C', 'E', 'G') 46
> > ## Â ('C', 'F', 'G') 37
> > ## Â ('D', 'E', 'F') 44
> > ## Â ('D', 'E', 'G') 41
> > ## Â ('D', 'F', 'G') 40
> > ## Â ('E', 'F', 'G') 41
>
> > > Thank you in advance :)
>
> Thank you very much!
> btw, is it possible to find the maximum without calculate all possible
> combination?

In some cases. For instance, if in the above example, we
change the AB pair's value to 1000 while leaving the rest
unchanged, then the triplet that's the max must contain AB.
That would be using a "greedy" algorithm to restrict the
choices you have to test.

Using the original values, there are two with a value of 20:
AB and CE. But these haven't got a letter in common, so no
triplet can contain both. As a consequence, none of the max
sum (49) contain CE. Two of them have AB but the third does
not. If we had tried to greedily look at the four letters
ABCE, it would not have worked.

Another example is The Bridge Crossing Problem.
http://mensanator.com/mensanator666/fun/playing.htm/#u2

Here, we have TWO sums, the crossing times and the return
times. If you greedily tried to minimize the return times
(by always having Bono carry the flashlight), that has an
impact on the crossing sum, which won't be minimum.

Sometimes optimization works, sometimes it doesn't.

Iterating through every possibility will always work (if
it's tractable to do so).

I often work with a list of numbers such as [1,2,1,3,1,2,1,4].
These sum to 15 and there are 8 numbers. I have to find how
many ways 15 objects can be placed in 8 containers such that
every container contains at least 1 object. For each possible
set of numbers, I have to create a rational number (such as)

3^0*2^11+3^1*2^10+3^2*2^8+3^3*2^7+3^4*2^4+3^5*2^3+3^6*2^n1+3^7*2^n
------------------------------------------------------------------
2^15 - 3^8

and check to see if it's an integer. Not easy to optimize, so I
pretty much have to step through every possible partition. And
most of the time, there isn't an answer at all.

From: Mensanator on 13 Nov 2009 15:22

On Nov 13, 1:26Â pm, Mensanator <mensana...(a)aol.com> wrote:
> On Nov 13, 2:30Â am, choi2k <rex.0...(a)gmail.com> wrote:
>
>
>
>
>
> > On 11æ13æ¥, ä¸å1æ56å, Mensanator <mensana...(a)aol.com> wrote:
>
> > > On Nov 12, 7:20Â pm, choi2k <rex.0...(a)gmail.com> wrote:
>
> > > > Suppose I have 7 symbols, A-B-C-D-E-F-G
> > > > for each combination of TWO symbols, I assign a value to it
> > > > (e.g. A-B = 10, A-C = 13, B-C = 16)
> > > > If I would like to find the combination of THREE symbols which has
> > > > maximum sum of it's sub-combinatioin's value (e.g. A-B-C = A-B + A-C
> > > > +
> > > > B-C is larger than other THREE symbols combination ), is there a best
> > > > way to do it?
>
> > > Sure.
>
> > > # Python 3.1
>
> > > import itertools as it
> > > import random
>
> > > # create combinations of 7 items taken 2 at a time
> > > bytwo = [i for i in it.combinations('ABCDEFG',2)]
>
> > > # create combinations of 7 items taken 3 at a time
> > > bytwe = [i for i in it.combinations('ABCDEFG',3)]
>
> > > bytwovalues = {}
>
> > > # assign random values to the pairs
> > > for i in bytwo:
> > > Â bytwovalues[i] = random.randint(10,20)
> > > Â print(i,bytwovalues[i])
> > > print()
>
> > > # for every set of three, sum all pairs of 3 items taken 2 at a time
> > > for i in bytwe:
> > > Â the_twe_pairs = [bytwovalues[j] for j in it.combinations(i,2)]
> > > Â print(i,sum(the_twe_pairs))
>
> > > ## Â ('A', 'B') 20
> > > ## Â ('A', 'C') 11
> > > ## Â ('A', 'D') 10
> > > ## Â ('A', 'E') 11
> > > ## Â ('A', 'F') 19
> > > ## Â ('A', 'G') 16
> > > ## Â ('B', 'C') 11
> > > ## Â ('B', 'D') 12
> > > ## Â ('B', 'E') 11
> > > ## Â ('B', 'F') 10
> > > ## Â ('B', 'G') 13
> > > ## Â ('C', 'D') 11
> > > ## Â ('C', 'E') 20
> > > ## Â ('C', 'F') 11
> > > ## Â ('C', 'G') 12
> > > ## Â ('D', 'E') 16
> > > ## Â ('D', 'F') 15
> > > ## Â ('D', 'G') 11
> > > ## Â ('E', 'F') 13
> > > ## Â ('E', 'G') 14
> > > ## Â ('F', 'G') 14
> > > ##
> > > ## Â ('A', 'B', 'C') 42
> > > ## Â ('A', 'B', 'D') 42
> > > ## Â ('A', 'B', 'E') 42
> > > ## Â ('A', 'B', 'F') 49
> > > ## Â ('A', 'B', 'G') 49
> > > ## Â ('A', 'C', 'D') 32
> > > ## Â ('A', 'C', 'E') 42
> > > ## Â ('A', 'C', 'F') 41
> > > ## Â ('A', 'C', 'G') 39
> > > ## Â ('A', 'D', 'E') 37
> > > ## Â ('A', 'D', 'F') 44
> > > ## Â ('A', 'D', 'G') 37
> > > ## Â ('A', 'E', 'F') 43
> > > ## Â ('A', 'E', 'G') 41
> > > ## Â ('A', 'F', 'G') 49
> > > ## Â ('B', 'C', 'D') 34
> > > ## Â ('B', 'C', 'E') 42
> > > ## Â ('B', 'C', 'F') 32
> > > ## Â ('B', 'C', 'G') 36
> > > ## Â ('B', 'D', 'E') 39
> > > ## Â ('B', 'D', 'F') 37
> > > ## Â ('B', 'D', 'G') 36
> > > ## Â ('B', 'E', 'F') 34
> > > ## Â ('B', 'E', 'G') 38
> > > ## Â ('B', 'F', 'G') 37
> > > ## Â ('C', 'D', 'E') 47
> > > ## Â ('C', 'D', 'F') 37
> > > ## Â ('C', 'D', 'G') 34
> > > ## Â ('C', 'E', 'F') 44
> > > ## Â ('C', 'E', 'G') 46
> > > ## Â ('C', 'F', 'G') 37
> > > ## Â ('D', 'E', 'F') 44
> > > ## Â ('D', 'E', 'G') 41
> > > ## Â ('D', 'F', 'G') 40
> > > ## Â ('E', 'F', 'G') 41
>
> > > > Thank you in advance :)
>
> > Thank you very much!
> > btw, is it possible to find the maximum without calculate all possible
> > combination?
>
> In some cases. For instance, if in the above example, we
> change the AB pair's value to 1000 while leaving the rest
> unchanged, then the triplet that's the max must contain AB.
> That would be using a "greedy" algorithm to restrict the
> choices you have to test.
>
> Using the original values, there are two with a value of 20:
> AB and CE. But these haven't got a letter in common, so no
> triplet can contain both. As a consequence, none of the max
> sum (49) contain CE. Two of them have AB but the third does
> not. If we had tried to greedily look at the four letters
> ABCE, it would not have worked.
>
> Another example is The Bridge Crossing Problem.http://mensanator.com/mensanator666/fun/playing.htm/#u2

Oops, spelled the link wrong, s/b
http://mensanator.com/mensanator666/fun/playing.htm#u2

>
> Here, we have TWO sums, the crossing times and the return
> times. If you greedily tried to minimize the return times
> (by always having Bono carry the flashlight), that has an
> impact on the crossing sum, which won't be minimum.
>
> Sometimes optimization works, sometimes it doesn't.
>
> Iterating through every possibility will always work (if
> it's tractable to do so).
>
> I often work with a list of numbers such as [1,2,1,3,1,2,1,4].
> These sum to 15 and there are 8 numbers. I have to find how
> many ways 15 objects can be placed in 8 containers such that
> every container contains at least 1 object. For each possible
> set of numbers, I have to create a rational number (such as)
>
> 3^0*2^11+3^1*2^10+3^2*2^8+3^3*2^7+3^4*2^4+3^5*2^3+3^6*2^n1+3^7*2^n
> ------------------------------------------------------------------
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â 2^15 - 3^8
>
> and check to see if it's an integer. Not easy to optimize, so I
> pretty much have to step through every possible partition. And
> most of the time, there isn't an answer at all.- Hide quoted text -
>
> - Show quoted text -

| Next | Last
Pages: 1 2
Prev: Lindelof summation?
Next: The puzzle of the honest pirates