I need to sort this list:
[('A','Y'), ('J','A'), ('Y','J')] like this:
[('A','Y'), ('Y','J'), ('J','A')].
Note how the Ys and Js are together. All I need is for the second element of
one tuple to equal the first element of the next tuple. Another valid
solution is [('J','A'), ('A','Y'), ('Y','J')].
I was successful in doing this a while back with a modified bubble sort
algorithm, but now I can't find my own code. Can the list be sorted with a
comparison function or some other way? 5 2092
Anthony D'Agostino, this is my first raw version, it can fail in lots
of ways depending on your input list l (and surely there are better
ways to do it), but it's a start:
.. l = [('A','Y'), ('J','A'), ('Y','J')]
.. pairs = dict(l)
.. result = []
.. key = pairs.iterkeys().next()
.. while pairs:
.. val = pairs.pop(key)
.. result.append( (key, val) )
.. key = val
.. print result
Bear hugs,
Bearophie
In article <fL********************@comcast.com>,
"Anthony D'Agostino" <ga*******@dope.comcast.net> wrote: I need to sort this list: [('A','Y'), ('J','A'), ('Y','J')] like this: [('A','Y'), ('Y','J'), ('J','A')].
Note how the Ys and Js are together. All I need is for the second element of one tuple to equal the first element of the next tuple. Another valid solution is [('J','A'), ('A','Y'), ('Y','J')].
This is an interesting problem. Can you give us more details? I'm
assuming the length of the list can be any arbitrary length. Will there
always only be three letters? Can there ever be a pair with the same first
and second elements, i.e. ('A', 'A')?
Will there always be a valid solution? For example, it's trivial to show
that
[('A', 'Y'), ('A', 'J'), ('J', 'A')]
cannot be sorted using your criteria (there's no pair starting with 'Y' to
match the one that ends with 'Y')
Is this a real-life problem, or are we doing your homework for you? :-)
I found my old bubble sort solution:
============================================
def esort(edges):
while 1:
swaps = 0
for j in range(len(edges)-2):
if edges[j][1] != edges[j+1][0]:
edges[j+1],edges[j+2] = edges[j+2],edges[j+1] # swap
swaps = 1
if swaps == 0: break
return edges
print esort([('A','Y'), ('J','A'), ('Y','J')])
print esort([(5,0), (6, -12), (0,6), (-12, 3)])
============================================
The list can be any length and there will always be multiple valid
solutions, depending on which edge you start with. I'm using this to sort
edges for mesh subdivision. I just thought there might be a more elegant way
to write it.
On Fri, 29 Apr 2005 23:37:39 -0400, "Anthony D'Agostino" <ga*******@dope.comcast.net> wrote: I found my old bubble sort solution:
============================================ def esort(edges): while 1: swaps = 0 for j in range(len(edges)-2): if edges[j][1] != edges[j+1][0]: edges[j+1],edges[j+2] = edges[j+2],edges[j+1] # swap swaps = 1 if swaps == 0: break return edges
print esort([('A','Y'), ('J','A'), ('Y','J')]) print esort([(5,0), (6, -12), (0,6), (-12, 3)]) ============================================
The list can be any length and there will always be multiple valid solutions, depending on which edge you start with. I'm using this to sort edges for mesh subdivision. I just thought there might be a more elegant way to write it.
This is not tested beyond what you see, but it might give some ideas for
what you want to do. I finds separate sequences if you combine the above into
one, e.g.,
----< dagostinoedges.py >-----------------------------------------------------------
# I need to sort this list:
# [('A','Y'), ('J','A'), ('Y','J')] like this:
# [('A','Y'), ('Y','J'), ('J','A')].
#
# Note how the Ys and Js are together. All I need is for the second element of
# one tuple to equal the first element of the next tuple. Another valid
# solution is [('J','A'), ('A','Y'), ('Y','J')].
#
import itertools
def connect(edges):
nodes = dict([(e[0], e) for e in edges])
heads = set([e[0] for e in edges])
tails = set([e[1] for e in edges])
starts = heads - tails
out = []
seen = set()
for h in itertools.chain(starts, heads):
curr = nodes[h]
sub = []
while curr not in seen:
sub.append(curr)
seen.add(curr)
curr = nodes.get(curr[1])
if curr is None: break
if sub: out.append(sub)
return out
if __name__ == '__main__':
edges = set([('A','Y'), ('J','A'), ('Y','J'),
(5,0), (6, -12), (0,6), (-12, 3),
('all', 'alone')])
for sub in connect(edges): print sub
------------------------------------------------------------------------------------
Result:
[ 2:54] C:\pywk\clp>py24 dagostinoedges.py
[('all', 'alone')]
[(5, 0), (0, 6), (6, -12), (-12, 3)]
[('A', 'Y'), ('Y', 'J'), ('J', 'A')]
Regards,
Bengt Richter This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: aruna |
last post by:
Given a set of integers, how to write a program in C
to sort these set of integers using C, given the following conditions
a. Do not use arrays
b. Do not use any comparison function like if/then...
|
by: Brian Henry |
last post by:
Here is another virtual mode example for the .NET 2.0 framework while
working with the list view. Since you can not access the items collection of
the list view you need to do sorting another...
|
by: apotheos |
last post by:
I can't seem to get this nailed down and I thought I'd toss it out
there as, by gosh, its got to be something simple I'm missing.
I have two different database tables of events that use different...
|
by: John Salerno |
last post by:
Hi everyone. If I have a list of tuples, and each tuple is in the form:
(year, text) as in ('1995', 'This is a citation.')
How can I sort the list so that they are in chronological order based...
|
by: joeke3el |
last post by:
Hi everyone,
I have not touched Perl in the last 4 years, my books are at work and I have something here I'm struggling to figure out. From a known list of servers, I need to gather up how many...
|
by: aine_canby |
last post by:
hi,
I have the following list -
how do I sort it like this -
|
by: james_027 |
last post by:
hi,
are there available library or pythonic algorithm for sorting a list
of list depending on the index of the list inside the list of my
choice?
d_list = ,
,
,
,
|
by: Jason |
last post by:
Hi folks--
Basically, I have a pressing need for a combination of 5.2 "Sorting a
List of Strings Case-Insensitively" & 5.3 "Sorting a List of Objects
by an Attribute of the Objects" from the...
|
by: ihimitsu |
last post by:
Hi friends
guide me
to sorting java list contains multiple list objects
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |