Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #11903 > unrolled thread

Compare tuples of different lenght

Back to article view | Back to comp.lang.python

Contents

  Compare tuples of different lenght Jurgens de Bruin <debruinjj@gmail.com> - 2011-08-20 01:25 -0700
    Re: Compare tuples of different lenght Chris Rebert <clp2@rebertia.com> - 2011-08-20 01:45 -0700
      Re: Compare tuples of different lenght Jurgens de Bruin <debruinjj@gmail.com> - 2011-08-20 01:54 -0700
      Re: Compare tuples of different lenght Jurgens de Bruin <debruinjj@gmail.com> - 2011-08-20 02:00 -0700
    Re: Compare tuples of different lenght Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-20 20:17 +1000
      Re: Compare tuples of different lenght Jurgens de Bruin <debruinjj@gmail.com> - 2011-08-20 03:47 -0700
    Re: Compare tuples of different lenght Peter Otten <__peter__@web.de> - 2011-08-20 13:56 +0200
    Re: Compare tuples of different lenght John O'Hagan <research@johnohagan.com> - 2011-08-21 01:03 +1000

#11903 — Compare tuples of different lenght

Hi,

I have a list of tuples:

[(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]

I would like to compare all the tuples to each other and if one
element if found two tuples the smallest tuples is removed from the
list.

example if tuple 1 and tuple 3 are compare it should find that a
single element in each are the same and tuple 1 should be removed
resulting in

[(12,13),(2,3,4),(8,),(5,6),(7,8,9),]

the same for tuple 4 and 6 resulting in

[(12,13),(2,3,4),(5,6),(7,8,9),]

is this possible as I am having no success.

Thanks

[toc] | [next] | [standalone]

#11905

On Sat, Aug 20, 2011 at 1:25 AM, Jurgens de Bruin <debruinjj@gmail.com> wrote:
> Hi,
>
> I have a list of tuples:
>
> [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
>
> I would like to compare all the tuples to each other and if one
> element if found two tuples the smallest tuples is removed from the
> list.

So, would [(5,6), (6,7,8)] become [(6,7,8)] ?

If no, then I believe you're trying to solve the set covering problem:
http://en.wikipedia.org/wiki/Set_cover_problem

Cheers,
Chris
--
http://rebertia.com

[toc] | [prev] | [next] | [standalone]

#11906

On Aug 20, 10:45 am, Chris Rebert <c...@rebertia.com> wrote:
> On Sat, Aug 20, 2011 at 1:25 AM, Jurgens de Bruin <debrui...@gmail.com> wrote:
>
> > Hi,
>
> > I have a list of tuples:
>
> > [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
>
> > I would like to compare all the tuples to each other and if one
> > element if found two tuples the smallest tuples is removed from the
> > list.
>
> So, would [(5,6), (6,7,8)] become [(6,7,8)] ?
>
> If no, then I believe you're trying to solve the set covering problem:http://en.wikipedia.org/wiki/Set_cover_problem
>
> Cheers,
> Chris
> --http://rebertia.com

[(5,6), (6,7,8)] would become [(6,7,8)].

Thanks for the response

[toc] | [prev] | [next] | [standalone]

#11907

On Aug 20, 10:45 am, Chris Rebert <c...@rebertia.com> wrote:
> On Sat, Aug 20, 2011 at 1:25 AM, Jurgens de Bruin <debrui...@gmail.com> wrote:
>
> > Hi,
>
> > I have a list of tuples:
>
> > [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
>
> > I would like to compare all the tuples to each other and if one
> > element if found two tuples the smallest tuples is removed from the
> > list.
>
> So, would [(5,6), (6,7,8)] become [(6,7,8)] ?
>
> If no, then I believe you're trying to solve the set covering problem:http://en.wikipedia.org/wiki/Set_cover_problem
>
> Cheers,
> Chris
> --http://rebertia.com

[(5,6), (6,7,8)] will indeed become [(6,7,8)]

Tanks!!

[toc] | [prev] | [next] | [standalone]

#11911

Jurgens de Bruin wrote:

> Hi,
> 
> I have a list of tuples:
> 
> [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
> 
> I would like to compare all the tuples to each other and if one
> element if found two tuples the smallest tuples is removed from the
> list.

It's not clear what you mean by "smallest" tuple. Is (8,) smaller than
(7,8,9)?

I'm going to guess you care only about the length of the tuple, and not the
items themselves.

Let's start with a couple of helper functions.

def compare(t1, t2):
    'Return -1 if t1 is "smaller" than t2, 0 if equal, and +1 if "bigger".'
    if len(t1) < len(t2): return -1
    elif len(t1) > len(t2): return 1
    else: return 0

def match_any_item(t1, t2):
    try:
        s1 = set(t1)
        s2 = set(t2)
        return bool(s1 & s2)
    except TypeError:
        # Can't convert to sets because at least one item is mutable.
        # Let's do this the slow(?) way.
        matched = [x for x in t1 if x in t2]
        return bool(matched)



list_of_tuples = [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
flags = [True]*len(list_of_tuples)
for i,t1 in enumerate(list_of_tuples):
    for j in range(i+1, len(list_of_tuples)):
        t2 = list_of_tuples[j]
        if match_any_item(t1, t2):
            n = compare(t1, t2)
            if n == -1:
                # Flag t1 to be removed.
                flags[i] = False
            elif n == 1:
                # Flag t2 to be removed.
                flags[j] = False

saved_tuples = []
for t,flag in zip(list_of_tuples, flags):
    if flag: saved_tuples.append(t)



This gives:

>>> saved_tuples
[(12, 13), (2, 3, 4), (5, 6), (7, 8, 9)]


which matches what you wanted:

> [(12,13),(2,3,4),(5,6),(7,8,9),]




-- 
Steven

[toc] | [prev] | [next] | [standalone]

#11912

On Aug 20, 12:17 pm, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> Jurgens de Bruin wrote:
> > Hi,
>
> > I have a list of tuples:
>
> > [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
>
> > I would like to compare all the tuples to each other and if one
> > element if found two tuples the smallest tuples is removed from the
> > list.
>
> It's not clear what you mean by "smallest" tuple. Is (8,) smaller than
> (7,8,9)?
>
> I'm going to guess you care only about the length of the tuple, and not the
> items themselves.
>
> Let's start with a couple of helper functions.
>
> def compare(t1, t2):
>     'Return -1 if t1 is "smaller" than t2, 0 if equal, and +1 if "bigger".'
>     if len(t1) < len(t2): return -1
>     elif len(t1) > len(t2): return 1
>     else: return 0
>
> def match_any_item(t1, t2):
>     try:
>         s1 = set(t1)
>         s2 = set(t2)
>         return bool(s1 & s2)
>     except TypeError:
>         # Can't convert to sets because at least one item is mutable.
>         # Let's do this the slow(?) way.
>         matched = [x for x in t1 if x in t2]
>         return bool(matched)
>
> list_of_tuples = [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
> flags = [True]*len(list_of_tuples)
> for i,t1 in enumerate(list_of_tuples):
>     for j in range(i+1, len(list_of_tuples)):
>         t2 = list_of_tuples[j]
>         if match_any_item(t1, t2):
>             n = compare(t1, t2)
>             if n == -1:
>                 # Flag t1 to be removed.
>                 flags[i] = False
>             elif n == 1:
>                 # Flag t2 to be removed.
>                 flags[j] = False
>
> saved_tuples = []
> for t,flag in zip(list_of_tuples, flags):
>     if flag: saved_tuples.append(t)
>
> This gives:
>
> >>> saved_tuples
>
> [(12, 13), (2, 3, 4), (5, 6), (7, 8, 9)]
>
> which matches what you wanted:
>
> > [(12,13),(2,3,4),(5,6),(7,8,9),]
>
> --
> Steven

Thanks Steven. This works great!!!

Appreciated very much!!!

[toc] | [prev] | [next] | [standalone]

#11913

Jurgens de Bruin wrote:

> Hi,
> 
> I have a list of tuples:
> 
> [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
> 
> I would like to compare all the tuples to each other and if one
> element if found two tuples the smallest tuples is removed from the
> list.
> 
> example if tuple 1 and tuple 3 are compare it should find that a
> single element in each are the same and tuple 1 should be removed
> resulting in
> 
> [(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
> 
> the same for tuple 4 and 6 resulting in
> 
> [(12,13),(2,3,4),(5,6),(7,8,9),]
> 
> is this possible as I am having no success.
> 
> Thanks

from collections import Counter, defaultdict
from itertools import chain

def process_counter(sample):
    c = Counter()
    d = defaultdict(list)
    for items in sample:
        c.update(items)
        d[len(items)].append(items)

    result = []
    for cluster in sorted(d.values(), key=len):
        c.subtract(chain.from_iterable(cluster))
        for items in cluster:
            if not any(c[item] for item in items):
                result.append(items)

    result.sort(key=sample.index)
    return result

if __name__ == "__main__":
    for process in [process_counter]:
        print process.__name__

        sample = [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
        wanted = [(12,13),(2,3,4),(5,6),(7,8,9),]
        assert process(sample) == wanted


        sample = [(5,6), (6,7,8)]
        wanted = [(6,7,8)]
        got = process(sample)
        assert got == wanted

        sample = wanted = [(5, 6), (6, 7)]
        assert process(sample) == wanted

        sample = [(1,), (1, 2), (2, 3, 4)]
        wanted = [(2, 3, 4)]
        assert process(sample) == wanted
 

[toc] | [prev] | [next] | [standalone]

#11920

On Sat, 20 Aug 2011 01:25:18 -0700 (PDT)
Jurgens de Bruin <debruinjj@gmail.com> wrote:

> Hi,
> 
> I have a list of tuples:
> 
> [(2,),(12,13),(2,3,4),(8,),(5,6),(7,8,9),]
> 
> I would like to compare all the tuples to each other and if one
> element if found two tuples the smallest tuples is removed from the
> list.
[...]

This should work:

def long_match(tuples):
    sorted_tuples = sorted(tuples, key=len)
    for n, t in enumerate(sorted_tuples):
        for s in sorted_tuples[n + 1:]:
            if len(s) > len(t) and any(i in s for i in t):    
                tuples.remove(t)
                break
    return tuples 
 

Regards,

John

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web