Author Topic: {Resolved}How to find the duplicate items in the list  (Read 13405 times)

0 Members and 1 Guest are viewing this topic.

xiaxiang

  • Guest
{Resolved}How to find the duplicate items in the list
« on: January 14, 2015, 04:56:07 AM »
Hi all
The Challenge today is that How to find the duplicate items(with fuzz) in my given list.
Maybe too simply?
Code: [Select]
(foo '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 )0.05)
;0.05 is fuzz
-->((1.19 1.2 1.21 1.22 1.23 1.25))
;;;1.25-1.19=0.6 > 0.5!
**********************************************************************************
Yes it's too simple for you masters.
**********************************************************************************
You can goto another topic
How to replace the duplicate items in the list
http://www.theswamp.org/index.php?topic=48652
Thanks!   :-D
« Last Edit: January 19, 2015, 09:59:18 PM by xiaxiang »

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: {Challenge}How to find the duplicate items in the list
« Reply #1 on: January 14, 2015, 06:01:41 AM »
Quickly written:

Recursive:
Code - Auto/Visual Lisp: [Select]
  1. (defun listdupesfuzz ( lst fuz / itm tmp )
  2.     (if (setq itm (car lst))
  3.         (progn
  4.             (setq lst (vl-remove-if '(lambda ( x ) (if (equal x itm fuz) (setq tmp (cons x tmp)))) (cdr lst)))
  5.             (if tmp
  6.                 (cons (cons itm (reverse tmp)) (listdupesfuzz lst fuz))
  7.                 (listdupesfuzz lst fuz)
  8.             )
  9.         )
  10.     )
  11. )

Iterative:
Code - Auto/Visual Lisp: [Select]
  1. (defun listdupesfuzz ( lst fuz / itm rtn tmp )
  2.     (while lst
  3.         (setq itm (car lst)
  4.               lst (vl-remove-if '(lambda ( x ) (if (equal x itm fuz) (setq tmp (cons x tmp)))) (cdr lst))
  5.         )
  6.         (if tmp
  7.             (setq rtn (cons (cons itm (reverse tmp)) rtn)
  8.                   tmp nil
  9.             )
  10.         )
  11.     )
  12.     (reverse rtn)
  13. )
Code - Auto/Visual Lisp: [Select]
  1. _$ (listdupesfuzz '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.3 ) 0.05)
  2. ((1.19 1.2 1.21 1.22 1.23))

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Challenge}How to find the duplicate items in the list
« Reply #2 on: January 14, 2015, 06:11:08 AM »
Another one of mine:

Code - Auto/Visual Lisp: [Select]
  1. (defun List:DuplicatesEq  (L fuzz / len result)
  2.   (setq len (1- (length L)))
  3.   (vl-remove-if
  4.     (function
  5.       (lambda (item)
  6.         (= (length (vl-remove-if (function (lambda (test) (equal test item fuzz))) L)) len)))
  7.     L))

Code: [Select]
_$ (List:DuplicatesEq '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.3 ) 0.05)
(1.19 1.2 1.21 1.22 1.23)
« Last Edit: January 14, 2015, 06:14:55 AM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: {Challenge}How to find the duplicate items in the list
« Reply #3 on: January 14, 2015, 06:20:20 AM »
Nice solution Irneb  :-)

@xiaxiang, how should the output be structured?

Code - Auto/Visual Lisp: [Select]
  1. _$ (listdupesfuzz '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
  2. ((1.19 1.2 1.21 1.22 1.23) (5.0 5.01 4.98))
  3.  
  4. _$ (List:DuplicatesEq '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
  5. (1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23)

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Challenge}How to find the duplicate items in the list
« Reply #4 on: January 14, 2015, 07:51:42 AM »
Nice solution Irneb  :-)
Thanks. Though yours is a lot more optimal (especially for long lists with lots of duplication).
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

VovKa

  • Water Moccasin
  • Posts: 1626
  • Ukraine
Re: {Challenge}How to find the duplicate items in the list
« Reply #5 on: January 14, 2015, 09:07:56 AM »
who is right?  :police:
Code: [Select]
(listdupesfuzz '(1.00 1.03 1.06) 0.05)
(List:DuplicatesEq '(1.00 1.03 1.06) 0.05)

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: {Challenge}How to find the duplicate items in the list
« Reply #6 on: January 14, 2015, 09:40:15 AM »
who is right?  :police:
Code: [Select]
(listdupesfuzz '(1.00 1.03 1.06) 0.05)
(List:DuplicatesEq '(1.00 1.03 1.06) 0.05)

I would assert that the items in each group should not vary by more than the given tolerance, e.g.:
Code - Auto/Visual Lisp: [Select]
  1. _$ (listdupesfuzz '(1.00 1.03 1.06 1.09 1.12 1.15 1.18 1.21 1.24) 0.05)
  2. ((1.0 1.03) (1.06 1.09) (1.12 1.15) (1.18 1.21))

But this requires that the list is sorted before processing otherwise the grouping will be ambiguous...



irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Challenge}How to find the duplicate items in the list
« Reply #7 on: January 14, 2015, 10:15:35 AM »
But this requires that the list is sorted before processing otherwise the grouping will be ambiguous...
Well if the list is sorted (if such assumption can be made) then the algorithm could be optimized a lot more - seeing as the search for duplicates only need to continue past current until a new non-duplicate is found.

But I'm not sure about the "groupings". They're pretty arbitrary IMO. E.g. say the list consists of '(1.00 1.03 1.06 1.09 2.06 2.09 3.02). Is the grouping simply relating to the first item found or all groupings? I.e. should the result (with fuzz factor of 0.05) only be:
Code: [Select]
((1.00 1.03) (1.06 1.09) (2.06 2.09))But then 1.03 should also group together with 1.06 (e.g.) shouldn't it? Not to mention shouldn't 2.09 and 3.02 also be grouped? But then a duplicate is repeated in the result.

IMO there's 2 alternative approaches to this:
Code: [Select]
; Option 1
((1.00 1.03) (1.03 1.06) (1.06 1.09) (2.06 2.09) (2.09 3.02))
; Option 2
((1.00 1.03 1.06 1.09) (2.06 2.09 3.02))
And as per the OP it seems option 2 is what's supposed to happen.

Though there's another ambiguous situation:
(UNIQUE_PAIRS '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.3 )0.05)
;0.1 is fuzz
-->((1.19 1.2 1.21 1.22 1.23))
[/code]
If the comment is to be believed then it's not as I thought. Since in such case 1.23 and 1.3 should also be considered duplicates, shouldn't they? Not to mention 1.0 and 1.1 (if 0.1 fuzz is considered inclusive).
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: {Challenge}How to find the duplicate items in the list
« Reply #8 on: January 14, 2015, 10:30:16 AM »
test 1
Code: [Select]
(setq l '(1.00 1.03 1.06 1.09 1.12 1.15 1.18 1.21 1.24) a 0.05)
(mapcar '(lambda (c) (vl-remove-if-not '(lambda (b) (equal b c a)) l)) l)
=>> ((1.0 1.03) (1.0 1.03 1.06) (1.03 1.06 1.09) (1.06 1.09 1.12) (1.09 1.12 1.15) (1.12 1.15 1.18) (1.15 1.18 1.21) (1.18 1.21 1.24) (1.21 1.24))

test 2
Code: [Select]
(setq l '(1.00 1.03 1.06 1.09 1.12 1.15 1.18 1.21 1.24) a 0.05)
(defun f (l a)
  (if l
    (cons (vl-remove-if-not '(lambda (b) (equal (car l) b a)) l)
          (f (vl-remove-if '(lambda (b) (equal (car l) b a)) l) a)
    )
  )
)
(f l a)
=>> ((1.0 1.03) (1.06 1.09) (1.12 1.15) (1.18 1.21) (1.24))

xiaxiang

  • Guest
Re: {Challenge}How to find the duplicate items in the list
« Reply #9 on: January 14, 2015, 08:48:14 PM »
@xiaxiang, how should the output be structured?
Code - Auto/Visual Lisp: [Select]
  1. _$ (listdupesfuzz '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
  2. ((1.19 1.2 1.21 1.22 1.23) (5.0 5.01 4.98))
  3.  
  4. _$ (List:DuplicatesEq '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
  5. (1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23)
Sorry for late. I think the original list should be "re" grouped and output as nested list.
So
Code: [Select]
((1.19 1.2 1.21 1.22 1.23) (5.0 5.01 4.98))
This result is right.

xiaxiang

  • Guest
Re: {Challenge}How to find the duplicate items in the list
« Reply #10 on: January 14, 2015, 09:26:12 PM »
Quote
Though there's another ambiguous situation:

Quote from: xiaxiang on Today at 04:56:07 am
Code: [Select]
(UNIQUE_PAIRS '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.3 )0.05)
;0.1 is fuzz
-->((1.19 1.2 1.21 1.22 1.23))
If the comment is to be believed then it's not as I thought. Since in such case 1.23 and 1.3 should also be considered duplicates, shouldn't they? Not to mention 1.0 and 1.1 (if 0.1 fuzz is considered inclusive).
I must applogize for that the comment for those codes is wrong. The fuzz is 0.05.
I've modified the topic.

Quote
Well if the list is sorted (if such assumption can be made) then the algorithm could be optimized a lot more - seeing as the search for duplicates only need to continue past current until a new non-duplicate is found.
Yes the list is sorted.

Quote
IMO there's 2 alternative approaches to this:

Code: [Select]
; Option 1
((1.00 1.03) (1.03 1.06) (1.06 1.09) (2.06 2.09) (2.09 3.02))
; Option 2
((1.00 1.03 1.06 1.09) (2.06 2.09 3.02))
And as per the OP it seems option 2 is what's supposed to happen.
The Option 2 is the result what I required.

xiaxiang

  • Guest
Re: {Challenge}How to find the duplicate items in the list
« Reply #11 on: January 14, 2015, 09:50:03 PM »
Noted that:
Code: [Select]
;;Lee mac
命令: (listdupesfuzz '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 ) 0.05)
((1.19 1.2 1.21 1.22 1.23))

Code: [Select]
;;Irneb
命令: (LIST:DUPLICATESEQ '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 ) 0.05)
(1.19 1.2 1.21 1.22 1.23 1.25)

For Lee's codes the grouping is only relating to the first item in every once Iteration.
Quote
(defun listdupesfuzz ( lst fuz / itm tmp ) 
  (if (setq itm (car lst))       
   (progn           
      (setq lst
         (vl-remove-if '(lambda ( x )
            (if (equal x itm fuz)
               (setq tmp (cons x tmp))
            )
            ) (cdr lst)
         )
      )           
      (if tmp               
         (cons (cons itm (reverse tmp)) (listdupesfuzz lst fuz))             
         (listdupesfuzz lst fuz)           
      )       
   )   
   )
)

I've got the same result with your "Unique with Fuzz" function,Lee.
Code: [Select]
命令: (LM:UniqueFuzz '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 ) 0.05)
(1.0 1.1 1.19 1.25 1.3)
So the judgment  which was from the first item to the end of the list is not suit for my condition.
 :-)
« Last Edit: January 14, 2015, 10:04:11 PM by xiaxiang »

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: {Challenge}How to find and replace the duplicate items in the list
« Reply #12 on: January 15, 2015, 12:18:43 AM »
xiaxiang

For the sanity of anyone trying to follow this thread perhaps it would be better to start a new thread with the revised requirements rather than just change the first post.
Have a little respect for those who come along later.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Challenge}How to find and replace the duplicate items in the list
« Reply #13 on: January 15, 2015, 12:32:01 AM »
@xiaxiang, how should the output be structured?
Code - Auto/Visual Lisp: [Select]
  1. _$ (listdupesfuzz '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
  2. ((1.19 1.2 1.21 1.22 1.23) (5.0 5.01 4.98))
  3.  
  4. _$ (List:DuplicatesEq '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
  5. (1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23)
Sorry for late. I think the original list should be "re" grouped and output as nested list.
So
Code: [Select]
((1.19 1.2 1.21 1.22 1.23) (5.0 5.01 4.98))
This result is right.
OK, here's an iterative + imperative attempt by first sorting the list:
Code - Auto/Visual Lisp: [Select]
  1. (defun List:DuplicatesEq2  (L fuzz / item group result)
  2.   (setq L (vl-sort L '<=))
  3.   (while (setq item (car L))
  4.     (setq L (cdr L))
  5.     (while (and L (equal item (car L) fuzz))
  6.       (setq group (cons item group)
  7.             item  (car L)
  8.             L     (cdr L)))
  9.     (if group
  10.       (setq result (cons (reverse (cons item group)) result)
  11.             group  nil)))
  12.   (reverse result))
Seems to work
Code: [Select]
_$ (List:DuplicatesEq2 '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 ) 0.05)
((1.19 1.2 1.21 1.22 1.23 1.25))
_$ (List:DuplicatesEq2 '(1.0 1.1 1.19 5.0 5.01 4.98 1.2 1.21 1.22 1.23 1.3) 0.05)
((1.19 1.2 1.21 1.22 1.23) (4.98 5.0 5.01))
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

xiaxiang

  • Guest
Re: {Challenge}How to find and replace the duplicate items in the list
« Reply #14 on: January 15, 2015, 02:07:54 AM »
xiaxiang

For the sanity of anyone trying to follow this thread perhaps it would be better to start a new thread with the revised requirements rather than just change the first post.
Have a little respect for those who come along later.

OK.Turn back.
 8-)
« Last Edit: January 15, 2015, 06:28:42 AM by xiaxiang »