By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,070 Members | 1,718 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,070 IT Pros & Developers. It's quick & easy.

Need a strange sort method...

P: n/a
I have a list and I need to do a custom sort on it...

for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.

a.sort(cmp)

print a
[1,4,7,10, 2,5,8, 3,6,9]

So withouth making this into an IQ test.
Its more like
1 4 7 10
2 5 8
3 6 9

Read that top to bottom from column 1 to column 4.
When you get to the bottom of a column move to the next column.
Get it?

Oct 16 '06 #1
Share this Question
Share on Google+
20 Replies


P: n/a
"SpreadTooThin" <bj********@gmail.comwrites:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.

a.sort(cmp)

print a
[1,4,7,10, 2,5,8, 3,6,9]
def k(n): return (n-1) % 3, (n-1) // 3
a.sort(key=k)
Oct 16 '06 #2

P: n/a
On 16 Oct 2006 11:13:08 -0700, SpreadTooThin <bj********@gmail.comwrote:
I have a list and I need to do a custom sort on it...

for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.

a.sort(cmp)

print a
[1,4,7,10, 2,5,8, 3,6,9]

So withouth making this into an IQ test.
Its more like
1 4 7 10
2 5 8
3 6 9
>>a = [1,2,3,4,5,6,7,8,9,10]
a.sort(key=lambda item: (((item-1) %3), item))
a
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

--
Cheers,
Simon B
si***@brunningonline.net
http://www.brunningonline.net/simon/blog/
Oct 16 '06 #3

P: n/a
SpreadTooThin wrote:
I have a list and I need to do a custom sort on it...
Its more like
1 4 7 10
2 5 8
3 6 9
that's trivial to do with slicing, of course. what makes you think you
need to do this by calling the "sort" method ?

</F>

Oct 16 '06 #4

P: n/a
On 10/16/06, Simon Brunning <si***@brunningonline.netwrote:
>a = [1,2,3,4,5,6,7,8,9,10]
a.sort(key=lambda item: (((item-1) %3), item))
a
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]
Re-reading the OP's post, perhaps sorting isn't what's required:
>>a[::3] + a[1::3] + a[2::3]
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

--
Cheers,
Simon B
si***@brunningonline.net
http://www.brunningonline.net/simon/blog/
Oct 16 '06 #5

P: n/a

SpreadTooThin wrote:
I have a list and I need to do a custom sort on it...

for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.

a.sort(cmp)

print a
[1,4,7,10, 2,5,8, 3,6,9]

So withouth making this into an IQ test.
Its more like
1 4 7 10
2 5 8
3 6 9

Read that top to bottom from column 1 to column 4.
When you get to the bottom of a column move to the next column.
Get it?
maybe the columnise function here would help:

http://www.gflanagan.net/site/python/utils/sequtils/

from math import sqrt

for i in range(2,12):
seq = range(1,i)
numcols = int(sqrt(len(seq)))
print columnise(seq, numcols)

[(1,)]
[(1, 2)]
[(1, 2, 3)]
[(1, 3), (2, 4)]
[(1, 3, 5), (2, 4, None)]
[(1, 3, 5), (2, 4, 6)]
[(1, 3, 5, 7), (2, 4, 6, None)]
[(1, 3, 5, 7), (2, 4, 6, 8)]
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
[(1, 4, 7, 10), (2, 5, 8, None), (3, 6, 9, None)]

--------------------------

def chunk( seq, size, pad=None ):
'''
Slice a list into consecutive disjoint 'chunks' of
length equal to size. The last chunk is padded if necessary.
>>list(chunk(range(1,10),3))
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>list(chunk(range(1,9),3))
[[1, 2, 3], [4, 5, 6], [7, 8, None]]
>>list(chunk(range(1,8),3))
[[1, 2, 3], [4, 5, 6], [7, None, None]]
>>list(chunk(range(1,10),1))
[[1], [2], [3], [4], [5], [6], [7], [8], [9]]
>>list(chunk(range(1,10),9))
[[1, 2, 3, 4, 5, 6, 7, 8, 9]]
>>for X in chunk([],3): print X
'''
n = len(seq)
mod = n % size
for i in xrange(0, n-mod, size):
yield seq[i:i+size]
if mod:
padding = [pad] * (size-mod)
yield seq[-mod:] + padding

