«

Say I have a hash with peoples names and a quality score, like their free
throw percentage.

Mathematically what is the most accurate way to divide the list into the two
most balanced teams?

Obviously you could do something simple like alternate in descending order,
but this isnt guaranteed to produce the most accurate result.

Ideally, I would like to be able to balance based on the mean, median, or
both.

Code isnt necessary but of course appreciated - but if you have a link to
the fundementals of solving such a problem thats fine to - I want to learn
to do it for myself.

On May 11, 10:47 am, "Seth Brundle" <brundlefl...@hotmail.com> wrote:
> Say I have a hash with peoples names and a quality score, like their free
> throw percentage.
>
> Mathematically what is the most accurate way to divide the list into the two
> most balanced teams?

This question has nothing to do with Perl. It would be the same
question regardless of what language you're using to implment your
solution. You're asking a mathematics question. You're more likely
to get good answers in a group that discusses mathematics.

Paul Lalli

thanks for the spamcop spam.
heres your cookie.


"Paul Lalli" <> wrote in message
news: oups.com...
> On May 11, 10:47 am, "Seth Brundle" <brundlefl...@hotmail.com> wrote:
>> Say I have a hash with peoples names and a quality score, like their free
>> throw percentage.
>>
>> Mathematically what is the most accurate way to divide the list into the
>> two
>> most balanced teams?
>
> This question has nothing to do with Perl. It would be the same
> question regardless of what language you're using to implment your
> solution. You're asking a mathematics question. You're more likely
> to get good answers in a group that discusses mathematics.
>
> Paul Lalli
>

"Seth Brundle" <> wrote:
> Say I have a hash with peoples names and a quality score, like their free
> throw percentage.
>
> Mathematically what is the most accurate way to divide the list into the
> two most balanced teams?

Mathematically, enumerate all possible sets of teams, compute the
balancedness of each, and take the one with the most balancedness. There
are various combinatoric modules and sample-code for Perl, but which one
you want probably depends on what exactly constitutes a legal pair of
teams.1

> Obviously you could do something simple like alternate in descending
> order, but this isnt guaranteed to produce the most accurate result.

It is not guaranteed to produce the *optimal* result. Accuracy probably
doesn't enter into it.

>
> Ideally, I would like to be able to balance based on the mean, median, or
> both.

Do both teams have to be the same size? If so, then balancing on mean is
the same as balancing on sum, right? That sounds like a variant of the
well-known bin-packing or knap-sack problems. For the median, that depends
strongly on whether the teams have to be divided equally, and also on
whether the number on each team is going to be odd or even, and on how you
define median in the case of even-membered teams.

>
> Code isnt necessary but of course appreciated - but if you have a link to
> the fundementals of solving such a problem thats fine to - I want to
> learn to do it for myself.

knap-sack and bin-packing are very widely discussed fundamentals. Google
on those terms, you will find more than you care for on them.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB

> Unless you have gross outliers, you will probably do well by sorting
> the list by score, then you would take (unshift) pairs of people with
> close scores (that is, take pair of persons 1 and 2 (two worst

thanks for the reply, but that solution is the one I referred to (basically
a phys-ed style draft pick) that I dont believe to be the most accurate.

Yes, the outcome I seek is that after the sort the two teams will have the
closest average (mean) mathematically possible.

However, it would be cool if I could do it by median as well, or both, just
for comparison.

> knap-sack and bin-packing are very widely discussed fundamentals. Google
> on those terms, you will find more than you care for on them.

Excellent thanks!
I see there is actually a perl-Algorithm-Knapsack module.

Nothing better then a unique keyword to help you find what your looking
for - thanks!

Ignoramus6365 <> wrote:
> On 11 May 2007 15:16:03 GMT, <> wrote:
> > "Seth Brundle" <> wrote:
> >> Say I have a hash with peoples names and a quality score, like their
> >> free throw percentage.
> >>
> >> Mathematically what is the most accurate way to divide the list into
> >> the two most balanced teams?
> >
> > Mathematically, enumerate all possible sets of teams, compute the
> > balancedness of each, and take the one with the most balancedness.
> > There are various combinatoric modules and sample-code for Perl, but
> > which one you want probably depends on what exactly constitutes a legal
> > pair of teams.1
>
> Try enumerating all possibilities for two teams of 20 people each.
>
> That would be 2^40 possibilities.

Well, more like 2^39. But even less if the teams have to be balanced in
size as well as in <whatever> score.

> 1 trillion of them or so.

He said "mathematically", not "algorithmically". Since when are
mathematicians concerned about run time?

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB

On 11 May 2007 08:00:54 -0700, Paul Lalli <> wrote:

>solution. You're asking a mathematics question. You're more likely
>to get good answers in a group that discusses mathematics.

Along with some answers from crackpots who claim to have a simple FLT
proof, that is!


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

>> 1 trillion of them or so.
>
> He said "mathematically", not "algorithmically". Since when are
> mathematicians concerned about run time?

hehe I think you will find a lot of them are just as efficiency-obsessed any
programmer.

> ``Obviously you could do something simple like alternate in descending
> order, but this isnt guaranteed to produce the most accurate result.''
>
> My suggestion does not merely alternate in descending order, it
> randomizes the pairs. Yours guarantees that one team will be always
> better than another. Whereas mine does not.

Sorry I misunderstood - interesting option!