Table of contentsClick link to navigate to the desired location
This content has been automatically translated from Ukrainian.
Combinatorial explosion is a phenomenon where the number of possible options increases rapidly with the number of elements. Everything looks innocent until you start counting.
For example:
- We have 3 types of pizza and want to choose 2 —, these are only 3 options.
- But if we have 20 toppings and want to choose any combination? More than a million options!
In mathematics, it is related to combinatorics - a section studying ways of selecting and ordering objects.
In programming, artificial intelligence or game theory, the combinatorial explosion is the real enemy. For example, in chess, the number of possible positions after 5 moves — is more than 69 billion. It is simply impossible to go through all the options — requires optimizations, heuristics and workarounds.
Combinatorial explosion - this is a situation when it becomes impossible to "count everything" because there are too many — options.
The term sounds a little dramatic - and for good reason. He illustrates well how quickly a real mathematical storm can grow out of a simple task.
Combinatorial explosion when creating a new class in Ruby
In Ruby (as in other OOP languages) combinatorial explosion can occur when you try to predict all possible combinations of object behavior or dependencies between class parameters.
An example of failed Notification class design:
class Notification
def initialize(user:, type:, channel:, urgency:)
@user = user
@type = type #:comment, :like, :mention, :follow
@channel = channel #:email, :sms, :push
@urgency = urgency # :low, :medium, :high
end
def deliver
# logic based on all combinations
end
end
Now we have:
- 4 event types (:comment, :like, :mention, :follow)
- 3 sending channels (:email, :sms, :push)
- 3 levels of urgency (:low, :medium, :high)
It already 4 × 3 × 3 = 36 combinations, each of which potentially requires a separate delivery logic (deliver). Add 2 more parameters — and that's it hundreds of options, which are difficult to test and support.
How to avoid a combinatorial explosion?
1. Objects-strategies:
class EmailNotificationStrategy; def deliver; ...; end; end class PushNotificationStrategy; def deliver; ...; end; end
2. Share responsibility (SOLID):
- Notification doesn't have to know everything about all channels.
- Each channel implements its own behavior.
3. Metaprogramming (must be done wisely):
rubyCopyEditdefine_method("deliver_#{channel}_#{type}_#{urgency}") do
# ...
end
But if the methods are 100+, it will only make the situation worse. A combinatorial explosion in the classroom occurs when you try to "seal" into the classroom too many options for logic, related to the combination of parameters. Over time, this leads to unreadable code, bugs, and pain.
This post doesn't have any additions from the author yet.
