Obtaining A Random Key From A Dictionary

Hello everyone,

I am currently working on a party system (you know, like an RPG party) that has a method “GetListOfParties”, which simply returns a dictionary of all the parties in the server. For every party that is created, the dictionary holds it as such:

local ListOfParties 		= {}

local function AddParty(partyObject)
	ListOfParties[partyObject] = true

As well as the code for creating a party:

function party.new(player)
	local self 			= setmetatable({}, {__index = party});
	self.leader 		= player
	self.members 		= {[player] = true}
	return self

At first, my party.GetListOfParties() method looked like this:

function party.GetListOfParties()
	return ListOfParties

However, I realized that I wanted to obtain a random party from that list. I’m aware that in Java, there is a method called “map.keySet()”, which is pretty much what I’m looking for, but I don’t think there is anything related to that in Lua.

Are there any methods for obtaining a random key in a dictionary? I’ve tried this:

function party.GetListOfParties()
	local arrayOfParties = {}
	for partyObj, _ in next, ListOfParties do
		arrayOfParties[#arrayOfParties+1] = partyObj
	return arrayOfParties

The only problem is that this method is of linear time complexity which is kinda… unfavorable.

Are there any better methods of obtaining a random party? I’ve already considered switching the ListOfParties to a simple array rather than a dictionary, but I’m using the dictionary’s properties for a quicker search algorithm that I’m using a lot.

local Array = {}

Array[math.random(1, #Array)]

Or something. Point is that you want to get a random number based on the number of indices in your Array and use that as an index. That’s provided you’re using numerical indices. Can’t remember how it’s done for any other indice.

1 Like

You can’t get the length of a dictionary without using a linear time complexity loop through all non-nil indices, so that also won’t really help :confused:

put them all in an array then choose a random index out of that array

1 Like

I understand your search for better methodology, but there is no built-in function for this.
The time complexity for your current method is of no significance, considering the situation

Just use what you have at the moment

Buut if you’re a hack, you could maintain a list of parties like the one created in part.GetListOfParties (instead of creating a new one every time)
You would add/remove from it when needed

1 Like

Alright, thanks!

Why not change the way you’re setting your indices or filling your table, then? You’re using tables as keys and just setting their values to true. You can probably strive towards solving your problem by changing your set up. For example: why do you need tables to be keys with true values?

It’s more for my method of removing parties with ease.

local function RemoveParty(partyObject)
	if ListOfParties[partyObject] then
		ListOfParties[partyObject] = nil

People will be leaving parties a lot (more than I’ll be searching for a random party in a list), and I’d rather use a quick search rather than looping through every single party in the ListOfParties array.

Changing the way you index doesn’t imply I was offering a workaround that involved looping through parties. I meant what I said fairly literally. Change the way you set indices. I’m also not sure what’s wrong with your current “unfavourable” method - there’s literally nothing wrong with it. Mind explaining?

Otherwise, there’s not really much else I can do to help you. There is no real built-in way to attain a random indice without either looping through your dictionary or using numerical indices.

local randomIndex, count = math.random(1, table.length(table)), 1
for index, value in pairs(table) do
      count = (count + 1);
      if (count >= randomIndex)) then
            -- do thing

-- table.length would be a function like this:
function table.length(table)
      local count = 0
      for i,v in pairs(table) do
             count = (count + 1);
       return count
1 Like

The reason I said my previous method was unfavorable was because I didn’t like the idea of having to loop through every single party every time I wanted to get an array.