def columnise( seq, numcols, pad=None ):
'''
>>columnise(range(1,10),3)
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
>>columnise(range(1,9),3)
[(1, 4, 7), (2, 5, 8), (3, 6, None)]
>>columnise(range(1,8),3)
[(1, 4, 7), (2, 5, None), (3, 6, None)]
'''
return zip( *chunk(seq, numcols, pad) )
-------------------------------

Gerard

Oct 16 '06 #6

P: n/a

SpreadTooThin wrote:
I have a list and I need to do a custom sort on it...

for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.

a.sort(cmp)

print a
[1,4,7,10, 2,5,8, 3,6,9]

So withouth making this into an IQ test.
Its more like
1 4 7 10
2 5 8
3 6 9

Read that top to bottom from column 1 to column 4.
When you get to the bottom of a column move to the next column.
Get it?
It's a little vague, but i'm supposing that if you have an 11 in a the
order will be:
[1,4,7,10, 2,5,8,11, 3, 6,9]
If this holds then your order is based on x%3. You place first all x
for which x%3 == 1, then x%3 == 2, and last x%3 == 0. And among these
three group you use "natural" order.
so:
def yourcmp(i,j):
ri = i%3
rj = j%3
if ri == rj: return i.__cmp__(j)
elif ri == 0: return 1
elif rj == 0: return -1
else: return ri.__cmp__(rj)
This works with your example, and with my assumption, feel free to
"optimize" the if/elif block.

However you shuold pay attention to the 0 behavior.
a = range(11)
a.sort(yourcmp)
print a
[1, 4, 7, 10, 2, 5, 8, 0, 3, 6, 9]

Oct 16 '06 #7

P: n/a
for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.
Well, if you're willing to give up doing it in a cmp() method,
you can do it as such:
>>a.sort()
chunk_size = 3
[a[i::chunk_size] for i in range(chunk_size)]
[[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]]

If you need it in a flat list, rather than as a list of
chunk_size lists (which are handy for iterating over in many
cases), there are ways of obtaining it, such as the hackish
>>sum([a[i::chunk_size] for i in range(chunk_size)], [])
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

There are likely good recipes for flattening a list. I just
happen not to have any at my fingertips.

I'm not sure it's possible to do in a cmp() method, given that it
requires apriori knowledge of the dataset (are the numbers
contiguous?). Unless, of course, you have such a list...

However, as a benefit, this method should work no matter what the
list contains, as long as they're comparable to each other for an
initial sorting:
>>a = [chr(ord('a') + i) for i in range(10)]
# a.sort() if it were needed
a
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
>>sum([a[i::chunk_size] for i in range(chunk_size)], [])
['a', 'd', 'g', 'j', 'b', 'e', 'h', 'c', 'f', 'i']
-tkc


Oct 16 '06 #8

P: n/a

Fredrik Lundh wrote:
SpreadTooThin wrote:
I have a list and I need to do a custom sort on it...
Its more like
1 4 7 10
2 5 8
3 6 9

that's trivial to do with slicing, of course. what makes you think you
need to do this by calling the "sort" method ?

</F>
You are of course correct.. There might be a way to do this with
slicing
and i % 3

Oct 16 '06 #9

P: n/a
On 2006-10-16, Tim Chase <py*********@tim.thechases.comwrote:
If you need it in a flat list, rather than as a list of
chunk_size lists (which are handy for iterating over in many
cases), there are ways of obtaining it, such as the hackish
>sum([a[i::chunk_size] for i in range(chunk_size)], [])
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

There are likely good recipes for flattening a list. I just
happen not to have any at my fingertips.
Actually, there isn't a good recipe in Python for flattening a
list. They all come out tasting like Circus Peanuts (Turkish
Delight for you non-Yanks).

