1

I am currently looking for a way to encode a list of random numbers most efficently (as in length).

To be specific, I have an array of 11 numbers containing each number from 0 to 10. The order will be randomized, and I need to get the smallest possible representation of these orderings.

I am currently trying with the fact that these arrays will have 11! unique cases, which means I would be able to push it down to 5 base-84 characters. However, simply converting to base-84 from base-11 will give me 6 characters. With my math knowledge I cannot think about any way to reduce it to 5 characters. Is there a way I can achieve this?

Thanks!

12
  • 1
    Why base 84? Why not some arbitrarily larger base? Because it seems to me like all you're doing here is asking for a data structure that contains 11! distinct values. It's also unclear what your goal here is, since reducing the character count at the cost of increasing the base is unlikely to yield any real world performance on a binary machine.
    – Flater
    Commented Jan 31, 2023 at 23:27
  • 1
    What application is this where you are sweating a few bytes in 2023 Commented Jan 31, 2023 at 23:31
  • 1
    Should this be on code golf instead?
    – svidgen
    Commented Feb 1, 2023 at 0:20
  • 1
    @DK13: because the rules of the site is that questions pertain to specific, real world problems, rather than brainstorming. Commented Feb 1, 2023 at 0:29
  • 1
    See [Lehmer code}(en.wikipedia.org/wiki/Lehmer_code). there is no table for encoding and decoding needed.
    – Doc Brown
    Commented Feb 1, 2023 at 7:24

4 Answers 4

2

There's a huge difference between 11 random numbers in range 0-10 and permutations (where each number occurs only once). Which do you actually want to represent? Naturally, the number of possible permutations without repetition is much smaller than the number of possible combinations with repetition.

However, what's your actual motivation? Just curiosity, or an actual problem where 5 versus 6 characters would make a difference that breaks your business model?

1
  • In my case, the number would not repeat. My actual motivation is the fact that its possible to reduce, but I cannot find a way to do it. As you said, in real application it wouldn't matter a bit.
    – DK13
    Commented Jan 31, 2023 at 23:31
2

You can do it in 4 characters

total number of permutations is 11! = 39916800

number of bits needed to represent that number log2(11!) = 25.25

bits in a char = 8

4 characters 8*4 = 32 bits

So you just need a table of what order your permutations are, number them, convert the 32 bit int which corresponds to the particular order you have randomly generated, split it into 4, convert each set of 8 bits into a character. write them out.

7
  • 1
    And of course since you could naively store them in 6 bytes, you'd need to keep track of just shy of 20 million combos for this to break even. Commented Feb 1, 2023 at 0:32
  • 1
    @whatsisname with some basic compression (000, 001, 010, 011, 100, 101, 110, 111 00, 111 01, 111 10) you can even pack it in 5 bytes (39 bits) vs. straight 4 bits per value (4 * 11 = 44 requiring 6 bytes). Commented Feb 1, 2023 at 5:46
  • 2
    "So you just need a table of what order your permutations are" - or you inform yourself a little bit more about the theory of such encodings, which can save you the table.
    – Doc Brown
    Commented Feb 1, 2023 at 7:25
  • 2
    Actually, since 80*80*80*80 = 40960000, you can represent each permutation with 4 characters from an 80-character subset of ASCII. Reversibly encoding the permutations is relatively easy. "I have a truly marvelous demonstration of this proposition which this margin is too narrow to contain" Commented Feb 1, 2023 at 8:41
  • @DocBrown I guess you could just define the method of generating the table. but I prefer to print mine out, get a nice leather binding, put it in my book case with a misleading title and then leave cryptic clues as to where to find it
    – Ewan
    Commented Feb 1, 2023 at 16:07
2

You only need four bytes

You can fit the whole thing into an unsigned, 32-bit int, which is only four bytes.

To pack a series of values you can usually use multiplication and addition, like this:

uint encodedValue = 0;
foreach (int element in input)
{
    encodedValue *= 11;
    encodedValue += element;
}

