Path: csiph.com!usenet.pasdenom.info!news.etla.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: "Natural" use of cmp= in sort
Date: Mon, 10 Nov 2014 20:19:46 +0100
Organization: None
References: <eb697764-934b-4650-af28-1c55520bc1da@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
User-Agent: KNode/4.13.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.15629.1415647202.18130.python-list@python.org>
Lines: 81
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:80478

Paddy wrote:

> Hi, I do agree with                                                       
>                   Raymond H. about the relative merits of cmp= and key= in
> sort/sorted, but I decided to also not let natural uses of cmp= pass
> silently.
> 
> In answering this question, http://stackoverflow.com/a/26850434/10562
> about ordering subject to inequalities it seemed natural to use the cmp=
> argument of sort rather than key=.
> 
> The question is about merging given inequalities to make 1 inequality such
> that the inequalities also stays true.
> 
> 
> Here is a copy of my code:
> 
> Python 2.7.5 (default, May 15 2013, 22:43:36) [MSC v.1500 32 bit (Intel)]
> on win32 Type "copyright", "credits" or "license()" for more information.
>>>> ineq = """f4 > f2 > f3
> f4 > f1 > f3
> f4 > f2 > f1
> f2 > f1 > f3"""
>>>> print(ineq)
> f4 > f2 > f3
> f4 > f1 > f3
> f4 > f2 > f1
> f2 > f1 > f3
>>>> greater_thans, all_f = set(), set()
>>>> for line in ineq.split('\n'):
> ....tokens = line.strip().split()[::2]
> ....for n, t1 in enumerate(tokens[:-1]):
> ........for t2 in tokens[n+1:]:
> ............greater_thans.add((t1, t2))
> ............all_f.add(t1)
> ........all_f.add(t2)
> 
> 
>>>> sorted(all_f, cmp=lambda t1, t2: 0 if t1==t2 else
> ...........(1 if (t1, t2) not in greater_thans else -1))
> ['f4', 'f2', 'f1', 'f3']
>>>>

I'm not sure this works. I tried:

$ cat paddy.py
ineq = """f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3
f3 > f5
"""

greater_thans = set()
all_f = set()

for line in ineq.split('\n'):
    tokens = line.strip().split()[::2]
    for n, t1 in enumerate(tokens[:-1]):
        for t2 in tokens[n+1:]:
            greater_thans.add((t1, t2))
            all_f.add(t1)
        all_f.add(t2)

print all_f
print greater_thans

print sorted(all_f, cmp=lambda t1, t2: 0 if t1==t2 else 
            (1 if (t1, t2) not in greater_thans else -1))
$ PYTHONHASHSEED=0 python paddy.py 
set(['f1', 'f2', 'f3', 'f4', 'f5'])
set([('f1', 'f3'), ('f2', 'f1'), ('f2', 'f3'), ('f4', 'f3'), ('f4', 'f2'), 
('f4', 'f1'), ('f3', 'f5')])
['f4', 'f2', 'f1', 'f3', 'f5']
$ PYTHONHASHSEED=1 python paddy.py 
set(['f5', 'f4', 'f3', 'f2', 'f1'])
set([('f1', 'f3'), ('f2', 'f3'), ('f2', 'f1'), ('f4', 'f1'), ('f3', 'f5'), 
('f4', 'f3'), ('f4', 'f2')])
['f5', 'f4', 'f2', 'f1', 'f3']