--
Neil Cerutti
Oct 16 '06 #10

P: n/a

SpreadTooThin wrote:
that's trivial to do with slicing, of course. what makes you think you
need to do this by calling the "sort" method ?

</F>

You are of course correct.. There might be a way to do this with
slicing
and i % 3
Slicing will work only with a sorted list.

Oct 16 '06 #11

P: n/a
>>that's trivial to do with slicing, of course. what makes you think you
>>need to do this by calling the "sort" method ?

</F>
You are of course correct.. There might be a way to do this with
slicing
and i % 3

Slicing will work only with a sorted list.
But modulus arithmetic will only work with contiguous,
non-repeating numeric sequences...Funky things happen with
sequences like

[1,2,3,4,4,5,6,7,8,9,10] # "4" appears twice

or

[1,3,5,7,11,13,17,19,23,29]

where the position and the numeric value no longer correlate via
a simple modulus.

-tkc

Oct 16 '06 #12

P: n/a

Simon Brunning wrote:
On 10/16/06, Simon Brunning <si***@brunningonline.netwrote:
>>a = [1,2,3,4,5,6,7,8,9,10]
>>a.sort(key=lambda item: (((item-1) %3), item))
>>a
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

Re-reading the OP's post, perhaps sorting isn't what's required:
>a[::3] + a[1::3] + a[2::3]
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

--
Cheers,
Simon B
si***@brunningonline.net
http://www.brunningonline.net/simon/blog/
Ok so this is what I got.. but there is an odd side effect:

def reslice(series):
series.sort()
i = 1
newseries = series[::3]
while(1):
c = series[i::3]
if len(c) >= 3:
newseries = newseries + c
else:
break
i = i + 1
return newseries

a = [2,1,4,3,6,5,8,7,10,9]
b = reslice(a)
print b
>>[1, 4, 7, 10, 2, 5, 8, 3, 6, 9, 4, 7, 10]
I have one extra 10 that I shouldn't...

Oct 16 '06 #13

P: n/a

Gerard Flanagan wrote:
SpreadTooThin wrote:
I have a list and I need to do a custom sort on it...

for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order
1 4 7 10
2 5 8
3 6 9

from math import sqrt

for i in range(2,12):
seq = range(1,i)
numcols = int(sqrt(len(seq)))
print columnise(seq, numcols)
should be:

numcols = int(sqrt(len(seq) + 0.5)
Gerard

Oct 16 '06 #14

P: n/a

SpreadTooThin wrote:
Simon Brunning wrote:
On 10/16/06, Simon Brunning <si***@brunningonline.netwrote:
>a = [1,2,3,4,5,6,7,8,9,10]
>a.sort(key=lambda item: (((item-1) %3), item))
>a
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]
Re-reading the OP's post, perhaps sorting isn't what's required:
>>a[::3] + a[1::3] + a[2::3]
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

--
Cheers,
Simon B
si***@brunningonline.net
http://www.brunningonline.net/simon/blog/
Ok so this is what I got.. but there is an odd side effect:

def reslice(series):
series.sort()
i = 1
newseries = series[::3]
while(1):
c = series[i::3]
if len(c) >= 3:
newseries = newseries + c
else:
break
i = i + 1
return newseries

a = [2,1,4,3,6,5,8,7,10,9]
b = reslice(a)
print b
>[1, 4, 7, 10, 2, 5, 8, 3, 6, 9, 4, 7, 10]

I have one extra 10 that I shouldn't...

I think my loop termination is incorrect...
maybe I should just stop when my new series size is the same size as
the original?

Oct 16 '06 #15

P: n/a
"SpreadTooThin" <bj********@gmail.comwrites:
I have one extra 10 that I shouldn't...

I think my loop termination is incorrect...
It looks wrong to me; try your loop on range(20) and see what happens.
maybe I should just stop when my new series size is the same size as
the original?
You should make exactly 3 passes. You might also want to use
list.extend rather than adding lists. Finally, your function modifies
its input list (by sorting it), which generally is not nice unless the
caller expects it and wants it. You can save the caller some trouble
by making a sorted copy to work from.
Oct 16 '06 #16

