Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Puzzle: need a more general algorithm

by dws (Chancellor)
on Jul 10, 2002 at 06:48 UTC ( #180694=note: print w/ replies, xml ) Need Help??


in reply to Puzzle: need a more general algorithm

I've been chewing on this problem for a day now. This is clearly problem with two logical parts. Part 1 is to generate all legal mappings of N columns of data into M buckets, given the constraints that no bucket can be empty, and that the columns need to stay ordered. The second part is apply these mappings to the input data, and select a mapping that yields a "best fit."

I focused on the first part, looking for a quicker, simpler solution. I think I have one. Here it is. Given a number of columns and a number of buckets, the code below calculates all legal mappings of columns to buckets, and returns these in a hash, where the key is a printable string, and the value is an anonymous array.

{ # map columns to buckets. key is string, value is anonymous array. my %c2bMap; sub c2bMappings { my($buckets, $columns) = @_; die "bogus args" unless $buckets > 1 && $columns > $buckets; %c2bMap = (); _genFrom(0, (0) x ($columns - $buckets), 1 .. ($buckets - 1)); return \%c2bMap; } sub _genFrom { my @c2bMap = @_; return if exists $c2bMap{"@c2bMap"}; print "@c2bMap\n"; #DEBUG $c2bMap{"@c2bMap"} = \@c2bMap; foreach my $i ( 2 .. $#c2bMap ) { my $n = $c2bMap[$i] - 1; if ( $c2bMap[$i - 2] == $n && $c2bMap[$i - 1] == $n ) { local $c2bMap[$i-1] = $c2bMap[$i]; _genFrom(@c2bMap); } } } } c2bMappings(4,6); __END__ 0 0 0 1 2 3 0 0 1 1 2 3 0 1 1 1 2 3 0 1 1 2 2 3 0 1 2 2 2 3 0 1 2 2 3 3 0 1 2 3 3 3 0 1 1 2 3 3 0 0 1 2 2 3 0 0 1 2 3 3
Recursion only happens with valid mappings. Note the selective localization of an element of the array that the code is about to recurse on.


Comment on Re: Puzzle: need a more general algorithm
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2015-07-03 00:35 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 (47 votes), past polls