Jump to content
Rangarajan

Finding unique elements across lists

Recommended Posts

Hi,

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.

 

Regards,

Rangarajan

Share this post


Link to post
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.

 

Regards,

Rangarajan

Share this post


Link to post
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)

 

Share this post


Link to post
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.

 

Regards,

Rangarajan

Share this post


Link to post
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.

 

Regards,

Rangarajan

Share this post


Link to post
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)))
    '(nil)))

 

;; (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.

 

Regards,

Rangarajan

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×