I know this title makes what I am about to ask sound like an off topic CS theory question but please bear with me because I assure you that it is not! (Well mostly, actually I am about ~90% certain that this is a perhaps routine application of representation theory...) If you just want the problem without the backstory, skip to the bottom.

Anyway, I would like to get some way to uniquely encode tuples of finite sets of bits up to a some type of reordering. In other words, let's suppose I have k binary strings all of equal length n, or in other words $a_1, a_2, ... a_k \in \mathbb{F}_2^n$, and I want to find some way to encode them uniquely as a binary string of minimal length so that I can insert them into a dictionary for later use.

Now if I care about the order of each of these guys, then there is really only one way to go, which is to just concatenate each of the bit strings together into one big string of length $nk$.

However, suppose that I don't care about the ordering (for example, I consider these things to be sets not sequences), then instead I only want to encode the orbit of this sequence under the usual action of $S_k$. Now there are at least a couple of ways to do this; for example I could sort the sequence lexicographically, or by being more clever I could re-encode them using symmetric polynomials. As a simple application, I could use the usual basis and write the result equivalently as:

$b_1 = a_1 + a_2 + ... a_k$

$b_2 = (a_1 a_2) + (a_1 a_3) + ...$

....

$b_k = a_1 a_2 ... a_k$

Of course this can be computed in time on the order of $nk \log^2(k)$ by divide and conquer and FFT polynomial multiplication. Ignoring the subtleties of the time complexity of computing all these sums for the moment, this suggests the following interesting question:

Question 1: On average, what is the smallest length binary string needed to encode $k$ length $n$ binary strings up to permutation? (which can be computed in polynomial time).

It should be about $nk - k \: \log (k)$, since there are $k!$ permutations, but I am not exactly sure how to get there.

Now, as a follow up question, what is the best you can do for an arbitrary group? For example, if you only care about encoding the binary sequences up to alternation, what is the best way to do it? One possibility is to use the Vandermonde polynomials, however there is a need to be a bit careful here, since if this is done directly over $\mathbb{F}_2^n$, then one runs into the small problem that $a_k = -a_k$. So this leads to the following pair of questions:

Let $G$ be a group acting faithfully on the indices of a finite set of binary strings $a_1, a_2, ... a_k$ whose individual lengths are at most $n$:

Question 2: Is there an efficiently computable encoding of the orbit of $a_1, a_2, ... a_k$ under $G$ of length at most $nk$? (In other words, two sequences in the same orbit would map to the same string, and this encoding can be found in time polynomial in $\log(G), n$ and $k$.)

Question 3: Is there an efficiently computable encoding on the order of length $O(nk - \log(|G|))$ of the orbit?

EDIT: Adjusted the wording of the first question to be more specific. Also fixed my brain fart with dividing out by the entropy of G instead of subtracting (in my defense, it was about 3am my local time when I wrote this).

EDIT 2: I tried to be a bit more specific with the time complexity requirements to rule out silly things like "take lexicographically first element of the orbit".