tuple checking in python

Question

i've written a small program:

def check(xrr):
    """ goes through the list and returns True if the list 
    does not contain common pairs, IE ([a,b,c],[c,d,e]) = true
    but ([a,b,c],[b,a,c]) = false, note the lists can be longer than 2 tuples"""
    x = xrr[:]
    #sorting the tuples
    sorted(map(sorted,x))
    for i in range(len(x)-1):
        for j in range(len(x)-1):
            if [x[i]] == [x[i+1]] and [x[j]] == [x[j+1]]:
                return False
    return True

But it doesnt seem to work right, this is probably something extremely basic, but after a couple of days trying on and off, i cant really seem to get my head around where the error is.

Thanx in advance

You're still confusing tuples and lists. Also, "doesn't seem to work right" is a 100% worthless bug report - what results do you get, what do you expect? — user395760
– user395760, Commented Dec 12, 2010 at 14:30
@delnan I think the expected result is described in the doc-string, but I agree on "still confusing list/tuple" :) — khachik
– khachik, Commented Dec 12, 2010 at 14:45
The docstring is misleading too, if the function would look for common pairs (if pairs means what you'd expect, ie pairs([1,2,3,4]) -> [(1,2),(2,3),(3,4)]) then there can be no sorted in there. See what happens with [1,2,3,4] vs [1,3,5,2] — Jochen Ritzel
– Jochen Ritzel, Commented Dec 12, 2010 at 15:05
Your reference to "common pairs" seems to point to sets, but the implementation is disconcerting. I'd recommend adding some extra (runnable) "asserts" that univocally describe the function's expected behavior. — tokland
– tokland, Commented Dec 12, 2010 at 15:22
What is "a common pair"? Is it "an element in the same position in each list"? Is it "a pair of elements that can be found in both lists"? Is it "a pair of adjacent elements that can be found in both lists"? Or just what? Programming demands precision. One 'true' example and one 'false' example isn't even close to being enough to describe the function. — Karl Knechtel
– Karl Knechtel, Commented Dec 12, 2010 at 17:40

Jochen Ritzel · Accepted Answer · 2010-12-12 16:02:00Z

There are so many problems with your code as others have mentioned. I'll try to explain how I would implement this function.

It sounds like what you want to do is actually this: You generate a list of pairs from the input sequences and see if there are any duplicates among the pairs. When you formulate the problem like this it gets much easier to implement.

First we need to generate the pairs. It can be done in many ways, the one you would probably do is:

def pairs( seq ):
    ret = []
    # go to the 2nd last item of seq
    for k in range(len(seq)-1):
        # append a pair
        ret.append((seq[k], seq[k+1]))
    return ret

Now we want to see (a,b) and (b,a) and the same tuple, so we simply sort the tuples:

def sorted_pairs( seq ):
    ret = []
    for k in range(len(seq)-1):
        x,y = (seq[k], seq[k+1])
        if x <= y:
            ret.append((x,y))
        else:
            ret.append((y,x))
    return ret

Now solving the problem is pretty straight forward. We just need to generate all these tuples and add them to a set. Once we see a pair twice we are done:

def has_common_pairs( *seqs ):
    """ checks if there are any common pairs among any of the seqs """
    # store all the pairs we've seen
    seen = set()
    for seq in seqs:
        # generate pairs for each seq in seqs
        pair_seq = sorted_pairs(seq)
        for pair in pair_seq:
            # have we seen the pair before?
            if pair in seen:
                return True
            seen.add(pair)
    return False

Now the function you were trying to implement is quite simple:

def check(xxr):
    return not has_common_pairs(*xxr)

PS: You can generalize the sorted_pairs function to work on any kind of iterable, not only those that support indexing. For completeness sake I'll paste it below, but you don't really need it here and it' harder to understand:

def sorted_pairs( seq ):
    """ yield pairs (fst, snd) generated from seq 
        where fst <= snd for all fst, snd"""
    it = iter(seq)
    fst = next(it)
    for snd in it:
        if first <= snd:
            yield fst, snd
        else:
            yield snd, fst
        first = snd

Sven Marnach · Accepted Answer · 2010-12-12 14:51:08Z

1

I would recommend using a set for this:

def check(xrr):
    s = set()
    for t in xrr:
        u = tuple(sorted(t))
        if u in s:
           return False
        s.add(u)
    return True

This way, you don't need to sort the whole list and you stop when the first duplicate is found.

There are several errors in your code. One is that sorted returns a new list, and you just drop the return value. Another one is that you have two nested loops over your data where you would need only one. Here is the code that makes your approach work:

def check(xrr):
    x = sorted(map(sorted,xrr))
    for i in range(len(x)-1):
        if x[i] == x[i+1]:
            return False
    return True

This could be shortened to

def check(xrr):
    x = sorted(map(sorted,xrr))
    return all(a != b for a, b in zip(x[:-1], x[1:]))

But note that the first code I gave will be more efficient.

BTW, a list in Python is [1, 2, 3], while a tuple is (1, 2, 3).

edited Dec 12, 2010 at 14:51

answered Dec 12, 2010 at 14:31

Sven Marnach

608k123 gold badges968 silver badges865 bronze badges

1 Comment

khachik Over a year ago

I'm not sure, but it seems that this shouldn't work, you cannot add lists to a set (you will get lists are unhashable or something like that).

khachik · Accepted Answer · 2010-12-12 14:42:12Z

0

sorted doesn't alter the source, it returns a new list.

def check(xrr):
    xrrs = map(sorted, xrr)
    for i in range(len(xrrs)):
        if xrrs[i] in xrrs[i+1:]: return False
    return True

answered Dec 12, 2010 at 14:42

khachik

28.8k10 gold badges63 silver badges98 bronze badges

Comments

tokland · Accepted Answer · 2010-12-12 15:09:19Z

0

I'm not sure that's what's being asked, but if I understood it correctly, I'd write:

def check(lst):
    return any(not set(seq).issubset(lst[0]) for seq in lst[1:])

print check([(1, 2, 3), (2, 3, 5)]) # True 
print check([(1, 2, 3), (3, 2, 1)]) # False

edited Dec 12, 2010 at 15:09

answered Dec 12, 2010 at 14:47

tokland

68.2k13 gold badges151 silver badges174 bronze badges

Comments

Paweł Prażak · Accepted Answer · 2010-12-12 15:29:49Z

Here is more general solution, note that it find duplicates, not 'non-duplicates', it's better this way and than to use not.

def has_duplicates(seq):
    seen = set()
    for item in seq:
        if hasattr(item, '__iter__'):
            item = tuple(sorted(item))
        if item in seen:
            return True
        seen.add(item)
    return False

This is more general solution for finding duplicates:

def get_duplicates(seq):
seen = set()
duplicates = set()
for item in seq:
    item = tuple(sorted(item))
    if item in seen:
        duplicates.add(item)
    else:
        seen.add(item)
return duplicates

Also it is better to find duplicates, not the 'not duplicates', it saves a lot of confusion. You're better of using general and readable solution, than one-purpose functions.

Collectives™ on Stack Overflow

tuple checking in python

5 Answers 5

Comments

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related