Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Bag uniform distribution algorithms

by kcott (Abbot)
on Apr 26, 2013 at 09:02 UTC ( #1030794=note: print w/ replies, xml ) Need Help??


in reply to Bag uniform distribution algorithms

G'day Dave,

By alternatively splicing elements from either end of the distribution, I get your original 'qw( A C B A D C A B C A )'.

$ perl -Mstrict -Mwarnings -E ' my %bag = ( A => 4, B => 2, C => 3, D => 1 ); my @distribution; for my $key (sort { $bag{$b} <=> $bag{$a} } keys %bag) { my $base_offset = int(@distribution / ($bag{$key} + 1)); my $offset = $base_offset; for (1 .. $bag{$key}) { next unless $_ % 2; splice @distribution, $offset, 0, $key; if ($_ < $bag{$key}) { splice @distribution, -$offset, 0, $key; } $offset += $base_offset + 1; } } say "@distribution"; ' A C B A D C A B C A

If I round up the $base_offset value, the middle two elements are reversed but everything else remains the same. I don't see this as being more or less uniform but maybe it's more correct.

$ perl -Mstrict -Mwarnings -E ' my %bag = ( A => 4, B => 2, C => 3, D => 1 ); my @distribution; for my $key (sort { $bag{$b} <=> $bag{$a} } keys %bag) { my $base_offset = int(@distribution / ($bag{$key} + 1) + 0.5); + my $offset = $base_offset; for (1 .. $bag{$key}) { next unless $_ % 2; splice @distribution, $offset, 0, $key; if ($_ < $bag{$key}) { splice @distribution, -$offset, 0, $key; } $offset += $base_offset + 1; } } say "@distribution"; ' A C B A C D A B C A

I haven't done extensive testing on this solution. Beyond your sample input, I tried:

my %bag = ( A => 4, B => 2, C => 3, D => 1, Z => 1 );

gives: A C B A C D Z A B C A; and

my %bag = ( A => 4, B => 2, C => 3, D => 1, Y => 5, Z => 1 );

gives: Y A C Y B A C Z D Y A B Y C A Y; and

my %bag = ( A => 4, B => 2, C => 3, D => 1, X => 6, Y => 5, Z => 1 );

gives: X Y A X C Y B A X Y Z D C X A B Y C X A Y X; and

my %bag = ( A => 4, B => 2, C => 3, D => 1, W => 4, X => 6, Y => 5, Z +=> 1 );

gives: X Y A W X C Y B A W X Y Z D C X W A B Y C X W A Y X

The above 4 tests all included rounding; without rounding, the results are:

A C B A Z D C A B C A Y A C Y B A C D Z Y A B Y C A Y X Y A C X Y B A C X D Z Y X A B Y X C A Y X X Y A W C X Y B A W C X D Z Y X W A B Y X C W A Y X

-- Ken


Comment on Re: Bag uniform distribution algorithms
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1030794]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (11)
As of 2015-07-06 16:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (77 votes), past polls