Array Combinations and Permutations

CONVENIENT PLOT DEVICE: I am having a burrito party and everyone is invited.

Unfortunately, I am a burrito tyrant, and thusly, I have published a list of approved burrito ingredients for my party.

Because I am stingy tyrant I have further decreed that each burrito may only include three toppings, and we will turn to my Burrito Assembler: The Spirit of ’55 to determine everyone’s burrito fate.

The Burrito Assembler: The Spirit of ‘55 needs to know every possible combination of these burrito toppings so that it can have a master list from which to assign everyone a burrito. How might we go about doing this?

One terrible solution would be to manually type out each of the possible burritos:

Another terrible solution would be to iterate through our ingredients array and assign each of them to various other burrito arrays, adding conditionals like

or

Fortunately, we don’t have to do either of these, as Ruby provides us with great methods for getting back all of the possible combinations or permutations of an array.

Wow look at all these permutations!

When called on an array, Array#permutation and Array#combination return every possible combination or permutation of the elements within that array. The difference between the two is that Array#permutation treats different orders of the same elements as different combinations, whereas Array#combination ignores different orders of the same elements, including each combination only once.

As you can see, Array#combination only includes each combination of elements a single time ([1,2] is considered the same as [2,1]), whereas Array#permutation treats these combinations differently (both [1,2] and [2,1] are included in the return).

Lets break down the syntax of these two methods.

In the above example, Array#combination takes in an argument of 2, which determines the length of the combinations returned to you; each combo array in the output has two elements. Changing this argument changes the return of the method.

This applies to Array#permutation as well, although the return of Array#permutation is almost always greater since it treats different ordered elements as different permutations.

You may have noticed that each time we call Array#permutation or Array#combination we’re calling it with .to_a. This is because the default return for either of these methods is an enumerable, which is generally much less useful than an array. Here’s what the output looks like without .to_a:

Array#permutation and Array#combination also have sister methods: Array#repeated_permutation and Array#repeated_combination. These differ from the main methods in that they allow for the repetition of elements as separate combinations or permutations.

As you can see, array.repeated_combination(2).to_a includes [1,1] and [2,2], return values which are not included in the standard array.combination(2).to_a. The same is true for their permutation counterparts.

Squidward is not pleased with spongebob.repeated_combination(4).to_a[0]

Let’s conclude by returning to our burrito party example.

If all 6 of my friends come to my burrito party, we can use Array#combination in our Burrito Assembler: The Spirit of ’55 to generate burritos for each guest which are guaranteed to not include duplicate ingredients.

Looks like Mango got the short end of the stick with his cheese, lettuce, and sour cream burrito, but that’s life.

Resources [1] [2] [3]

Developer, Songwriter, Bugbear Monk

Developer, Songwriter, Bugbear Monk