Shuffle and unscramble a string (Lua)

Question

I have a function to shuffle strings from another article adapted to reorder the characters with a table of predefined numbers. It works perfectly, so I also needed a function to unscramble this string using the number table, but I have no idea how to do this, especially after having tried and failed several times.

Shuffle function:

randomValues = {} 
for i = 1, 60 do
   table.insert(randomValues, 1, math.random())
end
function shuffle(str)
   math.randomseed(4)
   local letters = {}
   local idx = 0
   for letter in str:gmatch'.[\128-\191]*' do
      idx = idx + 1
      table.insert(letters, {letter = letter, rnd = randomValues[idx]})
   end
   table.sort(letters, function(a, b) return a.rnd < b.rnd end)
   for i, v in ipairs(letters) do 
      letters[i] = v.letter
   end
   return table.concat(letters)
end

Any tips?

score 1 · Accepted Answer · answered Aug 20 '21 at 07:50

I will assume, that all you're trying to do is:

Split a string into unicode characters.
Shuffle these characters.
Restore the characters to their original position.

I have separated the splitting up of unicode characters and doing the actual shuffle, to make it a bit easier to follow.

1. Splitting the characters

Starting off with the splitting of characters:

-- Splits a string into a table of unicode characters.
local function splitLetters(str)
  local letters = {}
  for letter in str:gmatch'.[\128-\191]*' do
     table.insert(letters, letter)
  end
  return letters
end

This is mostly copied from the first part of your function.

2. Shuffling the table of characters

Now that we have a nice table of characters, that we can work with, it's time to shuffle them. Shuffling a list can be done by going through each character in order and swapping it with a randomly chosen (but still unshuffled) item. While we do that, we also keep a table of all indices that got swapped, which I call swapTable here.

-- Shuffles in place and returns a table, which can be used to unshuffle.
local function shuffle(items)
  local swapTable = {}
  for i = 1, #items - 1 do
    -- Swap the first item with a random item (including itself).
    local j = math.random(i, #items)
    items[i], items[j] = items[j], items[i]
    -- Keep track of each swap so we can undo it.
    table.insert(swapTable, j)
    -- Everything up to i is now random.
    -- The last iteration can be skipped, as it would always swap with itself.
    -- See #items - 1 at the top of the loop.
  end
  return swapTable
end

3. Restoring the letters to their original positions

Using this swapTable, it is now pretty straightforward to just do the whole shuffle again, but in reverse.

-- Restores a previous shuffle in place.
local function unshuffle(items, swapTable)
  -- Go through the swap table backwards, as we need to do everything in reverse.
  for i = #swapTable, 1, -1 do
    -- Do the same as before, but using the swap table.
    local j = swapTable[i]
    items[i], items[j] = items[j], items[i]
  end
end

A full example using all those functions

Using those few functions (and table.concat to build up the list of letters into a string again) we can do everything you want:

-- Make our output reproducible
math.randomseed(42)

-- Split our test string into a table of unicode characters
local letters = splitLetters("Hellö Wörld! Höw are yoü?")

-- Shuffle them in-place, while also getting the swapTable
local swapTable = shuffle(letters)

-- Print out the shuffled string
print(table.concat(letters)) --> " rH?doröWüle Hl lwa eyöö!"

-- Unshuffle them in-place using the swapTable
unshuffle(letters, swapTable)

-- And we're back to the original string
print(table.concat(letters)) --> "Hellö Wörld! Höw are yoü?"

Creating the swapTable upfront

In your example, you generate the swapTable upfront (and it also works slightly different for you). You can of course split that part out and have your shuffle function work similar to how unshuffle is currently implemented. Tell me, if you want me to elaborate on that.