CODEWITHSUNDEEP
hash
Jakub Lédl
Jakub Lédl

Reputation: 1805

Finding a suitable integer representation for a collection of integer pairs

For a project I'm working on, I need a way to calculate a unique integer representation of a data structure with type [(int, int)], i. e. a collection of (nonnegative) integer pairs. The requirement is that while the ordering within the pair matters, the collection itself is order-insensitive. After some searching, I've come believe that a suitable solution would be to encode each pair using the Cantor pairing function and xor the results.

The range will be fairly small, say 1-700 for the first integer in the pair, 1-10 for the second one and the list will contain around 5-15 of these pairs.

If you believe there's a better solution, let me know, but an answer "yes, this will work" would be terrific as well :)

Upvotes: 1

Views: 123

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272517

[This answer assumes that when you say "unique", you really mean that; collisions are unacceptable.]

If the aim is to somehow uniquely map an arbitrary-sized collection of integer (pairs) onto a single (reasonably-sized) integer, then the answer is essentially "that's not possible". This can easily be demonstrated by appealing to the pigeonhole principle.

If the size of your collections is extremely limited, and the range of the input integers is extremely limited, then you may be able to do something. But in the general case, I'd suggest looking for a different solution to whatever your top-level problem is.

Update

As a worked example, let's consider the parameters you added to your question. 700 * 10 = 7000, so you need roughly 13 bits to uniquely represent each possible pair. With a maximum of 15 pairs, that's 195 bits needed in total.

Now, if order doesn't matter, then you can theoretically drop log2(15!) = 40 bits.* So in theory, you need an output datatype with 155 bits. Is that tractable?

* How one achieves this in practice is another question... ;)

Upvotes: 2

Related Questions