Ectaris has asked for the
wisdom of the Perl Monks concerning the following question:
I need to find every possible combination for putting x objects in y containers. All objects have to be used in every possibility. I have been searching the web but nothing seems to really fit.
So given 5 objects I need to come up with all combinations of these 5 objects that could fit in 3 containers. Possiblity one could be 12 34 5 while two would be 1 23 45 and so on.
Re: x objects in y containers where all objects are used by moritz (Cardinal) on Nov 06, 2009 at 14:08 UTC 
The answer has nothing to do with perl, only with math.
First you have to tell us if the containers have a maximal capacity; from your examples I'd guess so. If that's the case, the number of combinations is the factorial of the total capacity of all containers, divided by the product of the factorials of each capacity. So in your example
6!

2! * 2! * 2!
This assumes that order insider containers doesn't matter, ie that 12 34 5 is the same as 21 34 5, but that the order of containers does matter. (If it doesn't, you need to divide by the factorial of number containers).
If that's not what you want, you have to provide a few more details.
Perl 6  links to (nearly) everything that is Perl 6.
 [reply] 

 [reply] 

That formula (6! / 3(2!)) only applies if you have 6 items and put exactly two in each container. I don't think it expresses something about the maximal capacity, it's about a fixed capacity that you must put in each container.
 [reply] 

That formula (6! / 3(2!)) only applies if you have 6 items and put exactly two in each container.
You're right. That's why I asked if my assumption was correct that the containers have limited capacity. If it were, distributing 5 elements on 3 containers with a capacity of 2 each is the same as distributing 6, where the sixth is the empty/missing element.
I don't think it expresses something about the maximal capacity, it's about a fixed capacity that you must put in each container.
If you have a maximal capacity, and add virtual filling items, the problem becomes very similar to a fixed capacity  except that you have to divide by the factorial of the number of filling items, which I forgot in my previous post.
Perl 6  links to (nearly) everything that is Perl 6.
 [reply] 
Re: x objects in y containers where all objects are used by toolic (Bishop) on Nov 06, 2009 at 14:09 UTC 
 [reply] 

I'm not sure I understand the situation the OP is addressing or facing. Even after looking at the various responses and the OP's comments, I'm still not sure I'm understanding. But like toolic, I would suggest that if the OP hasn't already done so, looking into and considering CPAN modules. In particular I'd suggest looking in the List:: and Set:: modules of CPAN. I have been looking in CPAN for some module to do what I *think* is similar to what the OP is seeking except that my 'bags' had limited capacity whereas. If I understand the thread for this OP's question, the OP doesn't have that limitation. Anyway, I came upon the module Set::Bag which solved my particular problem. I have found that the List:: modules and the Set:: modules have a pretty rich set of tools to handle a wide variety of Power Set, binning, permutation and combinatorial problems. I would offer that it's worth looking at the modules in those two areas (List:: and Set:: ). Unfortunately, except for Set::Bag, I really don't have any experience with any of the rest. I just saw them as I was trying to find the solution to my particular problem and once I found Set::Bag, I had no additional need to learn more.
 [reply] 

The OP problem is easier if you think of it as assigning bins to items, and not as assigning items to bins. Each item MUST have one and only one bin. If you switch your thinking to assign on value in set Y to each of the items in X, then it becomes a much more clear problem.
Each item in X can be assigned exactly one of the values in Y. It is now the same class of a problem as counting in binary.
 [reply] 

Re: x objects in y containers where all objects are used by blokhead (Monsignor) on Nov 06, 2009 at 15:34 UTC 
The most straightforward solution I can think of is to generate all ways to assign each object with a container number. This will generate some assignments where some container does not receive any objects, so you will have to filter them out.
Using Algorithm::NestedLoops, that would look something like:
my $containers = ...
my $objects = ...
NestedLoops(
[ (sub{ [0 .. $containers1] }) x $objects ],
sub {
my @assignment = @_;
my @bins;
push @{ $bins[$assignment[$_]] }, $_ for 0 .. $objects1;
## @bins now contains the groupings
## filter out if one of the bins is empty
}
);
There is probably a more direct way to do this, so that you can cleverly iterate over just the assignments that use each bin. But I haven't discovered it yet in the short time that I've been thinking about your post.
 [reply] [d/l] 
Re: x objects in y containers where all objects are used by MidLifeXis (Monsignor) on Nov 06, 2009 at 15:45 UTC 
Update2: Rerereading the OP, I now understand the question. I did make a bad assumption. :)
Update: This node is based on the assumption that the bins have a maximum size. If that assumption is invalid, and the task is to create a set of unordered combinations, then this post is not a solution (well, the fitness function is trivial). See blokhead's comment below.
This is a bin packing algorithm, but you are looking for all solutions, not just the best solution. This is a theory problem.
See also the knapsack problem, travelling salesman problem, and other examples of this class of problem.
 [reply] 

