deterministic and reversible permutation function to store a message

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.

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.

Here's an algorithm to convert between permutations and ranks in linear time. However, the ranking it uses is not lexicographic. It's weird, but consistent. I'm going to give two functions, one that converts from a rank to a permutation, and one that does the inverse.

First, to unrank (go from rank to permutation)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

Next, to rank:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q
] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q
展开收缩
, q[n-1])
  return s + n * rank(n-1, p, q)
end

The running time of both of these is O(n).

There's a nice, readable paper explaining why this works: Ranking & Unranking Permutations in Linear Time, by Myrvold & Ruskey, Information Processing Letters Volume 79, Issue 6, 30 September 2001, Pages 281–284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Easy way

Merge sort has the convenient property that every comparison used has a distinct effect on the output if there are no duplicate elements in the input. You can use this property to encode a message easily.

Start with your column in sorted order, and then perform a merge sort, except that each time you would compare two elements, use a bit from your message to determine the result instead.

In order to decode your message, you have to perform the merge sort operation in reverse. In each un-merge, you can use the value of each element to determine which input list it came from, which decodes one bit of message.

This method is pretty good, but it doesn't always provide the absolute maximum number of bits. Sometimes it gives you a little less, and sometimes more.

If you really need the maximum number of bits, then...

Harder Way

When performing a selection sort, there are exactly N! possible sequences of "next minimum element" results, and each different sequence produces different output.

Start with your elements in order, and then perform a selection sort, but instead of doing a search for the minimum element, use arithmetic decoding to decode the index of the chosen element from your message.

Using a reasonably sized register for the arithmetic encoding, this will within 1 or 2 bits of the optimal floor(log(N!)).