What would be a good way to encode 52 integers into a fewer amount?

Question

So for example, I have an array containing 52 shuffled integers between 0 and 52 - no repeated values.

How can I encode this array according to an algorithm such that it can be represented as less numbers, and then decode and again to reproduce the original values?

I was thinking I could create a big binary String and group grouping of 0's or 1's together as characters, and expand on that. Would that be the way to go? Thanks

possible duplicate of [Fast permutation -> number -> permutation mapping algorithms](http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms) — Nick Johnson, Aug 02 '11 at 12:06

score 8 · Accepted Answer · edited May 23 '17 at 12:04

8

There are 52! (that's fifty two factorial) different arrays like you describe. By the way they are called permutations. A single number between 0 and 52! uniquely represents such a permutation. You need 226 bits to store such a number. Eight 32-bit integers would do just as well.

You can read about mapping numbers to permutations and back here.

edited May 23 '17 at 12:04

Community

1
1

answered Aug 02 '11 at 10:05

n. m. could be an AI

112,515
14
128
243

Good answer, but this question is really a duplicate of the one you link to. – Nick Johnson Aug 02 '11 at 12:06

score 0 · Answer 2 · answered Aug 02 '11 at 09:49

0

you need a 6 bit var to store a values that is lower than 64. Union is the key

union DATAPACK
{
    unsigned int code1 : 6;
    unsigned int code2 : 6;
    unsigned int code3 : 6;
    unsigned int code4 : 6;
   ....
} array1;

answered Aug 02 '11 at 09:49

cprogrammer

5,503
3
36
56

score 0 · Answer 3 · answered Aug 02 '11 at 09:51

0

If your range is 0 to 52 then you only need 6 bits to store each number - so instead of 52 bytes (assuming you are using 1 byte per digit) you would only need 52 x 6/8 or 39 bytes.

Hardly seems worth saving though unless you have trillions of them to store.

answered Aug 02 '11 at 09:51

Roger

15,793
4
51
73

It's to send the state of a deck of cards, so would be at max 39 bytes then. Which isn't a problem at all, was thinking more along the lines of actually hiding the data a bit in the process as well? – rtheunissen Aug 02 '11 at 09:58

score 0 · Answer 4 · answered Aug 02 '11 at 09:51

0

What about partition the array in a quadtree or a spatial index and then use a space-filling-curve to reduce the complexity? Maybe a z-curve can do it or a hilbert-curve? Do you need a power of 2 2d array? It this your requirement?

answered Aug 02 '11 at 09:51

Micromega

12,486
7
35
72

What would be a good way to encode 52 integers into a fewer amount?

4 Answers4