In binpacking, the difficulty of the problem comes from the fact that the items are different sizes. In any casting of the OP problem in terms of bin packing, you would have all items the same size, which completely trivializes the problem. Also, in any binpacking problem there is generally an unlimited supply of bins of fixed capacity, unlike in the OP where there are a fixed number of bins with unlimited capacity. Any references on bin packing (let alone TSP, which seems completely unrelated apart from it also being NPcomplete, or knapsack, in which items have both a variable cost and variable weight) will be unlikely to have anything relevant for these variants (let alone the very specific problem of enumerating solutions).
 [reply] 

 [reply] 
Re: x objects in y containers where all objects are used by MidLifeXis (Monsignor) on Nov 06, 2009 at 17:06 UTC 
Assign the bucket to the number (instead of the number to the bucket), and you have a much easier to comprehend solution. As a sanity check, you will have Y^{x} results.
One approach, with 8 objects in 2 bins, would be to treat it as binary. A digit of '0' in position X would put item X into bucket 0. A digit of '1' in position X would put item X into bucket 1. If you iterate over all of the values for that binary number, you have just iterated over all of the solutions  in this case 256.
00000000 => (87654321), ()
00000001 => (8765432), (1)
00000010 => (8765431), (2)
00000011 => (876543), (21)
00000100 => (8765421), (3)
...
11111111 => (), (87654321)
Extrapolate this to any value of X (8 above) and Y (2 above), and you have, I believe, your solution.
Update: Added example data
Update: You could also handle the case where all of the items do not need to be used by assigning a bin Y+1 as a hidden bin.
 [reply] [d/l] 

 [reply] 

 [reply] [d/l] 

Ok, not quite what I understood. My understanding of the problem were that empty bins were allowed.
In that case, my suggestion does nothing to make the solution easier, except that given X > Y, Y^{x} << X^{y} (thanks Corion and moritz for the confirmation).
Ok, given the numbers we are talking about, I guess that it could make it simpler.
 [reply] 
Re: x objects in y containers where all objects are used by ikegami (Pope) on Nov 06, 2009 at 19:29 UTC 
You need to choose y1 divisions in your set of objects.
For your example, that would be:
for my $p0 (1 .. 51) {
for my $p1 ($p0+1 .. 51) {
print(
substr('12345', 0, $p0),
"",
substr('12345', $p0, $p1$p0),
"",
substr('12345', $p1, 5$p1),
"\n",
);
}}
The general case requires y1 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_objects1 ],
(sub { [ $_[1]+1 .. $num_objects1 ] }) x ($num_containers2)
],
sub {
my $str = $str;
substr($str, $_, 0, '') for reverse @_;
print("$str\n");
},
);
12345
12345
12345
12345
12345
12345
 [reply] [d/l] [select] 

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) = N1;
T(N,K) = SIGMA(T(NX,K1)) for X = 1 to NK
Example: T(5,3) = T(4,2)+ T(3,2) + T(2,2)
= 3 + 2 + 1 = 6
 [reply] [d/l] 

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_objects1, $num_containers1)
= C(4, 2)
= 4! / (42)! / 2!
= (4*3) / (2*1)
= 6
 [reply] [d/l] 
Re: x objects in y containers where all objects are used by vitoco (Friar) on Nov 09, 2009 at 13:36 UTC 
#!perl
use v5.10;
use strict;
use warnings;
my $objects = "12345";
sub f {
print join('', @_) . "\n";
}
$objects =~ /^(.+)(.+)(.+)$
(?{ f($1, $2, $3) })
(*FAIL)
/x;
12345
12345
12345
12345
12345
12345
I don't think that this is a Diophantine equation, but it's still a freak way to solve this problem.
BTW, does the OP want other combinations like 13245?
 [reply] [d/l] [select] 
Re: x objects in y containers where all objects are used (multinomial coefficients) by repellent (Priest) on Nov 09, 2009 at 20:42 UTC 
This is a multinomial coefficients problem. The assumptions are:
 no empty containers
 order of items in containers do not matter in the results
 order of containers do matter in the results
mult_coeff(3, qw(a b c d e)); yields 150 results, which corresponds to the math:
5! 5!
 * 3 +  * 3 = 150
1! * 2! * 2! 1! * 1! * 3!
for combinations of 122, 212, 221, 113, 131, 311.
nck_with_leftover() should be memoized for performance.
A solution:
 [reply] [d/l] [select] 

