CODEWITHSUNDEEP
vectorlua
user2661380
user2661380

Reputation: 11

Taking common elements from 2 vectors in Lua

I have 2 vectors, lets say v1 = (a,b,c,d,e) and v2 = (e,h,t,b,w) and I want to get a third vector containing the common elements of v1 and v2, in this case v3 = (e,b)

I've seen this is already asked in c++, but I cant see it for Lua.

Upvotes: 1

Views: 1062

Answers (4)

Dmitry Ledentsov
Dmitry Ledentsov

Reputation: 3660

Just in case you want to intersect larger vectors (arrays/sets), here's an attempt at an unmeasured premature optimization

local v1 = {1,2,4,8,16}
local v2 = {2,3,4,5}

local function intersect(t1,t2)

        local function make_lookup(t)
            local res={}
            for _,v in ipairs(t) do
                res[v]=true
            end
            return res
        end

        local smaller,larger
        if (#t1>#t2) then
            larger=t1
            smaller=t2
        else
            larger=t2
            smaller=t1
        end

        local lookup=make_lookup(smaller)

        local res={}
        for _,v in ipairs(larger) do
            if lookup[v] then
                res[#res+1]=v
            end
        end
        return res
end

local v1v2_intersected=intersect(v1,v2)

The internal lookup table is made of the smaller array table of the two. In "production" you would perhaps also want to check, whether you're dealing with correct input values

Upvotes: 1

Mud
Mud

Reputation: 29000

You can take a pass through v1 to build a lookup table for its values, then one pass through v2 to find common values and add them to an output list:

function findcommon(a1, a2)
    local in_a1 = {} -- lookup table for a1's values
    for k,v in pairs(a1) do in_a1[v] = true end

    local common = {}
    local n = 0
    for k,v in pairs(a2) do 
        if in_a1[v] then 
            in_a1[v] = false
            n = n + 1
            common[n] = v
        end
    end

    return common
end

Given your example:

v1 = {'a','b','c','d','e'} 
v2 = {'e','h','t','b','w'}
common = findcommon(v1,v2)

print('('..table.concat(common,',')..')')  --> (e,b)

Upvotes: 2

lhf
lhf

Reputation: 72342

Unlike Yu Hao's solution, the code below runs in linear time, but it does need extra memory, unless you can live with v3 instead of insisting on v4. The time difference will probably only be noticeable for large input vectors, though.

local v1={1,2,4,8,16}
local v2={2,3,4,5}
local v3={}
for k,v in ipairs(v1) do v3[v]=false end
for k,v in ipairs(v2) do if v3[v]==false then v3[v]=true end end
for k,v in  pairs(v3) do if v3[k]==false then v3[k]=nil end end
local v4={}
local n=0
for k,v in  pairs(v3) do n=n+1; v4[n]=k end
for k,v in ipairs(v4) do print(k,v) end

Upvotes: 1

Yu Hao
Yu Hao

Reputation: 122433

I assume when saying vectors, you mean v1 and v2 are both array-like tables, like this:

local v1 = {1,2,4,8,16}
local v2 = {2,3,4,5}

Then you can do it like this:

local v3 = {}

for k1,v1 in pairs(v1) do
    for k2,v2 in pairs(v2) do
        if v1 == v2 then
            v3[#v3 + 1] = v1
        end
    end
end

Upvotes: 3

Related Questions