This would encode a stream of numbers between 0 and 10 inclusive. You then run a similar loop to decode, but in reverse, and instead of multiplying you divide, and instead of adding you take the modulus.

for (int i=0; i<11; i++)
{
    output[10-i] = encodedValue % 11;
    output /= 11;
}

Hopefully this procedure is somewhat familiar to you (although usually the base is 16 or 256, and is often done with logical shift left/right and logical AND instead of modulus. Both of these are just shortcuts. The underlying math is the same.)

But we can do better. While the first element can be any of 11 possible values (and therefore has an "alphabet" with count = 11), we know that the second element will be one of 10 possible values (with an alphabet with count = 10). Each step reduces the size of the alphabet. So you can reduce the multiplier as you go.

static uint Encode(byte[] input)
{
    var alphabet = Enumerable.Range(0,11).ToList();
    uint encodedValue = 0;
    byte multiplier = 10;
    for (int i=0; i<10; i++)
    {
        var element = input[i];
        var index = alphabet.IndexOf(element);
        alphabet.RemoveAt(index);
        encodedValue += (uint)index;
        encodedValue *= (multiplier--);
    }
    
    return encodedValue;
}

Notice we are only encoding ten values. The eleventh can be inferred because the other ten possible values are already taken.

The output of this process is a single, unsigned 32-bit integer, which requires only four bytes.

Decoding is a little more difficult since we have to reproduce the original alphabets, which has to be done forwards, even though everything else is backwards. So we do one pass backwards (to reverse the math) and one pass forward (to determine values based on the alphabet).

static byte[] Decode(uint input)
{
    var result = new byte[11];
    uint divisor = 2;
    var tmp = new int[11];
    var alphabet = Enumerable.Range(0,11).ToList();
    for (int i=0; i<10; i++)
    {
        tmp[i] = (int)(input % divisor);
        input /= (divisor++);
    }
    
    for (int j=9; j>=0; j--)
    {
        var index = tmp[j];
        var number = alphabet[index];
        result[9-j] = (byte)number;
        alphabet.RemoveAt(index);
    }
    result[10] = (byte)alphabet[0];
    
    return result;
}

Here is a working example on DotNetFiddle that demonstrates the procedure. You can click "Run" repeatedly to see that the decoded value always matches the input, even though the only data passed to it is a uint.

2
  • Nice solution. However, a trivial solution takes 6 bytes (just encode the numbers as nibbles). This mainly points out the uselessness of the question.
    – user949300
    Commented Feb 2, 2023 at 0:50
  • 1
    Agreed, I can't imagine a practical use for it. But it was fun to figure out an answer. :)
    – John Wu
    Commented Feb 2, 2023 at 1:41
0

There are 11! (39916800) different permutations of the sequence 0…10. There are 149186 characters currently assigned.

So, with only two characters (22256462596 combinations), you can encode every possible permutation.

4
  • Since 149186 is greater than 256x256, this stretches the definition of "character"
    – user949300
    Commented Feb 2, 2023 at 0:47
  • @user949300: I think you are confusing the definition of octet (a sequence of 8 bits) and character ("a unit of information that roughly corresponds to a grapheme, grapheme-like unit, or symbol"). Commented Feb 2, 2023 at 8:20
  • The question is about most efficient way to encode by length, so the actual size of the entity in bits is what matters. You stretched "character" to larger than a unicode 16 bit representation. The actual size of your representation would be something more than 4 bytes, probably 6. A simple and trivial encode by nibble algorithm takes just 6 bytes.
    – user949300
    Commented Feb 2, 2023 at 16:40
  • @user949300: The OP explicitly asks about characters 3 times in the question and 0 times about bytes. If the OP wanted to ask about bytes instead of characters, they would have asked about bytes instead of characters. Also, a byte is simply the smallest addressable unit of memory on a particular platform. So, talking about bytes does not make sense in this context, because the OP never specified the platform. At my employer, we are working with two platforms where a byte is 24 bits and 32 bits, respectively, so on the second platform, I can easily represent it in 1 byte. Commented Feb 3, 2023 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.