Quick Tip #16: Explosive combinatorials

Perl 6 has several sophisticated ways to make lists. I was playing with a particular task where I needed combinations for something similar to bin packing.

I have a list of items and I want to combine those into other lists of a particular length. Duplication doesn’t matter (so, not sets), although later I’ll want to filter the lists on some utility function. That’s not the interesting bit.

Create a list, and specify a length. Imagine a loop where the length gets bigger:

$ perl6
> my @n = <1 2 3>;
[1 2 3]
> my $n = 4;
4

Now for the fancy stuff. The xx replicates the list. It’s not flat. I get a list that has that number of lists. Yep, Perl 6 has proper lists of lists.

Then, I take that list of lists and reduce it with a cross operator. I end up with a bunch of lists of length $n in all the combinations:

> ( [X] ( @n xx $n ) )
((1 1 1 1) (1 1 1 2) (1 1 1 3) (1 1 2 1) (1 1 2 2) (1 1 2 3) 
(1 1 3 1) (1 1 3 2) (1 1 3 3) (1 2 1 1) (1 2 1 2) (1 2 1 3) 
(1 2 2 1) (1 2 2 2) (1 2 2 3) (1 2 3 1) (1 2 3 2) (1 2 3 3) 
(1 3 1 1) (1 3 1 2) (1 3 1 3) (1 3 2 1) (1 3 2 2) (1 3 2 3) 
(1 3 3 1) (1 3 3 2) (1 3 3 3) (2 1 1 1) (2 1 1 2) (2 1 1 3) 
(2 1 2 1) (2 1 2 2) (2 1 2 3) (2 1 3 1) (2 1 3 2) (2 1 3 3) 
(2 2 1 1) (2 2 1 2) (2 2 1 3) (2 2 2 1) (2 2 2 2) (2 2 2 3) 
(2 2 3 1) (2 2 3 2) (2 2 3 3) (2 3 1 1) (2 3 1 2) (2 3 1 3) 
(2 3 2 1) (2 3 2 2) (2 3 2 3) (2 3 3 1) (2 3 3 2) (2 3 3 3) 
(3 1 1 1) (3 1 1 2) (3 1 1 3) (3 1 2 1) (3 1 2 2) (3 1 2 3) 
(3 1 3 1) (3 1 3 2) (3 1 3 3) (3 2 1 1) (3 2 1 2) (3 2 1 3) 
(3 2 2 1) (3 2 2 2) (3 2 2 3) (3 2 3 1) (3 2 3 2) (3 2 3 3) 
(3 3 1 1) (3 3 1 2) (3 3 1 3) (3 3 2 1) (3 3 2 2) (3 3 2 3) 
(3 3 3 1) (3 3 3 2) (3 3 3 3))

Note that permutations are different, and that’s even easier because there’s a method for that:

> @n.permutations
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

But, let’s do it step by step.

First, I have a list:

> (1, 2, 3)
( 1 2 3 )

Now, I want to replicate it. I can do that to get two lists in a bigger list:

> (1, 2, 3) xx 2
((1 2 3) (1 2 3))

As a side note, if you don’t like that, you could “de-containerize” (using |) the small list so it loses its structure:

> |(1, 2, 3) xx 2
(1 2 3 1 2 3)

I want to keep the structure, however, so I can combine two copies of the list. The next step is a cross. Here I do it by hand:

> (1, 2, 3) X ( 1, 2, 3 )
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

That’s not so bad. The cross makes little lists of the first element of the first list and all the elements of the second list in turn. Then with the second element, and so on. The big list is a bunch of two element little lists.

Now, do that as a reduction. With two lists, it’s the same result:

> [X] (1, 2, 3), (1, 2, 3)
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

But, try it with three lists. The lefthand cross gives the result I’ve already shown. There’s one more cross to go. Take the first element, (1, 1) and combine it with 1 to get (1, 1, 1). And, do all of those:

> (1, 2, 3) X ( 1, 2, 3 ) X ( 1, 2, 3 )
...
>  ((1, 1) ... (3, 3))    X ( 1, 2, 3 )
((1 1 1) (1 1 2) ... (3 3 2) (3 3 3))

The reduction operator does that for me. It takes two elements, does the operation, and puts the result back on the list. Then it takes that element and the next element and does the operation again. It keeps doing that until there’s one element. I can cross as many times as I like without repeatedly typing it. This is the same thing:

> [X] (1, 2, 3), ( 1, 2, 3 ), ( 1, 2, 3 )
...

And, I already know how to replicate the list:

> [X] (1, 2, 3) xx 3
((1 1 1) (1 1 2) ... (3 3 2) (3 3 3))

Now, I put that list in a variable and the count in another variable:

> [X] @n xx $n
( ... )

The combinatorial explosion might wreck the computer, but that’s why they make bigger computers. And, later, Perl 6 will let things happen in parallel.

But, I said that I wanted to apply a utility function to these. I can grep those:

> ( [X] @n xx 5 ).grep( { .sum > 13 } )
((2 3 3 3 3) (3 2 3 3 3) (3 3 2 3 3) (3 3 3 2 3) (3 3 3 3 2) (3 3 3 3 3))

But, I can do better than that! Oh yeah, it gets better. I want to partition the big set. I can call categorize. The string I return is which hash key the item “belongs” to. I get a hash back, and each key has an array with the values associated with that key:

> ( [X] @n xx 5 ).categorize( { .sum > 13 ?? 'pass' !! 'fail' } )
{fail => [(1 1 1 1 1) ... (3 3 3 3 1)], pass => [(2 3 3 3 3) (3 2 3 3 3) (3 3 2 3 3) (3 3 3 2 3) (3 3 3 3 2) (3 3 3 3 3)]}

This sort of thing replaces several Perl 5 modules I’ve written where I had to manage arrays of arrays to build tuples.

Leave a Reply

Your email address will not be published. Required fields are marked *