P: n/a

Gerard Flanagan wrote:
Gerard Flanagan wrote:
SpreadTooThin wrote:
I have a list and I need to do a custom sort on it...
>
for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order
1 4 7 10
2 5 8
3 6 9
>
from math import sqrt

for i in range(2,12):
seq = range(1,i)
numcols = int(sqrt(len(seq)))
print columnise(seq, numcols)

should be:

numcols = int(sqrt(len(seq) + 0.5)
Feck! Missing a fecking bracket:

numcols = int(sqrt(len(seq)) + 0.5)

Oct 16 '06 #17

P: n/a

SpreadTooThin wrote:
SpreadTooThin wrote:
Simon Brunning wrote:
On 10/16/06, Simon Brunning <si***@brunningonline.netwrote:
>>a = [1,2,3,4,5,6,7,8,9,10]
>>a.sort(key=lambda item: (((item-1) %3), item))
>>a
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]
>
Re-reading the OP's post, perhaps sorting isn't what's required:
>
>a[::3] + a[1::3] + a[2::3]
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]
>
--
Cheers,
Simon B
si***@brunningonline.net
http://www.brunningonline.net/simon/blog/
Ok so this is what I got.. but there is an odd side effect:

def reslice(series):
series.sort()
i = 1
newseries = series[::3]
while(1):
c = series[i::3]
if len(c) >= 3:
newseries = newseries + c
else:
break
i = i + 1
return newseries

a = [2,1,4,3,6,5,8,7,10,9]
b = reslice(a)
print b
>>[1, 4, 7, 10, 2, 5, 8, 3, 6, 9, 4, 7, 10]
I have one extra 10 that I shouldn't...
Actually, you have an extra 4,7,10.
>

I think my loop termination is incorrect...
maybe I should just stop when my new series size is the same size as
the original?
You can do this automatically (and pass the size of the
desired sublist grouping also).

def strange(n,d):
""" n list to sort
d sublist length
"""
LoL = []
for i in xrange(d):
LoL.append(n[i::d])
print LoL
out = []
for i in LoL:
out.extend(i)
return out

a = [1,2,3,4,5,6,7,8,9,10]
b = [1,3,5,7,11,13,17,19,23,29]
c = [1,2,3,4,4,5,6,7,8,9,10]
d = [1,2]

print a
test = strange(a,3)
print test
print

print a
test = strange(a,4)
print test
print

print a
test = strange(a,5)
print test
print

print b
test = strange(b,3)
print test
print

print c
test = strange(c,3)
print test
print

print d
test = strange(d,5)
print test
print

## [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
## [[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]]
## [1, 4, 7, 10, 2, 5, 8, 3, 6, 9]
##
## [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
## [[1, 5, 9], [2, 6, 10], [3, 7], [4, 8]]
## [1, 5, 9, 2, 6, 10, 3, 7, 4, 8]
##
## [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
## [[1, 6], [2, 7], [3, 8], [4, 9], [5, 10]]
## [1, 6, 2, 7, 3, 8, 4, 9, 5, 10]
##
## [1, 3, 5, 7, 11, 13, 17, 19, 23, 29]
## [[1, 7, 17, 29], [3, 11, 19], [5, 13, 23]]
## [1, 7, 17, 29, 3, 11, 19, 5, 13, 23]
##
## [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10]
## [[1, 4, 6, 9], [2, 4, 7, 10], [3, 5, 8]]
## [1, 4, 6, 9, 2, 4, 7, 10, 3, 5, 8]
##
## [1, 2]
## [[1], [2], [], [], []]
## [1, 2]

Oct 16 '06 #18

P: n/a

Tim Chase wrote:
for example:
a = [1,2,3,4,5,6,7,8,9,10] #Although not necessarily in order

def cmp(i,j): #to be defined in this thread.

Well, if you're willing to give up doing it in a cmp() method,
you can do it as such:
>>a.sort()
>>chunk_size = 3
>>[a[i::chunk_size] for i in range(chunk_size)]
[[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]]

