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

How could one remove duplicates from such array?
Could it be done without subdividing the array?
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}

ComicSansMS · Accepted Answer · 2017-03-20 16:39:50Z

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.

answered Mar 20, 2017 at 16:39

ComicSansMS

55.9k15 gold badges166 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

tonypdmtr · Accepted Answer · 2017-03-21 13:17:38Z

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))

Mike V. · Accepted Answer · 2017-03-20 17:36:43Z

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

darkfrei · Accepted Answer · 2022-05-01 09:54:28Z

0

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

answered May 1, 2022 at 9:54

darkfrei

6184 silver badges11 bronze badges

Collectives™ on Stack Overflow

Remove pair duplicates from array of values

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related