Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: x objects in y containers where all objects are used

by ikegami (Patriarch)
on Nov 06, 2009 at 19:29 UTC ( [id://805560]=note: print w/replies, xml ) Need Help??


in reply to x objects in y containers where all objects are used

You need to choose y-1 divisions in your set of objects.

For your example, that would be:

for my $p0 (1 .. 5-1) { for my $p1 ($p0+1 .. 5-1) { print( substr('12345', 0, $p0), "|", substr('12345', $p0, $p1-$p0), "|", substr('12345', $p1, 5-$p1), "\n", ); }}

The general case requires y-1 nested loops. When you have a variable number of nested loop, Algorithm::Loops's NestedLoops is great:

use Algorithm::Loops qw( NestedLoops ); my $num_objects = 5; my $num_containers = 3; my $str = join('', 1..$num_objects); NestedLoops( [ [ 1 .. $num_objects-1 ], (sub { [ $_[-1]+1 .. $num_objects-1 ] }) x ($num_containers-2) ], sub { my $str = $str; substr($str, $_, 0, '|') for reverse @_; print("$str\n"); }, );
1|2|345 1|23|45 1|234|5 12|3|45 12|34|5 123|4|5

Replies are listed 'Best First'.
Re^2: x objects in y containers where all objects are used
by Anonymous Monk on Nov 07, 2009 at 23:03 UTC
    This could be classical recurrence problem. We need some formula, and then a module to convert that into values or count of possibilities.
    T(N,2) = N-1; T(N,K) = SIGMA(T(N-X,K-1)) for X = 1 to N-K Example: T(5,3) = T(4,2)+ T(3,2) + T(2,2) = 3 + 2 + 1 = 6
      The OP specifically said he didn't want the count. The count is easy to get without even using recursion. It's a simple Combination:
      C($num_objects-1, $num_containers-1) = C(4, 2) = 4! / (4-2)! / 2! = (4*3) / (2*1) = 6

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (5)
As of 2024-03-29 15:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found