Jump to content

Finding unique elements across lists

Recommended Posts


I see that there is a family of functions for computing "unique" elements, sequences, etc. Just wondering if there is a function to pick a random element from a list of lists, such that the result has no duplicates.


For example, assuming the function is called "select-unique-elements", I am expecting this behaviour:

(select-unique-elements '((1 2 3) (2 4) (3 5))) => (1 2 3) or (1 4 5) or (2 4 3) etc.


That is, each time I call this function it will return a possibly different list with one element chosen from each sub-list, but preserving uniqueness in the result.




Link to comment
Share on other sites

No, this won't work because the order is not preserved. I guess I should have been more precise in my specification. We need one element from each sublist, in the same order of sublists, such that the final selection is unique. This is reflected in my example output.


The solution you have given can yield, for example, (2 4 1). The last sublist in input does not have 1, so this is incorrect.




Link to comment
Share on other sites

Here it is:

(defun find-unique-seq (sequence &key seed)
  (do-verbose ("find-unique-seq")
    (rnd-seed seed)
    (prog (elem pick out)
      (dotimes (i (length sequence))
        (setf elem (find-unique (car sequence)))
        (setf pick (rnd-pick elem :seed (seed)))
        (setf out (cons pick out))
        (setf sequence (mapcar (lambda (x) (remove pick x)) (cdr sequence))))
      (return (remove nil (nreverse out))))))

(rnd-unique-seq '((1 2 3) (2 4) (3 5)))
=> (3 2 5)


Link to comment
Share on other sites

Thanks, but this does not work (in general). 


Try this test code:

(let (result)
    (dotimes (i 20)
      (setf result (find-unique-seq '((1 2 3) (2))))
      (when (< (length result) 2)
        (format t "Result: ~A  does not satisfy specification~%" result))))


You can see that there are times when the output does not include element from at least one of the subsets. The simplest test case is what I have used in the code fragment:

'((1 2 3) (2))


It seems to me that to solve this problem requires some backtracking or heavy pre-processing. Maybe I am wrong.




Link to comment
Share on other sites

I understand what you are saying, and this could be an acceptable specification of the function. According to my specification, this example is "unsatisfiable". There is a simple prerequisite: (>= (length (union given-sublists)) (length given-sublists)).


In this example, there are 4 sublists, but only 3 unique elements across the whole sublists. So it is not satisfiable at all. As an exception, in this case, you could repeat the elements. But what I want is: if the prerequisite is satisfied, then the function should return unique elements. So in this example '((1 2) (2)), the function should ALWAYS return '(1 2) because there is no other solution. In the case of '((1 2) (1 2) (2 3)), the solutions are: (1 2 3), (2 1 3).


I agree that the definition you have provided is still quite useful.




Link to comment
Share on other sites

I think this might work, although computationally expensive:


;; (combinations '(1 2) '(3 4)) => ((1 3) (2 3) (1 4) (2 4))
(defun find-all-combinations-of (&rest sublists)
  (if (first sublists)
      (mapcan (lambda (x) (mapcar (lambda (y) (cons y x)) (first sublists)))
              (apply #'find-all-combinations-of (rest sublists)))


;; (select-unique-elements '((1 3 2) (1) (2 1 3))) => (2 1 3) or (3 1 2)
(defun select-unique-elements (alist)
  (rnd-pick (remove-if (lambda (alist) (< (length (find-unique alist)) (length alist))) (apply #'find-all-combinations-of alist))))


;; Test cases

(select-unique-elements '((1 3 2) (1) (2 1 3))) => (2 1 3) or (3 1 2)


(select-unique-elements '((2) (2 1))) => (2 1)


(select-unique-elements '((1) (1))) => nil


I return nil if unique elements cannot be selected.




Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...

Important Information

Terms of Use Privacy Policy