Joins transpositions into one single cycle!

Dev Shed Forums Sponsor:

January 6th, 2013, 04:08 PM

Nightmareix35

Contributing User

Join Date: Nov 2012

Posts: 32

Time spent in forums: 8 h 42 m 41 sec
Reputation Power: 1

Joins transpositions into one single cycle!

Hey guys!

I was wondering, If I have a list of transpositions such this:

[(0, 11), (1, 5), (2, 18), (3, 21), (4, 24), (5, 7), (6, 0), (7, 12), (8, 25), (9, 4), (10, 14), (11, 9), (12, 3), (13, 2), (14, 27), (15, 6), (16, 10), (17, 16), (18, 1), (20, 8), (21, 23), (22, 15), (23, 19), (24, 26), (25, 22), (26, 13), (27, 20)]

what's the best way to join all of them into one cycle? - or ordered items - so it looks like this?

[17,16,10,14,27,20,8,25,22,15,6,0,11,9,4,24,26,13,2,18,1,5,7,12,3,21,23,19]

January 6th, 2013, 05:12 PM

Lux Perpetua

Contributing User

Dev Shed Intermediate (1500 - 1999 posts)

Join Date: Feb 2004

Location: San Francisco Bay

Posts: 1,936

Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312

I can sort of guess at what you want to do, but you really need to explain your problem better.

January 6th, 2013, 06:26 PM

Nightmareix35

Contributing User

Join Date: Nov 2012

Posts: 32

Time spent in forums: 8 h 42 m 41 sec
Reputation Power: 1

Quote:

Originally Posted by Lux Perpetua

I can sort of guess at what you want to do, but you really need to explain your problem better.

ok basically I have a list of tuples, each tuple contains a pair of numbers which represent the sequential order of them in the bigger sequence, for example, (1,3),(3,2) : one comes before three and three comes before two so the final sequence will appear as 1,3,2.

the lower bound of the given sequence is 17 (there's no number that comes before 17) - no pair such as (x , 17) which means 17 comes first for sure in the sequence and so on following the same rule.

its not quite the most comfy problem to explain but i hope ive been clear enough

)

January 6th, 2013, 08:38 PM

Nyktos

Contributing User

Join Date: Dec 2012

Posts: 76

Time spent in forums: 1 Day 3 h 26 m 10 sec
Reputation Power: 2

Off the top of my head, here's a basic idea of how you could go at it:

Code:

>>> d = dict([(0, 11), (1, 5), (2, 18), (3, 21), (4, 24), (5, 7)])
>>> d
{0: 11, 1: 5, 2: 18, 3: 21, 4: 24, 5: 7}
>>> d[0]
11

And so forth. Make your list of tuples into a dictionary, then access it with your number as a key to get the number that comes next.

Comments on this post

Lux Perpetua agrees: My solution would be similar.

January 6th, 2013, 09:58 PM

Lux Perpetua

Contributing User

Join Date: Feb 2004

Location: San Francisco Bay

Posts: 1,936

Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312

Here's a little trick to figure out which element should come first:

Code:

>>> input_list = [(0, 11), (1, 5), (2, 18), (3, 21), (4, 24), (5, 7),
...               (6, 0), (7, 12), (8, 25), (9, 4), (10, 14), (11, 9),
...               (12, 3), (13, 2), (14, 27), (15, 6), (16, 10),
...               (17, 16), (18, 1), (20, 8), (21, 23), (22, 15),
...               (23, 19), (24, 26), (25, 22), (26, 13), (27, 20)]
>>> next_map = dict(input_list)
>>> set(next_map.keys()) - set(next_map.values())
{17}
>>>

Comments on this post

Nightmareix35 agrees!

January 7th, 2013, 02:25 AM

Nightmareix35

Contributing User

Join Date: Nov 2012

Posts: 32

Time spent in forums: 8 h 42 m 41 sec
Reputation Power: 1

Quote:

Originally Posted by Nyktos

Off the top of my head, here's a basic idea of how you could go at it:

Code:

>>> d = dict([(0, 11), (1, 5), (2, 18), (3, 21), (4, 24), (5, 7)])
>>> d
{0: 11, 1: 5, 2: 18, 3: 21, 4: 24, 5: 7}
>>> d[0]
11

And so forth. Make your list of tuples into a dictionary, then access it with your number as a key to get the number that comes next.

Brilliant. Saved me from a 3 nested for loops. Exactly what I was looking for :]] thanks!

Joins transpositions into one single cycle!

Developer Shed Advertisers and Affiliates