[perl-python] generic equivalence partition

Discussion in 'Python' started by Xah Lee, Feb 24, 2005.

  1. Xah Lee

    Xah Lee Guest

    another functional exercise with lists.

    Here's the perl documentation. I'll post a perl and the translated
    python version in 48 hours.

    =pod

    parti(aList, equalFunc)

    given a list aList of n elements, we want to return a list that is a
    range of numbers from 1 to n, partition by the predicate function of
    equivalence equalFunc. (a predicate function is a function that
    takes two arguments, and returns either True or False.)

    Note: a mathematical aspect: there are certain mathematical constraints
    on the a function that checks equivalence. That is to say, if a==b,
    then b==a. If a==b and b==c, then a==c. And, a==a. If a equivalence
    function does not satisfy these, it is inconsistent and basically give
    meaningless result.

    example:
    parti([['x','x','x','1'],
    ['x','x','x','2'],
    ['x','x','x','2'],
    ['x','x','x','2'],
    ['x','x','x','3'],
    ['x','x','x','4'],
    ['x','x','x','5'],
    ['x','x','x','5']], sub {$_[0]->[3] == $_[1]->[3]} )

    returns
    [[1],['2','3','4'],['5'],['6'],['7','8']];

    =cut

    In the example given, the input list's elements are lists of 4
    elements, and the equivalence function is one that returns True if the
    last item are the same.

    Note that this is a generic function. The input can be a list whose
    elements are of any type. What "parti" does is to return a partitioned
    range of numbers, that tells us which input element are equivalent to
    which, according to the predicate given. For example, in the given
    example, it tells us that the 2nd, 3rd, 4th elements are equivalent.
    And they are equivalent measured by the predicate function given, which
    basically tests if their last item are the same integer. (note that if
    we want to view the result as indexes, then it is 1-based index. i.e.
    counting starts at 1.)

    PS if you didn't realize yet, nested lists/dictionaries in perl is a
    complete pain in the ass.

    PS note that the code "sub {$_[0]->[3] == $_[1]->[3]}" is what's called
    the lambda form, in Perl.

    Xah

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 24, 2005
    #1
    1. Advertising

  2. Xah Lee

    Bryan Guest

    Xah Lee wrote:
    > another functional exercise with lists.
    >
    > Here's the perl documentation. I'll post a perl and the translated
    > python version in 48 hours.
    >
    > =pod
    >
    > parti(aList, equalFunc)
    >
    > given a list aList of n elements, we want to return a list that is a
    > range of numbers from 1 to n, partition by the predicate function of
    > equivalence equalFunc. (a predicate function is a function that
    > takes two arguments, and returns either True or False.)
    >
    > Note: a mathematical aspect: there are certain mathematical constraints
    > on the a function that checks equivalence. That is to say, if a==b,
    > then b==a. If a==b and b==c, then a==c. And, a==a. If a equivalence
    > function does not satisfy these, it is inconsistent and basically give
    > meaningless result.
    >
    > example:
    > parti([['x','x','x','1'],
    > ['x','x','x','2'],
    > ['x','x','x','2'],
    > ['x','x','x','2'],
    > ['x','x','x','3'],
    > ['x','x','x','4'],
    > ['x','x','x','5'],
    > ['x','x','x','5']], sub {$_[0]->[3] == $_[1]->[3]} )
    >
    > returns
    > [[1],['2','3','4'],['5'],['6'],['7','8']];
    >
    > =cut
    >
    > In the example given, the input list's elements are lists of 4
    > elements, and the equivalence function is one that returns True if the
    > last item are the same.
    >
    > Note that this is a generic function. The input can be a list whose
    > elements are of any type. What "parti" does is to return a partitioned
    > range of numbers, that tells us which input element are equivalent to
    > which, according to the predicate given. For example, in the given
    > example, it tells us that the 2nd, 3rd, 4th elements are equivalent.
    > And they are equivalent measured by the predicate function given, which
    > basically tests if their last item are the same integer. (note that if
    > we want to view the result as indexes, then it is 1-based index. i.e.
    > counting starts at 1.)
    >
    > PS if you didn't realize yet, nested lists/dictionaries in perl is a
    > complete pain in the ass.
    >
    > PS note that the code "sub {$_[0]->[3] == $_[1]->[3]}" is what's called
    > the lambda form, in Perl.
    >
    > Xah
    >
    > http://xahlee.org/PageTwo_dir/more.html
    >


    this is the first thing that came to my mind. i'm sure there are more clever
    ways to do this.

    elements = [['x', 'x', 'x', '1'],
    ['x', 'x', 'x', '2'],
    ['x', 'x', 'x', '2'],
    ['x', 'x', 'x', '2'],
    ['x', 'x', 'x', '3'],
    ['x', 'x', 'x', '4'],
    ['x', 'x', 'x', '5'],
    ['x', 'x', 'x', '5']]
    pos = {}

    for i, element in enumerate(elements):
    pos.setdefault(element[-1], []).append(i+1)

    p = pos.values()
    p.sort()
    [[1], [2, 3, 4], [5], [6], [7, 8]]


    bryan
     
    Bryan, Feb 25, 2005
    #2
    1. Advertising

  3. Xah Lee

    John Machin Guest

    On Thu, 24 Feb 2005 17:48:47 -0800, Bryan <> wrote:

    >Xah Lee wrote:
    >> another functional exercise with lists.
    >>
    >> Here's the perl documentation. I'll post a perl and the translated
    >> python version in 48 hours.
    >>
    >> =pod
    >>
    >> parti(aList, equalFunc)
    >>
    >> given a list aList of n elements, we want to return a list that is a
    >> range of numbers from 1 to n, partition by the predicate function of
    >> equivalence equalFunc. (a predicate function is a function that
    >> takes two arguments, and returns either True or False.)


    [snip]

    >> example:
    >> parti([['x','x','x','1'],
    >> ['x','x','x','2'],

    [snip]
    >> ['x','x','x','5']], sub {$_[0]->[3] == $_[1]->[3]} )
    >>
    >> returns
    >> [[1],['2','3','4'],['5'],['6'],['7','8']];
    >>
    >> =cut
    >>
    >> In the example given, the input list's elements are lists of 4
    >> elements, and the equivalence function is one that returns True if the
    >> last item are the same.

    >

    [snip]

    >>

    >
    >this is the first thing that came to my mind. i'm sure there are more clever
    >ways to do this.
    >
    >elements = [['x', 'x', 'x', '1'],

    [snip]
    > ['x', 'x', 'x', '5']]
    >pos = {}
    >
    >for i, element in enumerate(elements):
    > pos.setdefault(element[-1], []).append(i+1)
    >
    >p = pos.values()
    >p.sort()
    >[[1], [2, 3, 4], [5], [6], [7, 8]]
    >
    >


    Bryan: Bzzzt. Xah was proposing a GENERAL function. You have HARDWIRED
    his (simplistic) example.

    Xah: Bzzzt. Too close to your previous exercise.
     
    John Machin, Feb 25, 2005
    #3
  4. In article <>,
    "Xah Lee" <> wrote:

    > parti(aList, equalFunc)
    >
    > given a list aList of n elements, we want to return a list that is a
    > range of numbers from 1 to n, partition by the predicate function of
    > equivalence equalFunc. (a predicate function is a function that
    > takes two arguments, and returns either True or False.)


    In Python it is much more natural to use ranges from 0 to n-1.
    In the worst case, this is going to have to take quadratic time
    (consider an equalFunc that always returns false) so we might as well do
    something really simple rather than trying to be clever.

    def parti(aList,equalFunc):
    eqv = []
    for i in range(len(aList)):
    print i,eqv
    for L in eqv:
    if equalFunc(aList,aList[L[0]]):
    L.append(i)
    break;
    else:
    eqv.append()

    If you really want the ranges to be 1 to n, add one to each number in
    the returned list-of-lists.

    --
    David Eppstein
    Computer Science Dept., Univ. of California, Irvine
    http://www.ics.uci.edu/~eppstein/
     
    David Eppstein, Feb 25, 2005
    #4
  5. In article <>,
    David Eppstein <> wrote:

    > def parti(aList,equalFunc):
    > eqv = []
    > for i in range(len(aList)):
    > print i,eqv
    > for L in eqv:
    > if equalFunc(aList,aList[L[0]]):
    > L.append(i)
    > break;
    > else:
    > eqv.append()


    Um, take out the print, that was just there for me to debug my code.

    --
    David Eppstein
    Computer Science Dept., Univ. of California, Irvine
    http://www.ics.uci.edu/~eppstein/
     
    David Eppstein, Feb 25, 2005
    #5
  6. David Eppstein wrote:
    > In article <>,
    > "Xah Lee" <> wrote:
    >>given a list aList of n elements, we want to return a list that is a
    >>range of numbers from 1 to n, partition by the predicate function of
    >>equivalence equalFunc.


    > In the worst case, this is going to have to take quadratic time
    > (consider an equalFunc that always returns false) so we might as well do
    > something really simple rather than trying to be clever.
    >
    > def parti(aList,equalFunc):
    > eqv = []
    > for i in range(len(aList)):
    > print i,eqv
    > for L in eqv:
    > if equalFunc(aList,aList[L[0]]):
    > L.append(i)
    > break;
    > else:
    > eqv.append()
    >
    >

    Unless we can inspect the predicate function and derive a hash function such
    that hash(a) == hash(b) => predicate(a,b) is True. Then the partition can take
    linear time
    i.e.,
    >>> def equal(a,b):

    ... return a[-1] == b[-1]
    ...
    >>> def hashFunc(obj):

    ... return hash(obj[-1])
    ...
    >>> def parti(aList, hashFunc):

    ... eqv = {}
    ... for i,obj in enumerate(aList):
    ... eqv.setdefault(hashFunc(obj),[]).append(i)
    ... return eqv.values()
    ...

    In the case where the predicate is a "black box", would a logistic regression
    over a sample of inputs enable a hash function to be derived experimentally?

    Michael
     
    Michael Spencer, Feb 25, 2005
    #6
  7. Xah Lee

    Paul Moore Guest

    David Eppstein <> writes:

    > In article <>,
    > "Xah Lee" <> wrote:
    >
    >> parti(aList, equalFunc)
    >>
    >> given a list aList of n elements, we want to return a list that is a
    >> range of numbers from 1 to n, partition by the predicate function of
    >> equivalence equalFunc. (a predicate function is a function that
    >> takes two arguments, and returns either True or False.)

    >
    > In Python it is much more natural to use ranges from 0 to n-1.
    > In the worst case, this is going to have to take quadratic time
    > (consider an equalFunc that always returns false) so we might as well do
    > something really simple rather than trying to be clever.


    As you say, with the spec as it stands, you can't do better than
    quadratic time (although it's O(n*m) where m is the number of
    partitions, rather than O(n^2)).

    You can do a lot better if you can use a "key" function, rather than
    an "equivalence" function, much as list.sort has a "key" argument, and
    itertools.groupby (which is pretty close in function to this
    partitioning problem) uses a key argument.

    In fact, I'd have difficulty thinking of an example where I'd want a
    partition function as specified, in Python. In Perl, it makes a lot of
    sense, as Perl's array indexing operations lend themselves to slinging
    round lists of indices like this. But in Python, I'd be far more
    likely to use list.sort followed by itertools.groupby - sort is stable
    (so doesn't alter the relative order within equivalence classes), and
    groupby then picks out the equivalence classes:

    >>> elements = [['x', 'x', 'x', '1'],

    .... ['x', 'x', 'x', '2'],
    .... ['x', 'x', 'x', '2'],
    .... ['x', 'x', 'x', '2'],
    .... ['x', 'x', 'x', '3'],
    .... ['x', 'x', 'x', '4'],
    .... ['x', 'x', 'x', '5'],
    .... ['x', 'x', 'x', '5']]

    >>> # No need to sort here, as the elements are already sorted!


    >>> from pprint import pprint
    >>> pprint([(k, list(v)) for k, v in groupby(elements, itemgetter(3))])

    [('1', [['x', 'x', 'x', '1']]),
    ('2', [['x', 'x', 'x', '2'], ['x', 'x', 'x', '2'], ['x', 'x', 'x', '2']]),
    ('3', [['x', 'x', 'x', '3']]),
    ('4', [['x', 'x', 'x', '4']]),
    ('5', [['x', 'x', 'x', '5'], ['x', 'x', 'x', '5']])]

    If you avoid the sort, the whole thing is highly memory efficient, as
    well, because by using iterators, we don't ever take a copy of the
    original list.

    Having cleverly redefined the question so that it fits the answer I
    wanted to give, I'll shut up now :)

    Paul.
    --
    To attain knowledge, add things every day; to attain wisdom, remove
    things every day. -- Lao-Tse
     
    Paul Moore, Feb 25, 2005
    #7
  8. Xah Lee

    Xah Lee Guest

    Re: generic equivalence partition

    # the following solution is submitted by
    # Sean Gugler and David Eppstein independently
    # 20050224.

    @def parti(aList, equalFunc):
    @ result = []
    @ for i in range(len(aList)):
    @ for s in result:
    @ if equalFunc( aList, aList[s[0]] ):
    @ s.append(i)
    @ break
    @ else:
    @ result.append( )
    @ return [[x+1 for x in L] for L in result] # add 1 to all numbers
    @
    @---------------

    as for my original perl code, i realized it is written to work on a
    sorted input. Here it is and the translated Python code.

    # perl
    sub parti($$) {
    my @li = @{$_[0]};
    my $sameQ = $_[1];

    my @tray=(1);
    my @result;

    for (my $i=1; $i <= ((scalar @li)-1); $i++) {
    if (&$sameQ($li[$i-1], $li[$i])) {
    push @tray, $i+1}
    else {
    push @result, [@tray]; @tray=($i+1);
    }
    }
    push @result, [@tray];
    return \@result;
    }


    @#python
    @def parti(li,sameQ):
    @ tray=[1];
    @ result=[];
    @
    @ for i in range(1, len(li) ):
    @ if sameQ(li[i-1],li):
    @ tray.append(i+1)
    @ else:
    @ result.append(tray)
    @ tray=[i+1]
    @ result.append(tray)
    @ return result
    @

    http://xahlee.org/perl-python/gen_parti_by_equiv.html

    Xah

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 26, 2005
    #8
  9. Xah Lee

    Xah Lee Guest

    Re: generic equivalence partition

    folks:

    when using google to post a reply, it sometimes truncates the subject
    line. i.e. [perl-python] is lost. This software error is obvious, they
    could not have not noticed it.

    another thing more egregious is that google _intentionally_ edit with
    people's posts. (e.g. they change email address lines without author's
    permission, and they also change program codes so it no longer run).
    Please spread these google irresponsibility to all related forums on
    software responsibility and online forum issues.

    Ostensible incorrect behavior like these by google is egregious enough
    to generate a law suit and if such company do not take software
    correctness seriously, we must punish them.

    Please spread this awareness.

    Xah

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 26, 2005
    #9
  10. Xah Lee

    Xah Lee Guest

    Re: generic equivalence partition

    People,

    .... sorry for the latching on on this broadside issue, but it is
    impotant ...

    here's are some germane points from another online discussion:

    the bug-reporting issue has came up so many times by so many people i
    thought i'd make a comment of my view.

    when a software is ostensibly incorrect, and if it is likely in
    connection to egregious irresponsibility as most software companies are
    thru their irresponsible licensing, the thing one should not do is to
    fawn up to their ass as in filing a bug report, and that is also the
    least effective in correcting the software.

    the common attitude of bug-reporting is one reason that contributed to
    the tremendous egregious irresponsible fuckups in computer software
    industry that each of us have to endure daily all the time. (e.g.
    software A clashed, software B can't do this, C can't do that, D i
    don't know how to use, E download location currently broken, F i need
    to join discussion group to find a work-around, G is all pretty and
    dysfunctional... )

    when a software is ostensibly incorrect and when the company is
    irresponsible with their licensing, the most effective and moral
    attitude is to do legal harm to the legal entity. This one an do by
    filing a law suit or spreading the fact. Filing a law suit is
    appropriate in severe and serious cases, and provided you have such
    devotion to the cause. For most cases, we should just spread the fact.
    When a company see facts flying about their incompetence or
    irresponsibility, they will immediately mend the problem source, or
    cease to exist.

    Another harm sprang from the fucking bug-reporting attitude rampant
    among IT morons is the multiplication of pop-ups that bug users for
    bug-reporting, complete with their privacy intrusion legalese.

    http://xahlee.org/UnixResource_dir/writ/responsible_license.html

    Xah

    http://xahlee.org/PageTwo_dir/more.html


    Xah Lee wrote:
    > folks:
    >
    > when using google to post a reply, it sometimes truncates the subject
    > line. i.e. [perl-python] is lost. This software error is obvious,

    they
    > could not have not noticed it.
    >
    > another thing more egregious is that google _intentionally_ edit with
    > people's posts. (e.g. they change email address lines without

    author's
    > permission, and they also change program codes so it no longer run).
    > Please spread these google irresponsibility to all related forums on
    > software responsibility and online forum issues.
    >
    > Ostensible incorrect behavior like these by google is egregious

    enough
    > to generate a law suit and if such company do not take software
    > correctness seriously, we must punish them.
    >
    > Please spread this awareness.
    >
    > Xah
    >
    > http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 27, 2005
    #10
  11. Re: generic equivalence partition

    Xah Lee wrote:

    > ... sorry for the latching on on this broadside issue, but it is
    > impotant ...


    You made a typo in that last word there. Obviously you meant to write
    an _e_ instead of an _a_.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    All bad poetry springs from genuine feeling.
    -- Oscar Wilde
     
    Erik Max Francis, Feb 27, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Xah Lee
    Replies:
    41
    Views:
    1,061
    Paul McGuire
    Feb 24, 2005
  2. bolega
    Replies:
    1
    Views:
    685
    Stan Bischof
    Mar 28, 2011
  3. Rudi Cilibrasi
    Replies:
    13
    Views:
    276
    Rick DeNatale
    Jul 4, 2008
  4. Xah Lee
    Replies:
    12
    Views:
    226
    Paul McGuire
    Feb 24, 2005
  5. Xah Lee
    Replies:
    7
    Views:
    149
    Erik Max Francis
    Feb 27, 2005
Loading...

Share This Page