Remove pair duplicates from array of values

Question

The problem

In lua I have an array of values (specifically - x and y position values) from which I would like to remove duplicate pairs. The array looks as follows:

array = {x1, y1, x2, y2, x3, y3, ... , xn, yn}

where n is the number of corrdinates pairs. So whether a value is an x coordinate or y coordinate is determined solely by its position in the array. A duplicate is defined as xa == xb and ya == yb. So for example if x1 == x2 and y1 == y2 I would like to remove x1 and y1 or (not both) x2 and y2 from the array.

Questions

1. How could one remove duplicates from such array?
2. Could it be done without subdividing the array?
3. Bonus: In more general case what if array contained 3 (or even more) variables, that is array = {x1, y1, z1, x2, y2, z2, ... , xn, yn, zn}

Numeric example

If an array of values is given:

array = {1, 1, 2, 1, 1, 1, 2, 1}

then removing duplicates should result in an array:

array = {1, 1, 2, 1}

Answer 1

This one also covers the 3rd point about being able to handle any size of grouped variables. All you have to do is give the grouping size you want to assume (default is 2)

function remove_dups(t,size)
  size = size or 2            --default group size is 2
  assert(#t % size == 0,'Table size is not a multiple of "size"')
  local temp = {}
  local key
  local i = 1
  while i <= #t do
    key = t[i]
    for count = 1, size-1 do
      key = key .. '|' .. t[i+count]
    end
    if temp[key] then
      for count = 1, size do
        table.remove(t,i)
      end
    else
      temp[key] = true
      i = i + size
    end
  end
  return t
end

-- Test the above --

function pa(t,size) -- print array grouped by size
  size = size or 2
  for i,v in ipairs(t) do io.write(v,i ~= #t and i % size == 0 and ', ' or ' ') end
  print()
end

array = {1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 1, 1, 1, 3, 2, 1, 1}

print 'Original'
pa(array)

print 'Dups removed'
pa(remove_dups(array))

Answer 2

You can use a table of tables to track duplicates. The outer table is indexed by the x component, the inner table is indexed by the y component. Then you simply iterate over the original array with an increment of 2, and only copy elements over to the result if they are not tracked as duplicates.

Answer 3

If the order of pairs is not important, then you can do so:

local Coords = {1, 1, 2, 1, 1, 1, 2, 1}
local Result,  interim = {}, {}

for i=1,#Coords,2 do
      if Coords[i+1]  then
           local PointSignature = Coords[i] .. '_' .. Coords[i+1] 
           interim[PointSignature] = true
      end
end
for k,v in pairs(interim) do
     local x, y = k:match("(.+)_(.+)")
     Result[#Result+1] = x
     Result[#Result+1] = y
end
for i=1, #Result do
  print(Result[i])
end

The result comes out slightly sorted.

different version, the result in original order:

local Coords = {1, 1, 22, 1, 1, 1, 2, 1, 11, 11, 22, 1}
local Result,  interim = {}, {}

for i=1,#Coords,2 do
      if Coords[i+1]  then
           local PointSignature = Coords[i] .. '_' .. Coords[i+1] 
           if not interim[PointSignature] then
                 Result[#Result+1] = Coords[i]
                 Result[#Result+1] = Coords[i+1] 
                 interim[PointSignature] = true
           end
      end
end

Answer 4

array = {x1, y1, x2, y2, x3, y3, ... , xn, yn}

You can convert it to the map and back to list:

local map = {}
for i = 1, #array-1, 2 do
    local x, y = array[i], array[i+1]
    if not map[x] then map[x] = {} end
    map[x][y] = true
end

local uniqueList = {}
for x, ys in pairs (map) do
    for y, b in pairs (ys) do
        table.insert(uniqueList, x)
        table.insert(uniqueList, y)
    end
end