What is a good algorithm to scramble data in a 2-D grid

Question

I want to know if there exists an algorithm i can use where the input is a string of data and the output is a scrambled version of the same but in a 2 D array
ie given something like:

---

|1 2 3 4 5 6 7 8 9|

---

I want an output somewhat like:

---

|2 8 * 3 |

---

|7 9 4 1 |

---

|* 5 * 6 |

---

The scrambling would ideally be on the basis of a key and the same key or its pair can be used to unscramble the message.

Answer 1

It seems like you just want to permute a string. E.g., transform the string "123456789"+ 3 blanks into the string "28_37941_5_6". Putting it into a 2-d array is just formatting (e.g., agree its to be a 4x3 array and then after every 4 characters add a line break).

There are plenty of algorithms to randomly permute a string. For example, the Knuth shuffle (aka Fisher-Yates shuffle) requires you to go through each element of a list and randomly swap it with itself or an earlier item in the list. (That is for the i-th position in the list do a swap with the i-th position and the j-th position where j is a random number between 0 and i inclusive). For example, this shuffle is implemented in python below:

import random

def knuth_shuffle(to_shuffle):
    for i in range(1, len(to_shuffle)):
        j = random.randint(0, i)
        to_shuffle[i], to_shuffle[j] = to_shuffle[j], to_shuffle[i]
    return to_shuffle

We can slightly modify this to take the random numbers as a "key" which tells us what permutation to do:

import random

def generate_key(input_length):
    key = []
    for i in range(1, input_length):
        j = random.randint(0, i)
        key.append(j)
    return key

def knuth_keyed_shuffle(to_shuffle, key):
    shuffled = to_shuffle[:] # create a copy of input to modify
    for i, j in zip(range(1, len(shuffled)), key):
        shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
    return shuffled


def knuth_keyed_unshuffle(to_unshuffle, key):
    unshuffled = to_unshuffle[:] # create a copy of input to modify
    for i, j in reversed(zip(range(1, len(unshuffled)), key)):
        unshuffled[i], unshuffled[j] = unshuffled[j], unshuffled[i]
    return unshuffled

For example in python (after defining the functions above)

In [3]: text = list("123456789***")

In [4]: print text
['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

In [5]: key = generate_key(len(text))

In [6]: print key
[0, 0, 2, 2, 1, 1, 1, 6, 8, 2, 11]

In [7]: shuffled_text = knuth_keyed_shuffle(text, key)

In [8]: print shuffled_text
['3', '8', '*', '2', '4', '1', '9', '7', '*', '6', '5', '*']

In [9]: knuth_keyed_unshuffle(shuffled_text, key)
Out[9]: ['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

Some notes: first this will not be particularly secure.

Also, if you aren't particularly fond of using a list of integers as your key, you can encode it to a single integer between 0 and (n!-1) by using the factorial number system (factoriadic). The key is essentially a number written in base factorial with the least significant digit first -- the first digit is 0 or 1; second digit 0,1, or 2; third digit 0, 1, 2, or 3, ... n-th digit is an integer from 0 to n inclusive.