Принимая общие элементы из 2 векторов в Lua

Question

У меня есть 2 векторов, позволяет сказать v1 = (a,b,c,d,e) и v2 = (e,h,t,b,w), и я хочу, чтобы получить третий вектор, содержащий общие элементы v1 и v2, в этом случае v3 = (e,b)

Я видел это уже задано в C++, но я не вижу его для Lua.

Answer 1

Я предполагаю, что когда говорят векторы, вы имеете в виду v1 и v2 оба массива, как таблицы, например:

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

Тогда вы можете сделать это следующим образом:

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 

Answer 2

В отличие от Ю. Хао решение, приведенный ниже код работает в линейном времени, но ему нужна дополнительная память, если вы не можете жить с v3, а не настаивать на v4. Разница во времени, вероятно, будет заметна только для больших входных векторов.

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 

Answer 3

Вы можете взять проход через v1 построить таблицу поиска для его значений, то за один проход через v2 найти общие ценности и добавить их в список вывода:

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 

Учитывая ваш пример :

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

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

Answer 4

Только в случае, если вы хотите, чтобы пересекать большие векторы (массивы/наборы), вот попытка на неизмеренной преждевременной оптимизации

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) 

Внутренняя таблица поиска выполнена из таблицы меньших массивов двух. В «производстве» вы, возможно, также захотите проверить, имеете ли вы правильные входные значения