If you need it in a flat list, rather than as a list of
chunk_size lists (which are handy for iterating over in many
cases), there are ways of obtaining it, such as the hackish
>>sum([a[i::chunk_size] for i in range(chunk_size)], [])
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

There are likely good recipes for flattening a list. I just
happen not to have any at my fingertips.

I'm not sure it's possible to do in a cmp() method, given that it
requires apriori knowledge of the dataset (are the numbers
contiguous?). Unless, of course, you have such a list...

However, as a benefit, this method should work no matter what the
list contains, as long as they're comparable to each other for an
initial sorting:
>>a = [chr(ord('a') + i) for i in range(10)]
>># a.sort() if it were needed
>>a
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
>>sum([a[i::chunk_size] for i in range(chunk_size)], [])
['a', 'd', 'g', 'j', 'b', 'e', 'h', 'c', 'f', 'i']
-tkc

Yes this is excellent...
Doh... How easy was that! :)
[a[i::chunk_size] for i in range(chunk_size)]

Oct 16 '06 #19

P: n/a
Neil Cerutti wrote:
On 2006-10-16, Tim Chase <py*********@tim.thechases.comwrote:
>If you need it in a flat list, rather than as a list of
chunk_size lists (which are handy for iterating over in many
cases), there are ways of obtaining it, such as the hackish
>>>>sum([a[i::chunk_size] for i in range(chunk_size)], [])
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

There are likely good recipes for flattening a list. I just
happen not to have any at my fingertips.

Actually, there isn't a good recipe in Python for flattening a
list. They all come out tasting like Circus Peanuts (Turkish
Delight for you non-Yanks).

Here's two that I came up with. They are both very fast compared to anything
else I've seen. Maybe they won't taste so much like Peanuts. :-)
def flatten(L):
""" Flatten a list in place.
"""
i = 0
while i < len(L):
while type(L[i]) is list:
L[i:i+1] = L[i]
i += 1
return L

def sflatten(sequence):
""" Return a flattened sequence as a list.
"""
def iterinner(seq):
for s in seq:
if hasattr(s, '__iter__'):
for i in iterinner(s):
yield i
else:
yield s
return list(iterinner(sequence))

Cheers,
Ron Adam
Oct 17 '06 #20

P: n/a
Ron Adam wrote:
Neil Cerutti wrote:
>On 2006-10-16, Tim Chase <py*********@tim.thechases.comwrote:
>>If you need it in a flat list, rather than as a list of
chunk_size lists (which are handy for iterating over in many
cases), there are ways of obtaining it, such as the hackish

>sum([a[i::chunk_size] for i in range(chunk_size)], [])
[1, 4, 7, 10, 2, 5, 8, 3, 6, 9]

There are likely good recipes for flattening a list. I just
happen not to have any at my fingertips.

Actually, there isn't a good recipe in Python for flattening a
list. They all come out tasting like Circus Peanuts (Turkish
Delight for you non-Yanks).


Here's two that I came up with. They are both very fast compared to
anything else I've seen. Maybe they won't taste so much like Peanuts.
:-)
def flatten(L):
""" Flatten a list in place.
"""
i = 0
while i < len(L):
while type(L[i]) is list:
L[i:i+1] = L[i]
i += 1
return L

def sflatten(sequence):
""" Return a flattened sequence as a list.
"""
def iterinner(seq):
for s in seq:
if hasattr(s, '__iter__'):
for i in iterinner(s):
yield i
else:
yield s
return list(iterinner(sequence))
Woops, cut the wrong one... Replace sflatten above with the following.
def flattened(seq):
""" Return a flattened sequence as a list.
"""
def visit(a, x):
for i in x:
if not hasattr(i, '__iter__'):
a.append(i)
else:
visit(a, i)
a = []
visit(a, seq)
return a

>
Cheers,
Ron Adam
Oct 17 '06 #21

This discussion thread is closed

Replies have been disabled for this discussion.