Home > Community > Forums > Custom IC SKILL > Remove duplicates from a list

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

 Remove duplicates from a list 

Last post Tue, Nov 27 2012 10:58 PM by pcbnagaraj. 8 replies.
Started by tweeks 14 May 2012 02:06 PM. Topic has 8 replies and 2871 views
Page 1 of 1 (9 items)
Sort Posts:
  • Mon, May 14 2012 2:06 PM

    • tweeks
    • Top 75 Contributor
    • Joined on Fri, Jun 3 2011
    • Irvine, CA
    • Posts 102
    • Points 1,590
    Remove duplicates from a list Reply

    Just wanted to share my solution to this common problem.

    (defun nub (l "l")
      (let ((table (makeTable "" nil)))
        (foreach e l table[e] = t)
        table->?))
    

    Output:

    (nub (parseString "Banana Rama" "")) => ("a" "m" "n" "R" "B" " ")
    

    This assumes order doesn't matter. If order does matter (and efficiency doesn't...), you could use this O(n^2) version, which is a literal translation of the one in the Haskell Data.List library:

    (defun nub (l "l")
      (defun _nub (xs ls "ll")
        (unless (null xs)
          (destructuringBind (x @rest xs) xs
            (if (member x ls)
                (_nub xs ls)
              (cons x (_nub xs (cons x ls)))))))
      (_nub l nil))
    

    Output:

    (nub (parseString "Banana Rama" "")) => ("B" "a" "n" " " "R" "m")
    

    If you want to preserve order and get O(n) performance, you could modify the last version to use a table instead of a list:

    (defun nub (l "l")
      (defun _nub (xs ls "lo")
        (unless (null xs)
          (destructuringBind (x @rest xs) xs
            (if (ls[x])
                (_nub xs ls)
              (cons x (_nub xs (ls[x] = t && ls)))))))
      (_nub l (makeTable "" nil)))
    

    Output:

    (nub (parseString "Banana Rama" "")) => ("B" "a" "n" " " "R" "m")
    
    • Post Points: 20
  • Mon, May 14 2012 4:54 PM

    • markbeck
    • Top 150 Contributor
    • Joined on Thu, Jun 30 2011
    • Beaverton, OR
    • Posts 45
    • Points 1,355
    Re: Remove duplicates from a list Reply

    Nice writeup.

    I was once shown a varient of this method to remove duplicates

    (defun nub (l_list)
      (let ( (l_unique (list nil)) g_first)    
        (while l_list            
          g_first = (car l_list)
          (tconc l_unique g_first)
          l_list=(remove g_first l_list)
        ) ; while
        (car l_unique)
      ); let
    ); defun    

    (nub (parseString "Banana Rama" ""))
    => ("B" "a" "n" " " "R"  "m")

    The nice thing about this method is that it works for large lists and preserves order (whereas your table version gave me a stack overflow with a large list).  That said, the first method you outlined has about 4X the performance of my method.  So if order is not important, your first method is the best way I've seen. Nice work!

    Mark

    • Post Points: 20
  • Mon, May 14 2012 7:10 PM

    • Adhil
    • Top 100 Contributor
    • Joined on Fri, Apr 15 2011
    • Singapore, 00-SG
    • Posts 61
    • Points 1,245
    Re: Remove duplicates from a list Reply

    i made a procedure to remove duplicates from an actual list.

    procedure(filterRepeatedLayers(aList)  

    println(aList)
    if(car(aList) != cadr(aList) && aList != nil then
    ncons(car(aList))
    filterRepeatedLayers(copy(cdr(aList)))

    else if(car(aList) == cadr(aList) && aList != nil then
    ncons(cadr(aList))
    filterRepeatedLayers(copy(cddr(aList)))
       )
      )
     )

    however, when i invoke

    a = filterRepeatedLayers('("M1" "M2" "M2"))

    i get a = nil instead of a = '("M1" "M2")

    • Post Points: 20
  • Mon, May 14 2012 7:16 PM

    • eDave
    • Top 10 Contributor
    • Joined on Sun, Jul 13 2008
    • Christchurch, 00-NZ
    • Posts 707
    • Points 15,395
    Re: Remove duplicates from a list Reply
    In the Allegro world we have a newish command called "unique". Is this available to you?
    Dave Elder, Tait Communications
    • Post Points: 35
  • Mon, May 14 2012 7:19 PM

    • Adhil
    • Top 100 Contributor
    • Joined on Fri, Apr 15 2011
    • Singapore, 00-SG
    • Posts 61
    • Points 1,245
    Re: Remove duplicates from a list Reply

    i checked the manuals, and it doesn't have this function

    • Post Points: 5
  • Tue, Nov 27 2012 4:24 AM

    • pcbnagaraj
    • Top 150 Contributor
    • Joined on Mon, Dec 5 2011
    • bangalore, Karnataka
    • Posts 55
    • Points 1,130
    Re: Remove duplicates from a list Reply

     Hi Dave,

     I am not finding this command 'unique' in skill language reference manual.

    Is this removed?

    I need this in Allegro.

    Thanks,

    Nagaraj.

    • Post Points: 35
  • Tue, Nov 27 2012 4:50 AM

    Re: Remove duplicates from a list Reply

    I can't answer about what's in Allegro, but it's easy to implement your own as shown in the original thread. Another implementation 

    (defun MyUnique (lst)
      (let ((seen (makeTable 'seen nil)))
        (setof elem lst
          (unless (arrayref seen elem)
            (setarray seen elem t)
          )
        )
      )
    )

    This preserves the order, isn't recursive so it's probably a little faster than final nub implementation (I didn't profile it, so take that with a pinch of salt). For the hard-of-LISP, it could be written:

    procedure(MyUnique(lst)
      let(((seen makeTable('seen nil)))
        setof(elem lst
          unless(seen[elem]
            seen[elem]=t
          )
        )
      )
    )

    So it's easy enough to write yourself!

    Andrew.

    • Post Points: 5
  • Tue, Nov 27 2012 10:56 AM

    • eDave
    • Top 10 Contributor
    • Joined on Sun, Jul 13 2008
    • Christchurch, 00-NZ
    • Posts 707
    • Points 15,395
    Re: Remove duplicates from a list Reply
    It's undocumented. Give it a try.
    Dave Elder, Tait Communications
    • Post Points: 20
  • Tue, Nov 27 2012 10:58 PM

    • pcbnagaraj
    • Top 150 Contributor
    • Joined on Mon, Dec 5 2011
    • bangalore, Karnataka
    • Posts 55
    • Points 1,130
    Re: Remove duplicates from a list Reply

     It worked!!.

    Thanks,

    Nagaraj.

    • Post Points: 5
Page 1 of 1 (9 items)
Sort Posts:
Started by tweeks at 14 May 2012 02:06 PM. Topic has 8 replies.