Author Topic: {Resolved}How to find the duplicate items in the list  (Read 13403 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 »

xiaxiang

  • Guest
Re: {Challenge}How to find the duplicate items in the list
« Reply #15 on: January 15, 2015, 04:34:51 AM »
Quote
OK, here's an iterative + imperative attempt by first sorting the list:
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))
Minor error
Code: [Select]
(List:DuplicatesEq2 '(1.0 1.1 1.19 1.2 1.2 1.21 1.22 1.23 1.25 1.3 2.0 2.1 2.19 2.2 2.2 2.21 2.22 2.23 2.25 2.3) 0.05)
-->((1.19 1.2 1.2 1.21 1.22 1.23 1.25) (2.19 2.2 2.2 2.21 2.22 2.23 2.25 2.3))
« Last Edit: January 15, 2015, 04:51:30 AM by xiaxiang »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: {Challenge}How to find the duplicate items in the list
« Reply #16 on: January 15, 2015, 04:40:37 AM »
Minor error
Code: [Select]
(List:DuplicatesEq2 '(1.0 1.1 1.19 1.2 1.2 1.21 1.22 1.23 1.25 1.3 2.0 2.1 2.19 2.2 2.2 2.21 2.22 2.23 2.25 2.3) 0.05)
-->((1.19 1.2 1.2 1.21 1.22 1.23 1.25) (2.19 2.2 2.2 2.21 2.22 2.23 2.25 [color=red]2.3[/color]))

On my comp:
Code: [Select]
  (equal 2.25 2.3 0.05);=>> T
  (equal 2.15 2.2 0.05);=>> nil
  (equal 2.05 2.1 0.05);=>> nil
:-(

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: {Challenge}How to find the duplicate items in the list
« Reply #17 on: January 15, 2015, 04:43:26 AM »
my version for sorted list:
Code - Auto/Visual Lisp: [Select]
  1. (defun f (l a b)
  2.   (cond ((and (not l) (cdr b)) (list (reverse b)))
  3.         ((not l) nil)
  4.         ((equal (car l) (car b) a) (f (cdr l) a (cons (car l) b)))
  5.         ((cdr b) (cons (reverse b) (f l a nil)))
  6.         ((f (cdr l) a (list (car l))))
  7.   )
  8. )
test:
Code - Auto/Visual Lisp: [Select]
  1. (f (vl-sort l '<=) a nil)

xiaxiang

  • Guest
Re: {Challenge}How to find the duplicate items in the list
« Reply #18 on: January 15, 2015, 04:55:33 AM »
my version for sorted list:
Code - Auto/Visual Lisp: [Select]
  1. (defun f (l a b)
  2.   (cond ((and (not l) (cdr b)) (list (reverse b)))
  3.         ((not l) nil)
  4.         ((equal (car l) (car b) a) (f (cdr l) a (cons (car l) b)))
  5.         ((cdr b) (cons (reverse b) (f l a nil)))
  6.         ((f (cdr l) a (list (car l))))
  7.   )
  8. )
test:
Code - Auto/Visual Lisp: [Select]
  1. (f (vl-sort l '<=) a nil)

What is "a" and "b"? :-o

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1569
  • Moscow (Russia)
Re: {Challenge}How to find the duplicate items in the list
« Reply #19 on: January 15, 2015, 05:03:37 AM »
What is "a" and "b"? :-o

Code: [Select]
(f (vl-sort '(1.0 1.1 1.19 1.2 1.2 1.21 1.22 1.23 1.25 1.3 2.0 2.1 2.19 2.2 2.2 2.21 2.22 2.23 2.25 2.3)  '<=) 0.05 nil)

VovKa

  • Water Moccasin
  • Posts: 1626
  • Ukraine
Re: {Challenge}How to find the duplicate items in the list
« Reply #20 on: January 15, 2015, 05:49:00 AM »
On my comp:
Code: [Select]
  (equal 2.25 2.3 0.05);=>> T
  (equal 2.15 2.2 0.05);=>> nil
  (equal 2.05 2.1 0.05);=>> nil
:-(
but
Quote
(equal 2.25 (+ 2.25 0.05) 0.05);=>> T
(equal 2.15 (+ 2.15 0.05) 0.05);=>> T
(equal 2.05 (+ 2.05 0.05) 0.05);=>> T
damn nice surprise from autodesk programmers :)

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Challenge}How to find the duplicate items in the list
« Reply #21 on: January 15, 2015, 06:05:00 AM »
Sorry for the intrusion, but there is something I do not understand. If we, for example, stating that this function is reliable:
Code: [Select]
;; Unique with Fuzz  -  Lee Mac
;; Returns a list with all elements considered duplicate to
;; a given tolerance removed.
(defun LM:UniqueFuzz ( l f / x r )
    (while l
        (setq x (car l)
              l (vl-remove-if (function (lambda ( y ) (equal x y f))) (cdr l))
              r (cons x r)
        )
    )
    (reverse r)
)
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: (1.2 1.21 1.22 1.23) are duplicates? This is the required result?
Code: [Select]
; 20150114 - 1.00 - only for test
(defun ALE_List_FindDupesFuzz (In_Lst FuzFac / OutLst TmpLst NthVal Countr)
    (setq OutLst (list (car In_Lst)) In_Lst (cdr In_Lst))
    (foreach ForElm In_Lst
      (if (vl-position ForElm OutLst)
        OutLst
        (progn
          (setq Countr 0)
          (while (and Countr (setq NthVal (nth Countr OutLst)))
            (if (equal ForElm NthVal FuzFac)
              (setq Countr nil)
              (setq Countr (1+ Countr))
            )
          )
          (if NthVal
            (setq TmpLst (cons ForElm TmpLst))
            (setq OutLst (cons ForElm OutLst))
          )
        )
      )
    )
    (reverse TmpLst)
)
(ALE_List_FindDupesFuzz '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3) 0.05)
(1.2 1.21 1.22 1.23)

xiaxiang

  • Guest
Re: {Challenge}How to find the duplicate items in the list
« Reply #22 on: January 15, 2015, 06:38:37 AM »
(1.19 1.2 1.21 1.22 1.23 1.25) are duplicate items in my case.The next step we will determine which value that was considered as duplicate should be reserved.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Challenge}How to find the duplicate items in the list
« Reply #23 on: January 15, 2015, 09:10:48 AM »
(1.19 1.2 1.21 1.22 1.23 1.25) are duplicate items in my case.The next step we will determine which value that was considered as duplicate should be reserved.
Ok, this may be a foreach version:
(ALE_List_FindDupesFuzz '(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)
Code: [Select]
; 20150115 - 1.03
(defun ALE_List_FindDupesFuzz (In_Lst FuzFac / OutLst TmpLst NthVal Countr)
  (setq OutLst (list (car In_Lst)) In_Lst (cdr In_Lst))
  (foreach ForElm In_Lst
    (if (vl-position ForElm OutLst)
      (or (vl-position ForElm TmpLst) (setq TmpLst (cons ForElm TmpLst)))
      (progn
        (setq Countr 0)
        (while (and Countr (setq NthVal (nth Countr OutLst)))
          (if (equal ForElm NthVal FuzFac) (setq Countr nil) (setq Countr (1+ Countr)))
        )
        (or
          Countr
          (progn
            (or  (vl-position NthVal TmpLst) (setq TmpLst (cons NthVal TmpLst)))
            (and (vl-position NthVal OutLst) (setq OutLst (vl-remove NthVal OutLst)))
          )
        )
        (if NthVal (setq TmpLst (cons ForElm TmpLst)) (setq OutLst (cons ForElm OutLst)))
      )
    )
  )
  (reverse TmpLst)
)

ronjonp

  • Needs a day job
  • Posts: 7526
Re: {Challenge}How to find the duplicate items in the list
« Reply #24 on: January 15, 2015, 09:34:14 AM »
Minor error
Code: [Select]
(List:DuplicatesEq2 '(1.0 1.1 1.19 1.2 1.2 1.21 1.22 1.23 1.25 1.3 2.0 2.1 2.19 2.2 2.2 2.21 2.22 2.23 2.25 2.3) 0.05)
-->((1.19 1.2 1.2 1.21 1.22 1.23 1.25) (2.19 2.2 2.2 2.21 2.22 2.23 2.25 [color=red]2.3[/color]))

On my comp:
Code: [Select]
  (equal 2.25 2.3 0.05);=>> T
  (equal 2.15 2.2 0.05);=>> nil
  (equal 2.05 2.1 0.05);=>> nil
:(

Same here .. that's not cool.

Windows 11 x64 - AutoCAD /C3D 2023

Custom Build PC

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Challenge}How to find the duplicate items in the list
« Reply #25 on: January 15, 2015, 09:49:47 AM »
Minor error
Code: [Select]
(List:DuplicatesEq2 '(1.0 1.1 1.19 1.2 1.2 1.21 1.22 1.23 1.25 1.3 2.0 2.1 2.19 2.2 2.2 2.21 2.22 2.23 2.25 2.3) 0.05)
-->((1.19 1.2 1.2 1.21 1.22 1.23 1.25) (2.19 2.2 2.2 2.21 2.22 2.23 2.25 [color=red]2.3[/color]))

On my comp:
Code: [Select]
  (equal 2.25 2.3 0.05);=>> T
  (equal 2.15 2.2 0.05);=>> nil
  (equal 2.05 2.1 0.05);=>> nil
:(

Same here .. that's not cool.
Code: [Select]
(equal 2.25 2.30 0.05)                ;=>> T
(equal 2.25 2.30 0.049999999999999)   ;=>> nil
(equal 2.25 2.30 0.0499999999999999)  ;=>> T

(equal 2.15 2.2 0.05)                 ;=>> nil
(equal 2.15 2.2 0.0500000000000001)   ;=>> nil
(equal 2.15 2.2 0.050000000000001)    ;=>> T
:?

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Challenge}How to find the duplicate items in the list
« Reply #26 on: January 15, 2015, 11:59:35 AM »
there is still something wrong...
Code: [Select]
(setq fuzz 0.05   alist '(3.0 1.0 1.1 1.19 1.2 1.21 1.22 3.0 3.0 3.0 3.0 3))
=> (3.0 1.0 1.1 1.19 1.2 1.21 1.22 3.0 3.0 3.0 3.0 3)

(ALE_List_FindDupesFuzz alist fuzz)  >>>  r.1.03
=>  (1.19 1.2 1.21 1.22 3.0 3)

(f (vl-sort alist  '<=) fuzz nil)
=> ((1.19 1.2 1.21 1.22) (3 3.0 3.0 3.0 3.0 3.0))

(List:DuplicatesEq alist fuzz)
=> (3.0 1.19 1.2 1.21 1.22 3.0 3.0 3.0 3.0 3)

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: {Challenge}How to find the duplicate items in the list
« Reply #27 on: January 15, 2015, 01:10:37 PM »
On my comp:
Code: [Select]
  (equal 2.25 2.3 0.05);=>> T
  (equal 2.15 2.2 0.05);=>> nil
  (equal 2.05 2.1 0.05);=>> nil
:-(
but
Quote
(equal 2.25 (+ 2.25 0.05) 0.05);=>> T
(equal 2.15 (+ 2.15 0.05) 0.05);=>> T
(equal 2.05 (+ 2.05 0.05) 0.05);=>> T
damn nice surprise from autodesk programmers :)
This problem is caused by the fact that the 64 bit binary floating point format cannot be exactly matched to the decimal format.

xiaxiang

  • Guest
Re: {Resolved}How to find the duplicate items in the list
« Reply #28 on: January 19, 2015, 10:05:16 PM »
Thank you all !
 :-D :-D :-D

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Resolved}How to find the duplicate items in the list
« Reply #29 on: January 20, 2015, 08:47:01 AM »
IMHO, I think to properly terminate this thread need to distinguish three types of "ListDupesFuzz" functions:
Code: [Select]
=> fuzz 0.05

Remove Uniques: (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0)
              =>(1.2              1.21 1.22 1.23)

Show     Dupes: (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0)
             => (        1.19 1.2 1.21 1.22 1.23 1.25     3.0)

Show All Dupes: (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0)
             => (        1.19 1.2 1.21 1.22 1.23 1.25     3.0 3.0 3.0)

xiaxiang

  • Guest
Re: {Resolved}How to find the duplicate items in the list
« Reply #30 on: January 20, 2015, 08:23:50 PM »
IMHO, I think to properly terminate this thread need to distinguish three types of "ListDupesFuzz" functions:
Code: [Select]
=> fuzz 0.05

Remove Uniques: (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0)
              =>(1.2              1.21 1.22 1.23)

Sorry but I couldn't understand the function "Remove Uniques".
Why does it return (1.2 1.21 1.22 1.23)?
In fact I could not state the situation of the duplicate items exactly yet.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Resolved}How to find the duplicate items in the list
« Reply #31 on: January 21, 2015, 03:49:50 AM »
Sorry but I couldn't understand the function "Remove Uniques".
Why does it return (1.2 1.21 1.22 1.23)?
In fact I could not state the situation of the duplicate items exactly yet.
My apologies the exact result is:
Code: [Select]
Remove Uniques: (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0)
              =>(             1.2 1.21 1.22 1.23              3.0 3.0)
You can understand what I meant if you see my previous post: http://www.theswamp.org/index.php?topic=48646.msg537421#msg537421

Code: [Select]
(LM:UniqueFuzz ' (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0) 0.05)
                 (1.0 1.1 1.19  ^   ^    ^     ^  1.25 1.3 3.0  ^   ^ )
Remove Uniques:=>(             1.2 1.21 1.22 1.23              3.0 3.0)

I do not know if I can explain well: in the case above the item "1:19" is unique in the  out list of LM:UniqueFuzz but but just because it is the first that the function processes:
Code: [Select]
(LM:UniqueFuzz '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0) 0.05)
              =>(1.0 1.1 1.19  ^   ^    ^     ^  1.25 1.3 3.0  ^   ^ )

(LM:UniqueFuzz '(1.0 1.1 1.2 1.21 1.22 1.23 1.25 1.3 3.0 1.19 3.0 3.0) 0.05)
              =>(1.0 1.1 1.2  ^    ^    ^   1.25 1.3 3.0  ^    ^   ^ )

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Resolved}How to find the duplicate items in the list
« Reply #32 on: January 21, 2015, 06:07:18 AM »
Here's another idea
Code - Auto/Visual Lisp: [Select]
  1. (defun group-duplicates  (L fuzz / aL grp sem)
  2.   (foreach item  L
  3.     (if (setq grp (assoc (setq sem (fix (/ item fuzz))) aL))
  4.       (setq aL (subst (cons sem (cons item (cdr grp))) grp aL))
  5.       (setq aL (cons (list sem item) aL))))
  6.   (setq aL (vl-sort aL (function (lambda (a b) (<= (car a) (car b)))))
  7.         L nil)
  8.   (while aL
  9.     (setq L (cond
  10.               ((and L (= (1+ (caar L)) (caar aL)))
  11.                (cons (cons (caar aL) (append (cdar aL) (cdar L))) (cdr L)))
  12.               (T (cons (car aL) L)))
  13.           aL (cdr aL)))
  14.                    (vl-remove-if (function (lambda (a) (<= (length a) 2))) L))))

Basically it uses the same principle as I've done in another duplicate finder: http://www.revitforum.org/third-party-add-ins-api-r-d/19248-find-duplicate-items.html

That one was finding "fuzz" duplicate items in Revit through the Dynamo visual programming language, but extended using IronPython to make use of hash table equality matching. In this example I'm using Lisp's built in association list instead of a hash table - actually pretty sad that Lisp doesn't have this capability (makes for huge speed increases in some situations).
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Resolved}How to find the duplicate items in the list
« Reply #33 on: January 21, 2015, 08:36:21 AM »
Here's another idea
...
Is it right?
Code: [Select]
(setq fuzz 0.05   alist '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0))
=> (1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0)

(group-duplicates alist fuzz)
=> ((1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3) (3.0 3.0 3.0))

(equal 1.1 1.0  0.05) => nil
(equal 1.1 1.19 0.05) => nil
(equal 1.3 1.25 0.05) => nil
(equal 1.3 3.0  0.05) => nil

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Resolved}How to find the duplicate items in the list
« Reply #34 on: January 21, 2015, 09:01:10 AM »
Is it right?
Code: [Select]
(group-duplicates alist fuzz)
=> ((1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3) (3.0 3.0 3.0))
(group-duplicates alist fuzz)
=> ((1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3) (3.0 3.0 3.0))
Following ... as I understand this:

Code: [Select]
(equal 1.1 1.19 0.05) => nil
This one I do see that I make a mistake. Will have to look at how to get around it without making a huge extra iteration just for that edge case.

Code: [Select]
(equal 1.3 1.25 0.05) => nil
Floating point inacuracies. I use a division on the fuzz, that's why in my defun that is considered equal. It's just an implementation issue.

Code: [Select]
(equal 1.1 1.0  0.05) => nil
(equal 1.3 3.0  0.05) => nil
I don't understand. Isn't that exactly what my defun did?
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Resolved}How to find the duplicate items in the list
« Reply #35 on: January 21, 2015, 09:17:07 AM »
Code: [Select]
(equal 1.1 1.0  0.05) => nil
(equal 1.3 3.0  0.05) => nil
I don't understand. Isn't that exactly what my defun did?
Yes, I just wanted to say that:
Code: [Select]
for 1.1 >>> 1.0  is the the nearest lower (equal 1.1 1.0  0.05) => nil
for 1.1 >>> 1.19 is the closest top       (equal 1.1 1.19 0.05) => nil

for 1.3 >>> 1.25 is the the nearest lower (equal 1.3 1.25 0.05) => nil
for 1.3 >>> 3.0  is the closest top       (equal 1.3 3.0  0.05) => nil

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Resolved}How to find the duplicate items in the list
« Reply #36 on: January 21, 2015, 09:20:18 AM »
So here goes my 2nd attempt at the association list method:
Code - Auto/Visual Lisp: [Select]
  1. (defun group-duplicates1  (L fuzz / aL grp sem mx mn)
  2.   (foreach item  L
  3.     (if (setq grp (assoc (setq sem (fix (/ item fuzz))) aL))
  4.       (setq aL (subst (cons sem (cons item (cdr grp))) grp aL))
  5.       (setq aL (cons (list sem item) aL))))
  6.   (setq aL (vl-sort aL (function (lambda (a b) (>= (car a) (car b)))))
  7.         L (list (car aL))
  8.         aL (cdr aL))
  9.   (while aL
  10.     (setq mx (cond ((= (length (car L)) 2) (cadar L)) (T (apply 'max (cdar L))))
  11.           mn (cond ((= (length (car aL)) 2) (cadar aL)) (T (apply 'min (cdar aL))))
  12.           L (cond
  13.               ((equal mx mn fuzz)
  14.                (cons (cons (caar aL) (append (cdar aL) (cdar L))) (cdr L)))
  15.               (T (cons (car aL) L)))
  16.           aL (cdr aL)))
  17.   (mapcar (function (lambda (a) (reverse (cdr a))))
  18.           (vl-remove-if (function (lambda (a) (<= (length a) 2))) L)))

Seems to work:
Code: [Select]
_$ (group-duplicates1 '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0) 0.05)
((1.19 1.2) (1.25 1.21 1.22 1.23) (3.0 3.0 3.0))

Sorts out even the cases where the divide turned the floating point error arround from what the equal did.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Resolved}How to find the duplicate items in the list
« Reply #37 on: January 21, 2015, 09:28:56 AM »
Seems to work:
Code: [Select]
_$ (group-duplicates1 '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0) 0.05)
((1.19 1.2) (1.25 1.21 1.22 1.23) (3.0 3.0 3.0))
Hang-on ... that's even worse isn't it!

Back to the drawing board  :oops:
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: {Resolved}How to find the duplicate items in the list
« Reply #38 on: January 21, 2015, 09:38:59 AM »
OK, 3rd attempt ... this time it does seem to produce the correct result. I was going all wrong due to the added optimization I tried by sorting in reverse order to omit one of the reverse calls.

Code - Auto/Visual Lisp: [Select]
  1. (defun group-duplicates2  (L fuzz / aL grp sem mx mn)
  2.   (foreach item  L
  3.     (if (setq grp (assoc (setq sem (fix (/ item fuzz))) aL))
  4.       (setq aL (subst (cons sem (cons item (cdr grp))) grp aL))
  5.       (setq aL (cons (list sem item) aL))))
  6.   (setq aL (vl-sort aL (function (lambda (a b) (>= (car a) (car b)))))
  7.         L (list (car aL))
  8.         aL (cdr aL))
  9.   (while aL
  10.     (setq mx (apply 'max (cdar aL))
  11.           mn (apply 'min (cdar L))
  12.           L (cond
  13.               ((equal mx mn fuzz)
  14.                (cons (cons (caar aL) (append (cdar L) (cdar aL))) (cdr L)))
  15.               (T (cons (car aL) L)))
  16.           aL (cdr aL)))
  17.   (mapcar (function (lambda (a) (reverse (cdr a))))
  18.           (vl-remove-if (function (lambda (a) (<= (length a) 2))) L)))

This looks much more like it:
Code: [Select]
_$ (group-duplicates2 '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0) 0.05)
((1.19 1.2 1.21 1.22 1.23 1.25) (3.0 3.0 3.0))
« Last Edit: January 21, 2015, 09:45:32 AM by irneb »
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Resolved}How to find the duplicate items in the list
« Reply #39 on: January 21, 2015, 10:43:39 AM »
Another simple version (perhaps too simple), not very tested...
Code: [Select]
(defun ALE_List_ShowDupesFuzz (In_Lst FuzFac / For001 For002 OutLst)
  (foreach ForElm (mapcar '(lambda (x) (nth x In_Lst)) (vl-sort-i In_Lst '<))
    (and
      (or (equal ForElm For001 FuzFac) (and For001 (equal For001 For002 FuzFac)))
      (setq OutLst (cons For001 OutLst))
    )
    (setq For002 For001 For001 ForElm)
  )
  (if (equal For001 For002 FuzFac) (reverse (cons For001 OutLst)) (reverse OutLst))
)
Code: [Select]
(setq fuzz 0.05   alist '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0))

(ALE_List_ShowDupesFuzz alist fuzz)
=>(1.19 1.2 1.21 1.22 1.23 1.25   3.0 3.0 3.0)

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: {Resolved}How to find the duplicate items in the list
« Reply #40 on: January 22, 2015, 12:21:13 PM »
With the same concept can also do the reverse version:
Code: [Select]
; Function: ALE_List_RemoveAllDupesFuzz - Version 1.01 - 2015/01/21
;
(defun ALE_List_RemoveAllDupesFuzz (In_Lst FuzFac / For001 For002 OutLst )
  (foreach ForElm (mapcar '(lambda (x) (nth x In_Lst)) (vl-sort-i In_Lst '<))
    (and
      For001
      (or
        (equal ForElm For001 FuzFac) (equal For001 For002 FuzFac)
        (setq OutLst (cons For001 OutLst))
      )
    )
    (setq For002 For001 For001 ForElm)
  )
  (if (equal For001 For002 FuzFac) (reverse OutLst) (reverse (cons For001 OutLst)))
)
Code: [Select]
(setq fuzz 0.05   alist '(1.0 1.1 1.19 1.2 1.21 1.22 1.23 1.25 1.3 3.0 3.0 3.0))
                     =>  (1.0 1.1                              1.3)