Representing a number as an unordered list of smaller numbers

Question

Suppose we want to encode a large integer \$x\$ as a list of words in such a way that the decoder can recover \$x\$ regardless of the order in which the words are received. Using lists of length \$k\$ and a dictionary of \$n\$ words, there are \$\binom{n+k-1}k\$ different multisets possible (why?), so we should be able to represent values of \$x\$ from \$1\$ through \$\binom{n+k-1}k\$.

This is a code golf challenge to implement such an encoder and decoder (as separate programs or functions); your golf score is the total code length. Any sensible/conventional input & output formats are allowed.

Encode: Given positive integers \$n,k,x\$ with \$x\le\binom{n+k-1}k\$, encode \$x\$ as a list of \$k\$ integers between \$1\$ and \$n\$ (inclusive).

Decode: Given \$n\$ and a list of \$k\$ integers between \$1\$ and \$n\$, output the decoded message \$x\$.

Correctness requirement: If encode(n,k,x) outputs \$L\$ and \$\operatorname{sort}(L)=\operatorname{sort}(M)\$, then decode(n,M) outputs \$x\$.

Runtime requirement: Both operations must run in polynomial time with respect to the length of \$x\$ in bits. This is meant to rule out impractical brute-force solutions that just enumerate all the multisets.

Answer 1

Python, 258 bytes

from numpy import*
P=cumprod;p=prod
def e(x,k):r=r_[:k]+1;f=p(r);X=x*f-f;i=int(X**(1/k));Q=P([1,*i+r]);Q[-2::-1]*=P(i+1-r);j=sum(Q<=X);x-=Q[j-1]//f;k-=1;return*(1//k*[x]or e(x,k)),j+i-k
d=lambda L,j=1:1+sum([p(s-1+r_[:j])//p(r_[1:(j:=j+1)])for s in sort(L)])

Attempt This Online!

Two functions e and d for encoding and decoding: We do not use or accept parameter n since it is not needed (because using the "natural" encoding different n will give the same result provided they are large enough).

Multisets are represented as sorted sequences; the decoder also accepts unsorted input.

With n eliminated it actually makes sense to talk about complexity in x because now x can grow without bound.

I'll assume fixed k and that all basic operations including taking the kth root are polynomial in the bit length of their operands. As k is fixed this will also hold for all factorials and binomial coefficients the functions use.

How?

Decoding is easy since it amounts to summing a couple of binomial coefficients.

Encoding is a bit more tricky as we need to invert binomial coefficients (in n, k is fixed) to make this constant in terms of basic operations we use the simple inequality

\$n^\underline k \le n^k \le n^\overline k\$

where the underline and overline denote falling and rising factorials.

To find the largest n such that

\$\begin{pmatrix}n+k-1 \\ k \end{pmatrix}\le x\$

we take the kth root of k!x and then brute force check all rising factorials whose terms "pass" through the value obtained, k in total.

Answer 2

Charcoal, 80 + 31 = 111 bytes

Encoder, 80 bytes

ＮθＮη≔⁰ζ≔⁰ε≔¹δＷ¬›δη«≔δε≦⊕ζ≔÷×δ⁺ζθζδ»Ｆ⮌…⁰θ«Ｗ›εη«≦⊖ζ≔÷×εζ⁺ζ⊕ιε»⟦Ｉζ⟧≧⁻εη¿ι≔÷×ε⊕ι⁺ζιε

Try it online! Link is to verbose version of code. 0-indexed. Takes k and x as inputs. Explanation: Port of the sord function from this Math.SE answer, but outputs the values in reverse order since it's golfier.

Decoder, 31 bytes

Ｗ⁻θυＦ№θ⌊ι⊞υ⌊ιＩΣＥυ÷Π…·ι⁺ικΠ…·¹⊕κ

Try it online! Link is to verbose version of code. 0-indexed. Takes a list of k integers as input. Explanation:

Ｗ⁻θυＦ№θ⌊ι⊞υ⌊ι

Sort the integers.

ＩΣＥυ÷Π…·ι⁺ικΠ…·¹⊕κ

Apply the ords algorithm from this Math.SE answer.

Answer 3

Haskell, 283 bytes

import Data.List
i=fromIntegral
p=product
m=map
s=succ
t=pred
f n=p[1..n]
a k n=p[n..n+k-1]`div`f k
b k x=t$until((>x).a k)s$floor((i$x*f k)**(1/i k))
d _ _[]=0
d k n(e:f)=a k e+d(k-1)e f
e 1 n x=[x]
e k n x|let m=b k x=m:e(k-1)m(x-a k m)
c k n=(m s.e k n.t,s.d k n.m t.reverse.sort)

Try it online!