Randomly select a key from a table in Lua

Question

I want to randomly populate a grid in Lua using a list of possible items, which is defined as follows:

  -- Items
  items = {}
  items.glass = {}
  items.glass.color = colors.blue
  items.brick = {}
  items.brick.color = colors.red
  items.grass = {}
  items.grass.color = colors.green

So the keys of the table are "glass", "brick" and "grass".

How do I randomly select one of these keys if they are not addressable by a numeric index?

Answer 1

Well, I kind of got a workaround, but I would be open to any better suggestions.

The first solution consists of having a secondary table which serves as an index to the first table:

item_index = {"grass", "brick", "glass"}

Then I can randomly store a key of this table (board is a matrix that stores the value of the random entry in item_index):

local index = math.random(1,3)
board[i][j] = item_index[index]

After which I can get details of the original list as follows:

items[board[y][x]].color

The second solution, which I have decided on, involves adding the defined elements as array elements to the original table:

  -- Items
  items = {}
  items.glass = {}
  items.glass.color = colors.blue
  table.insert(items, items.glass)   --- Add item as array item
  items.brick = {}
  items.brick.color = colors.red
  table.insert(items, items.brick)   --- Add item as array item
  items.grass = {}
  items.grass.color = colors.green
  table.insert(items, items.grass)   --- Add item as array item

Then, I can address the elements directly using an index:

  local index = math.random(1,3)
  board[i][j] = items[index]

And they can be retrieved directly without the need for an additional lookup:

  board[y][x].color

Answer 2

Although your second method gives concise syntax, I think the first is easier to maintain. I can't test here, but I think you can get the best of both, won't this work:

local items = {
    glass = {
        color = colors.blue,
    },
    brick = {
        color = colors.red,
    },
    grass = {
         color = colors.green,
    },
}
local item_index = {"grass", "brick", "glass"}
local index = math.random(1,3)
board[i][j] = items[item_index[index]]
print('color:', board[i][j].color)

Answer 3

If you're table is not too big and you can just break off at a random point. This method assumes that you know the number of entries in the table (which is not equal to #table value, if the table has non-number keys).

So find the length of the table, then break at random(1, length(table)), like so:

local items = {} ....
items.grass.color = colors.green

local numitems = 0 -- find the size of the table
for k,v in pairs(items) do
    numitems = numitems + 1
end

local randval = math.random(1, numitems) -- get a random point

local randentry
local count = 0
for k,v in pairs(items) do
    count = count + 1
    if(count == randentry) then
        randentry = {key = k, val = v}
        break
    end
end

The goods: You don't have to keep track of the keys. It can be any table, you don't need to maintain it. The bad and ugly: It is O(n) - two linear passes.So, it is not at all ideal if you have big table.

Answer 4

The above answers assume you know what all of the keys are, which isn't something I was able to do earlier today. My solution:

function table.randFrom( t )
    local choice = "F"
    local n = 0
    for i, o in pairs(t) do
        n = n + 1
        if math.random() < (1/n) then
            choice = o      
        end
    end
    return choice 
end

Explanation: we can't use table.getn( t ) to get the size of the table, so we track it as we go. The first item will have a 1/1=1 chance of being picked; the second 1/2 = 0.5, and so on...

If you expand for N items, the Nth item will have a 1/N chance of being chosen. The first item will have a 1 - (1/2) - (1/3) - (1/4) - ... - (1/N) chance of not being replaced (remember, it is always chosen at first). This series converges to 1 - (N-1)/N = 1/N, which is equal to the chance of the last item being chosen.

Thus, each item in the array has an equal likelihood of being chosen; it is uniformly random. This also runs in O(n) time, which isn't great but it's the best you can do if you don't know your index names.