1.0.0 • Published 3 years ago
drichlet-box v1.0.0
Drichlet Box
Context: Pigeonhole Principle Wikipedia Article.
A function that maps the (holesCount, pigeonsCount, pigeonIndex)
3-tuple to the corresponding holeIndex
, in constant time.
Explanation
Given a wooden structure with holesCount
pigeonholes and pigeonsCount
pigeons, the drichlet-box
function returns the zero-based hole index, holeIndex
, in which a pigeon indicated by the zero-based integer pigeonIndex
should go, so that the following holds:
- There are at least
floor(pigeonsCount/holesCount)
pigeons in a hole (small hole). - There are at most
floor(pigeonsCount/holesCount)
pigeons in a hole (big hole). drichlet-box
is an increasing function in regards to itspigeonIndex
argument.- The big holes are the first ones. In other words, if
i
is an index of a big hole andj
is an index of a small hole,i < j
.
1.0.0
3 years ago