# 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 on other sites

```(setf lst '((1 2 3) (2 4) (3 5)))
(rnd-unique (length lst) (flatten lst))```

##### 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 on other sites

I see what you are after.

As you know you can write your own functions and extend the system to your own needs.

##### Share on other sites

Yeah. There are so many nice functions in OM, so wanted to know if there was one directly usable.

Thanks, anyway.

Regards,

Rangarajan

##### 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 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 on other sites

I personally think this is how the function needs to work.

What would you expect here:

`(find-unique-seq '((1 2 3) (2) (2) (2)))`

Unique is unique.

##### 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 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 on other sites

NIL output is what we need to avoid in Opusmodus especially when you deal with pitches, lengths etc... this is why you almost never, see any NIL output in OPMO.

##### Share on other sites

OK, interesting point. It is possible to return duplicate elements if unique elements cannot be found.

-Rangarajan

## Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

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

×
×
• #### Browser

• Video Gallery

• Lessons