Neat problem. I love things like this.

Okay, so my thought was the utilize the following logic: walk forward through the list of managers, assigning each one in order the letter group with the highest population. After walking the list once, the first manager has the most people while the last one has the fewest. So, walk the list agian, but in reverse, assign the highest population group as you go. If there is more left after this walk, reverse direction and do it again.

It seems to work for my test groups; though I know it won't work in all situations :) Given the input data above, I get: 

1: A 5
2: DB 6
3: EC 6

[download]
Doubling the size of the list (F-J with A-E's numbers) gets me: 
1: AJC 11
2: FEH 11
3: DIBG 12

[download]
Which also seems to work.

Now below is the code. I want to apologize for the while loop: I couldn't (quickly) think of a clever way of running a list backwards and forwards multiple times until a condition is met. Suggests are welcome! 

#!/usr/bin/perl -w

use strict;

##

my %letters=(
             A => 5,
             B => 1,
             C => 2,
             D => 5,
             E => 4,
            );

my $reps=3;
my %reps;

## hackarific!
my $pos=1;
my $dir=1;

## keep going until we run out
while (keys %letters) {
  ## get highest
  my($h,undef)=sort { $letters{$b} <=> $letters{$a} } keys %letters;

  ## note the grouping
  $reps{$pos}{letter}.=$h;
  $reps{$pos}{size}+=$letters{$h};

  delete $letters{$h};

  ## sorry folks, couldn't think of a better way fast enough :)
  if ($dir==1) {
    $pos++;
    if ($pos>$reps) {
      $pos--;
      $dir=0;
    }
  }
  else {
    $pos--;
    if ($pos==0) {
      $pos++;
      $dir=1;
    }
  }
}

for my $r (keys %reps) {
  print "$r: $reps{$r}{letter} $reps{$r}{size}\n";
}

[download]
For fun, replace the %letters declaration at the top with this 
my %letters; 
          
for my $x ('A'..'Z') { 
  $letters{$x}=int(rand(10)+1); 
}

[download]
UPDATE!!

I thought of a better way. Instead of walking the list backwards and fowards (which even distributes the NUMBER of letters each rep has), instead pick the rep with the LOWEST size of it's letter groups. Programmatically, this requires an initialization of the %reps hash so that we can do a simple sort to get the lowest. 

#!/usr/bin/perl -w 
 
use strict; 
 
## 
 
my %letters; 
 
for my $x ('A'..'Z') { 
  $letters{$x}=int(rand(10)+1); 
} 
   
 
my $reps=5; 
my %reps; 
 
for my $x (1..$reps) { 
  $reps{$x}{size}=0; 
} 
 
my $pos=1; 
 
## keep going until we run out 
while (keys %letters) { 
  ## get highest 
  my($h,undef)=sort { $letters{$b} <=> $letters{$a} } keys %letters; 
 
  ## note the grouping 
  $reps{$pos}{letter}.="$h($letters{$h}) "; 
  $reps{$pos}{size}+=$letters{$h}; 
 
  delete $letters{$h}; 
 
  ## find the lowest position 
  ($pos,undef)=sort { $reps{$a}{size} <=> $reps{$b}{size} } keys %reps
+; 
} 
 
for my $r (keys %reps) { 
  print "$r: $reps{$r}{letter} $reps{$r}{size}\n"; 
}

[download]
which yields the following as output: 
1: M(10) U(10) T(6) L(3) B(3)  32
2: R(10) O(9) J(7) D(3) K(3)  32
3: V(10) Z(9) S(6) F(6) P(2)  33
4: W(10) E(8) H(7) G(6) C(1)  32
5: N(10) X(8) I(7) Q(4) A(2) Y(1)  32

[download]

In reply to Re: Constraint Satisfaction Problem by mr.nick
in thread Constraint Satisfaction Problem by princepawn

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.