x objects in y containers where all objects are used

[Ectaris]

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.

[MidLifeXis]

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.

[Ectaris]

I think I can make this work. Thanks for the great idea MidLifeXis.

[jandrew]

I was intrigued and found Math::Fleximal and leveraged it into the following code based on MidLifeXis proposed solution.

Read more... (4 kB)

[MidLifeXis]

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.

[moritz]

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.

[blokhead]

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.

[moritz]

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.

[Ectaris]

My problem is that I don't need the number of combination's but the combination's themselves. Order does not matter and there containers do not have a maximum capacity.

[toolic]

I googled 'cpan combination' and found Math::Combinatorics.

Then, I googled 'cpan permute' and found Algorithm::Permute.

I have no idea if they will help you, but they seem promising.

[ack]

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.

[MidLifeXis]

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.

[blokhead]

The most straight-forward 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 .. $containers-1] }) x $objects ],
  sub {
    my @assignment = @_;

    my @bins;
    push @{ $bins[$assignment[$_]] }, $_ for 0 .. $objects-1;
    
    ## @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.

[ikegami]

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

[Anonymous Monk]

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

[ikegami]

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

[MidLifeXis]

Update2: Re-re-reading 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.

[blokhead]

In bin-packing, 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 bin-packing 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 NP-complete, 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).

[MidLifeXis]

Update: Bad assumption confirmed.

I am running on moritz's assumption that the bins have limited sizes. Otherwise, you are correct, it is a trivial loop or recursive iteration problem. You are also correct that the TSP is probably casting too large of a net. I tend to be a generalist.

The solution I have in mind is the general NP solution - exhaustive search with a fitness function. In this case, the fitness function would be to check if the binsize was overshot.

[vitoco]

Using one idea I took from The Oldest Plays the Piano by casiano, I wrote the following script that returns those 6 combinations:

#!perl
use v5.10;
use strict;
use warnings;

my $objects = "12345";

sub f {
  print join('|', @_) . "\n";
}

$objects =~ /^(.+)(.+)(.+)$
              (?{ f($1, $2, $3) })
              (*FAIL)
            /x;

123|4|5
12|34|5
12|3|45
1|234|5
1|23|45
1|2|345

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 13|24|5?

[repellent]

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 1-2-2, 2-1-2, 2-2-1, 1-1-3, 1-3-1, 3-1-1.

nck_with_leftover() should be memoized for performance.

A solution:

Read more... (1316 Bytes)