Read more
I was helping a friend in finding all possible combinations of
schedules for a given set of courses, and it varied wildly the number of
schedules each course had, most had 2 or 3, but others had more than 15
schedules, and when selecting the larger ones, the number of possible
combinations blew up, and it was taking a looong time to compute.
A Ridiculous Question
So then, for fun, I started to think that those were ∼ 15 schedules in each of the 7 courses, which is roughly 15 × 7 = 105 schedules in total. So I asked
myself, given a fixed number of schedules, How many courses should I
distribute those 105 schedules so that
it maximizes the number of possible combinations?
Just to be clear, changing schedules from one course to another does
not make sense at all. This is just a purely algorithmic / mathematical
question.
Hypothesis
I have thought in the past about common cases of permutations and
combinations, like for example, in 10 coin
flips the result that has more combinations is 5 heads and 5
tails, hence the more likely result.
So I thought “Hmm!, this looks familiar, I bet we can get the most
combinations by distributing things evenly”, so my first guess was
to distribute schedules in a way that the number of courses were the
same as the average number of schedules in the courses, … roughly.
But that’s just a wild guess!, I want to know the real answer!
Testing
So naturally, I started testing my hypothesis. To make it simple, I
started with 10 items. Let’s test
different ways of distributing the items
>>> 5*5
25
>>> 4*4*2
32
>>> 3*3*3*1
27
>>> 2*2*2*2*2
32
>>> 3*3*4
36
So 3 × 3 × 4 is the winner, 3 groups of ∼ 3.333 items, nice! my guess looks strong,
both numbers are very close. But let’s test it with more items, let’s
try 20 items.
>>> 5*5*5*5
625
>>> 4*4*4*4*4
1024
>>> 3*3*3*3*3*3*2
1458
>>> 2*2*2*2*2*2*2*2*2*2
1024
Uh oh!, my guess is not doing well. The winner is now 3 × 3 × 3 × 3 × 3 × 3 × 2 which is 7 groups of ∼ 2.833 items, both numbers are now very
different. And the average number of items, in both tests, are
suspiciously close to 3.
But Hang on!, the groups of 4 and 2 give
the same combinations in both cases, is there a connection here?.
Yes there is! If we look closely, 4 × 4 × 4 × 4 × 4 and 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 are
essentially the same thing. In fact, we can always replace 4 with 2 × 2, because they are equivalent in both
calculating the combinations (4=2×2)
and preserving the number of items (4=2+2).
Ok, so if 2 and 4, by logic are always the same regardless of
the number of items, then 3 does indeed
seem to be the sweet spot. It’s interesting that I’ve never come across
this fact.
So what does
this have to do with number bases?
Well, I wanted to test bigger numbers, but I got lazy, so I started
to look for patterns, and I noticed that these calculations are
equivalent to calculating numbers in other numerical systems with
different bases.
For example, the number of combinations of 10 items distributed in groups of 2, results in 5
groups of 2 items each, and
that’s equivalent to the number of numbers that can be represented with
5 digits in base 2. This is because both scenarios
involve making 5 independent choices,
each with 2 options.
So in the 5 groups of 2 items each, we get that the number of
combinations is 2 × 2 × 2 × 2 × 2 = 32.
And in the case of 5 digits in
base 2 we get that the number of
numbers that can be represented is 25 = 32.
Some of you might notice that 11111
is 31, instead of 32, but that’s because 00000 is ignored, so after we count it back,
we get 32.
So these are the equivalences I found:
- The number of groups is equivalent to the
number of digits.
- The number of items in each group is equivalent to
the base number.
- And the total number of items is equivalent to
__________ I have no idea, but I am going to call it “units of
information”.
Edit: maybe the technical term is “radix
economy” (which is usually base
number × number of digits)
For example, How many items “units of
information” do we need in base 2
to represent the number 654987?.
But first, What do I mean by “units of information” exactly?, I
mean something like the amount of symbols used, …
What???.
Yes, base 2 has 2 possibilities, 1 or 0 in
each digit, so the “units of information” in n bits is 2n, and that’s the amount of symbols
used to represent a number.
Ok, so to calculate the “units of information”, we need the
number of bits needed to represent 654987. Let’s hunt it!
>>> 2*2*2*2*2*2*2*2*2*2 # 10 bits
1024
>>> 2**10
1024
>>> 2**18
262144
>>> 2**19
524288 # almost there
>>> 2**20
1048576
Yeah I know, I could have just used the logarithm
>>> math.log(654987, 2)
19.321106747160712
So we got 20 bits, and that means,
that the “units of information” contained is 20 × 2 = 40 "units of information".
Since 3 seems to be the most
efficient one, let’s find out what we can accomplish with the same 40 "units of information" but now in base 3.
First, how many trigits (base-3 digits) can we get with 40 "units of information"?.
40 ÷ 3 = 13.333, that means we can
fully represent 13 trigits using less
than 40 "units of information", 39 to be exact.
To use exactly 40 “units of information” we could use a
number that is a frankenstein mix of base
2 and base 3, specifically,
12 trigits and 2 bits. But there’s no need to complicate
things, let’s stick to 13 trigits.
Let’s see how many combinations we get with 13 trigits, or in other words, what’s the
maximum number we can describe using 13
trigits?, if we get more than what we get with 20 bits, then base
3 is more efficient, and so is using sets of 3 elements to maximize the cartesian
product.
>>> 3**13
1594323
>>> 2**20
1048576
Yayy!, using base 3 we got ∼ 50% more combinations, that means, we can
represent more numbers, besides the fact that we have a tiny bit less
“units of information” than base
2, in fact, here’s the difference
Conclusion
So folks, if you want to maximize the combinations of a cartesian
product, arrange your items in groups of 3.
Or conversely, if you want to minimize the number of combinations, stay
away from groups of 3.
Weeell, it turns out 3 is
not really the most optimal number, but it’s close enough, it’s still
the king among integers, and of many practical applications.
But the king of kings is in fact e, the base of the natural
logarithm.
And don’t ask me how a base e
number system would even look like, nor how would you even name the …
eits ?. You
can read more about it here
BTW “Entropy” may be a related concept to this. I’ve seen
people measuring
entropy in bits, in this fascinating take of Death Note’s Light Yagami’s
anonimity
Imagine an enemy is following you and you want to lose them.
Lucky for you, you live in a multiverse where people can jump through
universes, and you have a unique ability that no one else can, you can
jump to multiple universes at the same time, like creating clones of
you, or more like forking yourself.
You may jump to a single universe, but that’s useless because the
enemy can detect when and to which universe you jumped, and they can
easily keep tracking you.
So you cannot really lose track of your enemy, what you can
do is to overwhelm them!. If you jump to multiple universes at
the same time, on each universe a different version of you will continue
your journey, so even if your enemy tracks you, they will have to follow
you on each universe, and each version of you can keep jumping deeper
into the multiverse, you can see how this grows exponentially
So what’s the catch? Well, you can only jump 20
times. So how should you arrange those jumps in order to maximize the
number of “versions of you” your enemy would have to keep track
of?
Obviously, you should arrange them in jumps to ~3 universes. To be
more precise, 6 jumps of 3 universes + 1 jump of 2 universes = 20 jumps,
and that will give you 3*3*3*3*3*3*2 = 1458
“versions
of you”