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.
burrito_ingredients=["beans","chicken","cheese","lettuce","pico","sour cream"]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:
burrito1=["beans","lettuce","pico"]
burrito2=["beans","lettuce","cheese"]
burrito3=["beans","lettuce","sour cream"]
burrito4= ...Another terrible solution would be to iterate through our ingredients array and assign each of them to various other burrito arrays, adding conditionals like
unless burrito.count==3or
unless burrito.include?("topping whatever")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.
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.
array=[1,2,3]array.combination(2).to_a
=>[[1,2],[1,3],[2,3]]array.permutation(2).to_a
=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
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.
array=[1,2,3]array.combination(2).to_a
=>[[1,2],[1,3],[2,3]]
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.
array.combination(3).to_a
=> [[1, 2, 3]]array.combination(4).to_a
=> []
#the return of an empty array represents that no combinations are present of the specified lengtharray.combination(0).to_a
=> [[]]
#the return of a single nested array represents the single possible combination with a length of '0'
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.
array.permutation(3).to_a
=> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]array.permutation(4).to_a
=> []array.permutation(0).to_a
=> [[]]
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(2)
=> #<Enumerator: [1, 2, 3]:permutation(2)>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.
array=[1,2,3]array.combination(2).to_a
=> [[1, 2], [1, 3], [2, 3]]array.repeated_combination(2).to_a
=> [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
array.permutation(2).to_a
=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]array.repeated_permutation(2).to_a
=> [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
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.
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.
ruby burrito_assembler_spirt_of_55.rb
=>Chad got a burrito with chicken, cheese, lettuce, and love.
Mango got a burrito with cheese, lettuce, sour cream, and love.
Applekid got a burrito with cheese, pico, sour cream, and love.
Rangus got a burrito with beans, chicken, sour cream, and love.
Mobin got a burrito with chicken, cheese, pico, and love.
Grimp got a burrito with beans, cheese, sour cream, and love.Looks like Mango got the short end of the stick with his cheese, lettuce, and sour cream burrito, but that’s life.
