Prev: Lindelof summation?
Next: The puzzle of the honest pirates
From: Rob Pratt on 14 Nov 2009 13:31
"choi2k" <rex.0510(a)gmail.com> wrote in message
news:85564ca1-b78d-4e69-981c-e6c01c608e36(a)h40g2000prf.googlegroups.com...
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?

---

Yes, there are several alternatives to brute-force enumeration.

Search phrase: "maximum edge-weighted clique problem"

Rob Pratt


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