Need a strange sort method...

[SpreadTooThin]

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?

[Paul Rubin]

"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)

[Simon Brunning]

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/

[Fredrik Lundh]

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>

[Simon Brunning]

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/

[Gerard Flanagan]

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

[Saizan]

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]

[Tim Chase]

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

[SpreadTooThin]

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

[Neil Cerutti]

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

[Saizan]

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.

[Tim Chase]

>>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

[SpreadTooThin]

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...

[Gerard Flanagan]

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

[SpreadTooThin]

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?

[Paul Rubin]

"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.

[Gerard Flanagan]

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)

[mensanator]

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]

[SpreadTooThin]

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)]

[Ron Adam]

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

[Ron Adam]

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