Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
1

How do I check if any of the values in a table are the same?

Asked by
Validark 1580 Snack Break Moderation Voter
10 years ago

All values in my table are Numbers. How can I check to see if any of the values in the table are the same?

2 answers

Log in to vote
1
Answered by
BlueTaslem 18071 Moderation Voter Administrator Community Moderator Super Administrator
10 years ago

There are more or less 3 different ways to do this.

Each basically consider each element and check whether or not that element has been seen before / is in the table multiple times (by looking for it).


The most straightforward way is to check all of the remaining elements and compare them to the current one. For example,

for i = 1, #list do
    local element = list[i]
    -- Search for `element` in the
    -- remainder (from i + 1 on) of the list
    for j = i + 1, #list do
        -- For each element in the remainder of the list...
        if list[j] == element then
            -- list[i] and list[j] are the same!
        end
    end
end

If there are N elements in the table, then this takes approximately N * N / 2 checks (a quadratic time). This can be very slow if you have a large list.


We can go faster, though! If we sort the list (if somehow the data can be sorted -- this can no longer be done in general), then we can just compare adjacent indices.

That would make this take approximately N * log(n) + N checks, which is significantly better than the quadratic implementation above.

One efficiency note: If you cannot modify the original table for some reason, you will first have to copy it, taking N extra memory (which the 1st implementation doesn't have a problem with). Of course, Lua is not usually a language where you have to care about memory consumption.

For numbers (or strings), we can use the default table.sort; for other data types, we would have to define our own.

-- First, sort it.
table.sort( list )

for i = 1, #list - 1 do
    -- If they are the same, then, since they're sorted
    -- they will be right next to each other.
    -- So we just compare adjacent values.
    if list[i] == list[i + 1] then
        -- list[i] and list[i + 1] are the same!
    end
end

Finally, we can go much faster! In fact, just N time, by using a hashtable. This, however, takes significantly more memory -- though, again, Lua isn't a context where memory usage is very important.

-- Use a hashtable:
haveSeen = {}

for i = 1, #list do
    local element = list[i]
    -- Check whether or not any previous place has
    -- recorded `element` into `haveSeen`
    if not haveSeen[element] then
        -- haveSeen[element] is empty
        haveSeen[element] = i
    else
        -- haveSeen[element] is NOT empty --
        -- the element has already been seen
        -- list[ haveSeen[element] ] and list[i] are the same!
    end
Ad
Log in to vote
0
Answered by 10 years ago

This should work, just tested.

nums = {1,2,3,4,4} --Example, replace this with your table

function TableCheck(tab,val,position) --Create a function with the input arguments
    for i = 1, #tab do --Numeric for loop through 1 and the number of items in the table.
        if tab[i] == val and position ~= i then --Makes sure tab[i] equals the value and that the position of the value is not the same as i.
            return true --Returns true and stops the function
        end
    end
    return false --Returns false if nothing is found.
end

for i = 1, #nums do --Numeric for loop through 1 and the number of items in the nums table.
    local result = TableCheck(nums,nums[i],i) --Calls function with the arguments being the nums table, the value in the position of i in the nums table and i itself.
    if result == true then --If the function returns true then.
        print("Match found at table position " .. i) --Prints that a match was found at i.
        break --Breaks loop.
    else --If the function returns false then.
        print("Match not found at table position " .. i) --Prints that a match wasn't found at i, and keeps searching if i isn't equal to #nums.
    end
end

NOTE: You can get rid of the break below the match found print if you want to keep searching after finding a duplicate. You can also edit what happens after the result returns true or false, for example, you can make it remove the duplicate value when it's found.

0
This is quadratic - very slow. BlueTaslem 18071 — 10y

Answer this question