deterministic and reversible permutation function to store a message

Question

I'd like to hide a secret message in a column of a csv file by changing the order of the row.

I'm looking for a deterministic and reversible permutation function.

Suppose I have the row list A=[1,2,3,4,5] ordered lexicographically. I have 5! = 120 possible permutations. This means I can save a 6-bit message because 2^6 = 64 < 120.

I would like to have the following functions encode and decode.

A = [1,2,3,4,5]
message = '010010'

B = encode(A, message) # [2,1,3,4,5] for example

B = [2,1,3,4,5]
message = decode(B) # get back message

I can compute all permutations, but that would take too long if there are a lot of lines. The function must work with a lot a lines, for instance 10 000 lines. So I'm asking for help here if you have some suggestion.

Answer 1

Imagine a list of all permutations which is sorted in ascending order (most significant element first). Let N be the number of elements.

You want to determine the (0-based) index of your permutation in this list.

You can go element by element. If your fist element is a 3, you know that there are 2*(N-1)! many permutations before that starting with 1 or 2.

Then go to the next element, if its a 2, you get 1*(N-2)! permutations before, starting with 3,1.

Ans so on. At the end you have the index of the permutation in the list.

For the reverse have to decompose your index into the 1!, 2!, 3!, ... part with modulo. Like you would decompose the digits of a base10 number. This works because smaller factorials always divide the bigger factorials without remainder.

You finally interpret your index-number as binary.