What would it take to create a feasibly computable injective function sending elements of $\mathbb{Z}_{k}$ (for the largest possible $k$) into, say, the set of distinct states of a bag of $n$ freely tumbling 3x3x3 standard Rubik's Cubes without twisted corners? I thank commenter “Karl” for pointing out that the lexographic ordering of possible bag states exists, but is not feasible to directly compute in the general case.
$\text{log}_2{({8! \times 3^7 \times \frac{12!}{2} \times 2^{11}})} \approx 65.229 \gt 64$, so I can clearly see that at least injecting $\mathbb{Z}_{2^{64}}$ is possible in the single-cube case, and I thank Daniel Schepler for an enlightening comment making that possibility a reality by suggesting to use mixed-base arithmetic as an essentially trivial bijection, which is easily computed in a reasonable amount of time, with the set of positive integers less than the order of the group.
My original expansion of the question remains, however: if you have multiple otherwise indistinguishable cubes tumbling freely together (e.g. in a drawer), I believe the number of bits stored per cube should be $\text{log}_2{({ \binom { 8! \times 3^7 \times 12! \div 2 \times 2^{11} + n - 1 } {n}} )} \div n$; this doesn't drop below $64$ until $n=5$, so, if my math is correct, then one could even theoretically create a function that works as a codec to store arbitrary 256-bit blobs in “rubik's socks” (containers with 4 standard cubes inside of them).
Has such a function ever been discussed, proposed, or invented before now?
Approximately how much effort would it be to create it? Would it be an hour's labor? An afternoon's labor? A dissertation's worth of labor? Or would it, like the 1-cube case, only take a few seconds of lucky insight to nail down?
I was not able to find any prior art on the specific idea of “scrambled Rubik’s Cubes as data storage medium”.
To reify this idea completely required 2 steps:
Injecting integers into cube scrambles
Injecting integers into multisets of integer representatives of cube scrambles
Each of these steps, thankfully, turned out to be a pretty straightforward application only of existing techniques; no new research was required to solve this!
The first step can be done (h/t Daniel Schepler from Math Overflow) by putting the input integer in a particular mixed radix form, then applying the Fisher–Yates algorithm (or any true shuffle algorithm) to scramble the pieces of the cube with the integer's digits in lieu of random numbers; this creates a bijection—needing no discoveries newer than 1938. (Additional storage can be got by using further digits to twist the corners and flip the edges; though care must be taken to avoid prescribing illegal scrambles.)
The second step can be done (h/t pseudonymous “Y. Beer” from Grant Sanderson's Summer of Math Exposition creators' forum) by treating the bag as a multiset of (integer representatives of) cube scrambles, then applying the combinatorial representation of integers—which was at least invented by 2005.
Details
1. $\mathbb{Z}_n \leftrightarrow \text{scramble}$
Legal scrambles of a single Rubik's cube can be modeled as a mixed-radix number, as follows:
Eleven of the radices are $12, 11, \dots, 2$; their digits are consumed in lieu of random values in a pseudo-shuffle of the edge pieces.
Six of the radices are $8, 7, \dots, 3$; their digits are likewise consumed as inputs to the same pseudo-shuffle on the corner pieces. (The last swap here is constrained to keep the resulting scramble legal.)
Eleven of the radices are $2$; their digits determine the orientation of the first eleven edge pieces. (The orientation of the last edge piece is constrained by legality.)
Seven of the radices are $3$; their digits determine through what angle the first seven corner pieces will be twisted. (The twist of the last corner is likewise constrained by legality, so that the total twist of all corners is $0 \text{ mod } 3$.)
(Obviously, if desired, this can be generalized pretty easily to variant cubes such as picture cubes, by adding extra radices for the extra degrees of freedom, taking care to divide out any constraints on them.)
Now that you've got a bijection between $\mathbb{Z}_{\text{the order of a Rubik's orbit}}$ and concrete scrambles within that orbit, it's straightforward to store your 65-and-a-quarter-ish bits of entropy in the cube.
But, obviously, we're not done yet. If you want to store more than 1 cube in a bag, and have that bag encode a commensurately larger integer, inefficiencies from the obvious "naive" scheme of spending the high bits on synthetically ordering the cubes drop the system's capacity below 64 bits per cube once you surpass just $k=2$ cubes, and consume all additional storage beyond $k=2^{64}$ cubes per bag, which is just sad. To solve that…
2. $\mathbb{N} \leftrightarrow \text{multiset}(n, k)$
A “bag” of potentially scrambled and otherwise indistinguishable cubes here is represented as a multiset of cardinality $k = \text{quantity of cubes}$, with elements from a set of cardinality $n={({12!})}\times{({8!\div 2})}\times{({2^{11}})}\times{({3^{7}})}$.
However, the combinatorial number system works with combinations, not multisets. The workaround for this is a bijection between combinations and multisets:
first, use a bit of creativity with the combinatorial number system to biject the input into $\left\{c \in {\mathcal{P}\left(\mathbb{N}\right)} \mid \forall x \in c \left( \left( n+\left\lvert c\right\rvert-1 \right) \gt x \right) \right\}$;
from there, it's a straightforward bijection ($c \mapsto \biguplus\left\{\left[x-i\right] \mid \left( i = \left\lvert \left\{y \in c \mid y \lt x\right\}\right\rvert \right) \right\}$[notation] or
[x-i for i, x in enumerate(sorted(c))]) over to a multiset of valid scramble representatives.