# Representing a number as an unordered list of smaller numbers

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.

• Your restricted complexity requirement is perfectly legitimate, but impractical brute-force solutions and code-golf are actually good ol' friends. :-) Commented May 18, 2023 at 10:40
• I admit I'm less interested in the byte-level golf and more interested in seeing simple practical algorithms for this problem! Should I change the post in some way to reflect this?
– Karl
Commented May 18, 2023 at 16:22
• @Karl codegolf and simple/practical are pretty much mutually exclusive. If you are interested in the latter I suggest you drop the codegolf tag. Or rather I would suggest it if there weren't already an answer. Commented May 19, 2023 at 10:09
• Is there a reason that you expect this to be possible within the complexity constraint of polynomial in the bit-length of $x$? I think the most efficient algorithm will be much like those on en.wikipedia.org/wiki/… with tweaks to cater for repeats, which I don't think will be. Commented May 19, 2023 at 16:40

# 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.

• Apologies for my mistake and the previous comments and thank you for taking the time to respond to them! Commented May 20, 2023 at 14:36
• @Hunaphu no worries. Good to see you figured it out in the end. Commented May 20, 2023 at 19:44

# 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.

• Isn't the sord function O(x^{1/k}) which is not polynomial in the bit length of x? I can't read charcoal, so I looked at the math SE code instead. (I was curious because efficient inversion of the binomial coefficient was what I got stuck at at my own attempts.) Commented May 19, 2023 at 5:50
• @loopywalt The Math.SE question asks for the most efficient algorithm. I just assumed that it would be good enough for this question...
– Neil
Commented May 19, 2023 at 7:22

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]divf 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!