Then I must have made a mistake in my explanation because the solution should be closer to Huffman coding as roboticus astutely concluded above. Since I can't explain why what I am trying to accomplish is slightly different, I guess I am stuck.

Well, you mentioned proportional which I interpreted to mean that higher frequencies should take longer to reach than lower frequencies, which barring the possibility of equal frequencies, a lop-sided tree achieves.

(Albeit you said inversely proportional which would mean reversing the order of the sort from what I posted.)

The only other sense I can get from the information provided -- brought on by the mention of Huffman -- is that you are perhaps looking to minimise the depth of the tree. This does that by building a heap and then converting it to a tree rather clumbsily. Though that could be fixed if the idea is right:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use List::Util qw[ reduce ];
use enum qw[ NAME FREQ LEFT RIGHT ];

our $N //= 1;

my$n = 0;
my @heap = map{
    $_->[LEFT] = ++$n;
    $_->[RIGHT] = ++$n;
    $_;
} sort {
    $a->[FREQ] <=> $b->[FREQ]
} map[
    $_ , int( rand 1000 )
], 'A'x$N .. 'Z'x$N;;

my @tree = map {
$_->[LEFT] = $heap[ $_->[LEFT] ], $_->[RIGHT] = $heap[ $_->[RIGHT] ]
} @heap;

pp \@tree;
[download]

Output:

C:\test>1031775.pl
do {
  my $a = [
    [
      "Y",
      1,
      [
        "G",
        4,
        [
          "D",
          166,
          ["X", 245, ["I", 516, undef, undef], ["O", 563, undef, undef
+]],
          ["K", 315, ["M", 628, undef, undef], ["R", 710, undef, undef
+]],
        ],
        [
          "A",
          218,
          ["P", 324, ["T", 731, undef, undef], ["Q", 732, undef, undef
+]],
          ["J", 374, ["V", 735, undef, undef], ["C", 835, undef, undef
+]],
        ],
      ],
      [
        "E",
        33,
        [
          "U",
          220,
          ["L", 393, ["S", 845, undef, undef], ["F", 930, undef, undef
+]],
          ["W", 471, ["Z", 944, undef, undef], undef],
        ],
        ["H", 228, ["B", 507, undef, undef], ["N", 515, undef, undef]]
+,
      ],
    ],
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
    'fix',
  ];
  $a->[1] = $a->[0][2];
  $a->[2] = $a->[0][3];
  $a->[3] = $a->[0][2][2];
  $a->[4] = $a->[0][2][3];
  $a->[5] = $a->[0][3][2];
  $a->[6] = $a->[0][3][3];
  $a->[7] = $a->[0][2][2][2];
  $a->[8] = $a->[0][2][2][3];
  $a->[9] = $a->[0][2][3][2];
  $a->[10] = $a->[0][2][3][3];
  $a->[11] = $a->[0][3][2][2];
  $a->[12] = $a->[0][3][2][3];
  $a->[13] = $a->[0][3][3][2];
  $a->[14] = $a->[0][3][3][3];
  $a->[15] = $a->[0][2][2][2][2];
  $a->[16] = $a->[0][2][2][2][3];
  $a->[17] = $a->[0][2][2][3][2];
  $a->[18] = $a->[0][2][2][3][3];
  $a->[19] = $a->[0][2][3][2][2];
  $a->[20] = $a->[0][2][3][2][3];
  $a->[21] = $a->[0][2][3][3][2];
  $a->[22] = $a->[0][2][3][3][3];
  $a->[23] = $a->[0][3][2][2][2];
  $a->[24] = $a->[0][3][2][2][3];
  $a->[25] = $a->[0][3][2][3][2];
  $a;
}
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.
/div

BrowserUk,
By inversely proportional, I meant that the number of questions asked to identify an animal (Q) multiplied by how many times the animal is chosen (C) should be constant. If a goat appears a hundred times more often than a unicorn then it should take a hundred times more questions to identify the unicorn than the goat.

I apologize for not seeing it before hand, but I am pretty sure the optimal strategy for my problem is in fact Huffman Coding. To get a better idea of the fuzzy problem I am dealing with in my head, see Re^4: Challenge: Optimal Animals/Pangolins Strategy

Cheers - L~R

Aren't Huffman trees generally expected to be lop-sided?

jakeease,
I think that depends heavily on the frequency distribution.

Cheers - L~R