Testing whether a tuple has all distinct elements

Question

I was seeking for a way to test whether a tuple has all distinct elements - so to say, it is a set and ended up with this quick and dirty solution.

def distinct ( tup):
    n=0
    for t in tup:
        for k in tup:
            #print t,k,n
            if (t == k ):
                n = n+1
    if ( n != len(tup)):
        return False
    else :
        return True


print distinct((1,3,2,10))

print distinct((3,3,4,2,7))

Any thinking error? Is there a builtin on tuples?

Answer 1

You can very easily do it as:

len(set(tup))==len(tup)

This creates a set of tup and checks if it is the same length as the original tup. The only case in which they would have the same length is if all elements in tup were unique

Examples

>>> a = (1,2,3)
>>> print len(set(a))==len(a)
True

>>> b = (1,2,2)
>>> print len(set(b))==len(b)
False

>>> c = (1,2,3,4,5,6,7,8,5)
>>> print len(set(c))==len(c)
False

Answer 2

In the majority of the cases, where all of the items in the tuple are hashable and support comparison (using == operator) with each other, @sshashank124's solution is what you're after:

len(set(tup))==len(tup)

For the example you posted, i.e. a tuple of ints, that would do.

---

Else, if the items are not hashable, but do have order defined on them (support '==', '<' operators, etc.), the best you can do is sorting them (O(NlogN) worst case), and then look for adjacent equal elements:

sorted_tup = sorted(tup)
all( x!=y for x,y in zip(sorted_tup[:-1],sorted_tup[1:]) ) 

---

Else, if the items only support equality comparison (==), the best you can do is the O(N^2) worst case algorithm, i.e. comparing every item to every other.

I would implement it this way, using itertools.combinations:

def distinct(tup):
  for x,y in itertools.combinations(tup, 2):
    if x == y:
      return False
  return True

Or as a one-liner:

all( x!=y for x,y in itertools.combinations(tup, 2) )