{"id":2700,"date":"2023-05-29T12:51:59","date_gmt":"2023-05-29T17:51:59","guid":{"rendered":"http:\/\/www.ishygddt.xyz\/~blog\/?p=2700"},"modified":"2023-05-29T14:30:34","modified_gmt":"2023-05-29T19:30:34","slug":"set-multiset-bijection","status":"publish","type":"post","link":"http:\/\/www.ishygddt.xyz\/~blog\/2023\/05\/set-multiset-bijection","title":{"rendered":"Bijection between sets and multisets"},"content":{"rendered":"

I needed this for a project I'm working on. I needed to inject<\/a> appropriately small integers to multisets<\/a> of a given universe and cardinality, but all I could find was this scheme<\/a>, which only injects integers into sets<\/em> of a given universe and cardinality.<\/p>\n

On the Wikipedia page about multisets, I found this elaborate diagram<\/a> showing a bijection between the<\/abbr> k<\/i>=3-element multisets of a n<\/i>=5-element universe and the<\/abbr> k<\/i>-element subsets of an n<\/i>+k<\/i>\u22121-element universe. While this certainly showed that the bijection exists<\/em> for k<\/i>=3; n<\/i>=5, and at least\u00a0marginally<\/em> convinced me that it would generalize, it seemed very convoluted and hard to interpret. After much puzzling, I was able to translate it into code, but how it worked still escaped me. However, after studying the code translation for a while, I figured it out\u2014it's so incredibly simple\u2014all you need to do to take a multiset and reversibly transform it into a set of the same cardinality belonging to the smallest feasible universe is incrementally offset every element<\/strong> (including non-unique ones)!<\/p>\n

That is: start with the multiset's smallest element, add 0 to it; then go to the next element (which might be a duplicate), and add 1 to it (which will guarantee it's no longer a duplicate); then go to the next element (which might still be a duplicate of the first), and add 2 to it (which will guarantee it's no longer a duplicate of the first or<\/em> second elements), and so on. After this transformation is applied, you'll have a set with no duplicates<\/em>, from a k<\/i>\u22121-elements-larger universe, that can easily be transformed back by just subtracting instead of adding!<\/p>\n

Now, you might ask, \u201cwell, what if my elements aren't integers?\u201d In that case, just order<\/a> the elements (you are authorized by God<\/a> to fake this if you feel like there's no obvious ordering) and biject them over into an (obviously contiguous, ideally 0-indexed) block of integers for the transformation. (So replace the \u201csmallest\u201d unique element with 0, the \u201csecond-smallest\u201d unique element with 1, et cetera.) You will<\/em> need a larger target set than your source set, anyway, and with integers you get \u201cfor free\u201d an easy way to cope with this requirement.<\/p>\n

Below, I've included some example code demonstrating this simplified interpretation of the bijection, plus a demo of the combinatorial number system thrown in for good measure.<\/p>\n

\n
from math import comb as _comb\nfrom itertools import count as _count\n\n\n_Multiset = list  # :^)\n\n\ndef combination_to_multiset(s):\n\treturn _Multiset(elem - offset for offset, elem in enumerate(sorted(s)))\n\n\ndef multiset_to_combination(ms):\n\treturn set(elem + offset for offset, elem in enumerate(sorted(ms)))\n\n\n# Bonus methods\n\n\ndef multicomb(n, k):\n\t"https:\/\/en.wikipedia.org\/wiki\/Multiset#Counting_multisets"\n\treturn _comb(n + k - 1, k)\n\n\ndef integer_to_combination(i, k, n):\n\t"https:\/\/en.wikipedia.org\/wiki\/Combinatorial_number_system#Finding_the_k-combination_for_a_given_number"\n\ts = set()\n\tuniverse = range(n)\n\tif not 0 <= i < _comb(n, k):\n\t\traise ValueError(f"not 0 <= {i} < comb({n}, {k})")\n\tfor j in range(k, 0, -1):\n\t\telem = _search_maxsatisfying(lambda n, r=j, N=i, comb=_comb: _comb(n, r) <= N)\n\t\tassert elem in universe\n\t\tassert elem not in s\n\t\ts.add(elem)\n\t\ti -= _comb(elem, j)\n\tassert i == 0\n\treturn s\n\n\ndef combination_to_integer(s):\n\t"https:\/\/en.wikipedia.org\/wiki\/Combinatorial_number_system#Place_of_a_combination_in_the_ordering"\n\treturn sum(_comb(elem, k+1) for k, elem in enumerate(sorted(s)))\n\n\ndef _search_maxsatisfying(predicate, initial=0):\n\t"Return the largest n for which predicate succeeds"\n\tlower_bound = initial\n\tupper_bound = lower_bound + 1\n\tif not predicate(lower_bound):\n\t\traise ValueError(f"initial does not satisfy predicate")\n\t# 1. Exponential approach to establish upper-bound\n\twhile predicate(upper_bound):\n\t\tupper_bound = upper_bound*2\n\tguess = lower_bound = (upper_bound - 1) and (upper_bound \/\/ 2)\n\t# 2. Binary search\n\twhile (upper_bound - lower_bound) > 1:\n\t\tguess = lower_bound + (upper_bound - lower_bound) \/\/ 2\n\t\tif not predicate(guess):\n\t\t\tupper_bound = guess\n\t\t\tguess = lower_bound\n\t\telse:\n\t\t\tlower_bound = guess\n\tassert predicate(guess) and not predicate(guess+1)\n\treturn guess\n\n\n# Composed methods\n\n\ndef integer_to_multiset(i, k=None, n=43252003274489856000):\n\t# TODO: fix redundancy to enable incremental decoding\n\t# https:\/\/discord.com\/channels\/834837272234426438\/866699434116775946\/1112819325666070539?invite=WZvZMVsXXR\n\tif k is None:\n\t\tassert n > 1\n\t\tk = next(k for k in _count(1) if multicomb(n, k) > i)\n\tnPrime = n + k - 1\n\treturn combination_to_multiset(integer_to_combination(i, k, nPrime))\n\n\ndef multiset_to_integer(ms):\n\treturn combination_to_integer(multiset_to_combination(ms))<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
To take a multiset and reversibly transform it into a set of the same cardinality \u2026 start with the multiset's smallest element, add 0 to it; then go to the next element (which might be a duplicate), and add 1 to it (which will guarantee it's no longer a duplicate); then go to the next element (which might still be a duplicate of the first), and add 2 to it (which will guarantee it's no longer a duplicate of the first or<\/em> second elements), and so on. After this transformation is applied, you'll have a set with no duplicates<\/em>, from a k<\/i>\u22121-elements-larger universe, that can easily be transformed back by just subtracting instead of adding!<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-2700","post","type-post","status-publish","format-standard","hentry","category-drafts"],"_links":{"self":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts\/2700","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/comments?post=2700"}],"version-history":[{"count":22,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts\/2700\/revisions"}],"predecessor-version":[{"id":2722,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts\/2700\/revisions\/2722"}],"wp:attachment":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/media?parent=2700"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/categories?post=2700"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/tags?post=2700"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}