P: n/a

I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:
if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) )  1
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.
Sincerely
Thomas Philips  
Share this Question
P: n/a

You might look at the bisect module (part of the standard
distribution).  
P: n/a

On Mar 16, 12:59 pm, tkp...@hotmail.com wrote:
I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:
if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) )  1
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.
Sincerely
Thomas Philips
One way to do this would be to use the cmp builtin and loop over the
items in the list. Maybe something like this:
x = [0, 100, 200, 1000]
numLst = len(x)
count = 0
for i in range(numLst):
resultOfCmp = cmp(newNum, x[count])
if resultOfCmp == 1:
print i
x.insert(count, newNum)
break
count += 1
# Where newNum is the one to be inserted.
It's a hack, but it might get the ol' creative juices flowing.
Mike  
P: n/a

On Mar 16, 12:59 pm, tkp...@hotmail.com wrote:
I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:
if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) )  1
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.
Sincerely
Thomas Philips
List "will typically have 2 to 5 items"? Keep it simple!
x.append(y)
x.sort()
 Paul  
P: n/a

On Mar 16, 2:32 pm, "Paul McGuire" <p...@austin.rr.comwrote:
On Mar 16, 12:59 pm, tkp...@hotmail.com wrote:
I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
positive integer y, I want to determine its appropriate position in
the list (i.e the point at which I would have to insert it in order to
keep the list sorted. I can clearly do this with a series of if
statements:
if y<x[1]:
n = 0
elif y < x[2]:
n = 1
elif y < x[3]:
n = 2
else:
n = 3
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) )  1
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
My list will typically have 2 to 5 items, so speed is not a huge
issue. I'd appreciate your guidance.
Sincerely
Thomas Philips
List "will typically have 2 to 5 items"? Keep it simple!
x.append(y)
x.sort()
 Paul
I thought doing an append and sort was a good idea too, but the
question entailed knowing the insertion point, so I skipped it.
Thanks!  
P: n/a

How about:

x = [0, 100, 200, 1000]
y = 1
inserted = False
for i in range(len(x)):
if(y <= x[i]):
x.insert(i, y)
inserted = True
break
if(not inserted): x.append(y)
print x
  
P: n/a

On Mar 16, 11:20 am, "Matimus" <mccre...@gmail.comwrote:
You might look at the bisect module (part of the standard
distribution).
Here is an example:
>>from bisect import insort x = [0,100,200,1000] insort(x,10) x
[0, 10, 100, 200, 1000]  
P: n/a

Or like this:
x = [0, 100, 200, 1000]
y = 435
for n, i in enumerate(x):
if y < i:
n = n  1
break
x.insert(n + 1, y)
If you decide to stick with
n = sum ( y>x[i] for i in range(len(x)) )  1
Replace it with:
n = sum(y i for i in x)  1
Tobias K.  
P: n/a
 tk****@hotmail.com writes:
Or with a generator comprehension
n = sum ( y>x[i] for i in range(len(x)) )  1
But there has to be a cleaner way, as the first approach is unwieldy
and does not adapt to changing list lengths, and the second is not
obvious to a casual reader of the code.
How about :
n = len([y t for t in x])  
P: n/a

On Fri, 16 Mar 2007 18:17:08 0800, Paul Rubin wrote: tk****@hotmail.com writes:
>Or with a generator comprehension n = sum ( y>x[i] for i in range(len(x)) )  1
But there has to be a cleaner way, as the first approach is unwieldy and does not adapt to changing list lengths, and the second is not obvious to a casual reader of the code.
How about:
n = len([y t for t in x])
(1) It's wrong. That always returns the length of the list. Perhaps you
meant something like this?
len(["anything will do" for t in x if y t])
or even
len(filter(lambda t, y=y: y>t, x))
(2) It's barely more comprehensible than the alternative that the Original
Poster rejected for being insufficiently clear.
Since (almost) everyone insists on ignoring the bisect module and
reinventing the wheel, here's my wheel:
def find(alist, n):
"""Return the position where n should be inserted in a sorted list."""
if alist != sorted(alist):
raise ValueError('list must be sorted')
where = None
for i in range(len(alist)):
if where is not None:
break
alist.insert(i, n)
if alist == sorted(alist):
where = i
del alist[i]
if where is None:
where = len(alist)
return where
Here's another dodgy implementation:
def find(alist, n):
return sorted(alist + [n]).index(n)
It's especially good for large lists. Not!

Steven.  
P: n/a

Steven D'Aprano <st***@REMOVE.THIS.cybersource.com.auwrites:
(1) It's wrong. That always returns the length of the list. Perhaps you
meant something like this?
len(["anything will do" for t in x if y t])
Yeah, that's what I meant.  
P: n/a

Steven D'Aprano <st***@REMOVE.THIS.cybersource.com.auwrites:
or even
len(filter(lambda t, y=y: y>t, x))
How about
min(i for i,t in enumerate(x) if t >= y)
or
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.  
P: n/a

"7stud" schrieb
How about:

x = [0, 100, 200, 1000]
y = 1
inserted = False
for i in range(len(x)):
if(y <= x[i]):
x.insert(i, y)
inserted = True
break
if(not inserted): x.append(y)
print x

You can get rid of the sentinel "inserted" using the
else clause of the for loop:
for i in range(len(x)):
if (y <= x[i]):
x.insert(i, y)
break
else: x.append(y)
Python is cool :)
IMHO. HTH.
Martin  
P: n/a

On Mar 17, 5:42 pm, Paul Rubin <http://phr...@NOSPAM.invalidwrote:
Steven D'Aprano <s...@REMOVE.THIS.cybersource.com.auwrites:
or even
len(filter(lambda t, y=y: y>t, x))
How about
min(i for i,t in enumerate(x) if t >= y)
or
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.
I'd hate to see "indirect". Worse, the minusing gizmoid crashes when
y x[1]  all your ifs are belong to False.
>>x
[0, 100, 200, 1000]
>>tests = [0, 1, 100, 150, 1000, 2000] [(y, max(i for i,t in enumerate(x) if t <= y)) for y in tests]
[(0, 0), (1, 0), (100, 1), (150, 1), (1000, 3), (2000, 3)]
Looks OK, iff one is happy with the OP's strange usage of "insert
point".
>>xc = x[:] xc.insert(1, 150) xc
[0, 150, 100, 200, 1000]
Whoops.
Try this for size:
>>[(y, sum(t <= y for t in x)) for y in tests]
[(0, 1), (1, 1), (100, 2), (150, 2), (1000, 4), (2000, 4)]
Cheers,
John  
P: n/a

Paul Rubin wrote:
Steven D'Aprano <st***@REMOVE.THIS.cybersource.com.auwrites:
>or even
len(filter(lambda t, y=y: y>t, x))
How about
min(i for i,t in enumerate(x) if t >= y)
or
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.
How about a solution (like the bisect one suggested almost as soon as
this thread started) that doesn't iterate over the whole list.
Having said which, for the promoted use cases I agree that the append()
and sort() paradigm wins hands down until it starts to make a real and
observable difference to the run time.
regards
Steve

Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Recent Ramblings http://holdenweb.blogspot.com  
P: n/a

On Mar 17, 9:46 pm, Steve Holden <s...@holdenweb.comwrote:
Paul Rubin wrote:
Steven D'Aprano <s...@REMOVE.THIS.cybersource.com.auwrites:
or even
len(filter(lambda t, y=y: y>t, x))
How about
min(i for i,t in enumerate(x) if t >= y)
or
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.
How about a solution (like the bisect one suggested almost as soon as
this thread started) that doesn't iterate over the whole list.
Having said which, for the promoted use cases I agree that the append()
and sort() paradigm wins hands down until it starts to make a real and
observable difference to the run time.
Unfortunately for sort/append, the OP wants to find the insertion
point  he hasn't mentioned actually doing the insertion.  
P: n/a

On Mar 17, 4:12 am, "Martin Blume" <mbl...@socha.netwrote:
"7stud" schrieb
How about:

x = [0, 100, 200, 1000]
y = 1
inserted = False
for i in range(len(x)):
if(y <= x[i]):
x.insert(i, y)
inserted = True
break
if(not inserted): x.append(y)
print x

You can get rid of the sentinel "inserted" using the
else clause of the for loop:
for i in range(len(x)):
if (y <= x[i]):
x.insert(i, y)
break
else: x.append(y)
Python is cool :)
IMHO. HTH.
Martin
forelse? Neat.  
P: n/a

Steve Holden <st***@holdenweb.comwrites:
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.
How about a solution (like the bisect one suggested almost as soon as
this thread started) that doesn't iterate over the whole list.
Here's a Haskellinspired one:
len(list(itertools.takewhile(lambda t: y t, x)))
It stops iterating when it hits an element >= y. I originally wanted
to write the above as:
len(itertools.takewhile(y.__gt__, x))
but it looks like regular numbers only support __cmp__ and not rich
comparison, and also you can't take the length of an iterator. In
Haskell this type of thing is very natural:
length(takeWhile (y >) x)  
P: n/a

On Mar 18, 2:23 am, Paul Rubin <http://phr...@NOSPAM.invalidwrote:
Steve Holden <s...@holdenweb.comwrites:
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.
How about a solution (like the bisect one suggested almost as soon as
this thread started) that doesn't iterate over the whole list.
Here's a Haskellinspired one:
len(list(itertools.takewhile(lambda t: y t, x)))
Can you explain how list() works in that statement. I looked up
takewhile() and it returns an iterator that will automatically stop at
the insertion point? So does list() do an internal comprehension with
the iterator?  
P: n/a

7stud <bb**********@yahoo.comwrote:
On Mar 18, 2:23 am, Paul Rubin <http://phr...@NOSPAM.invalidwrote:
Steve Holden <s...@holdenweb.comwrites:
max(i for i,t in enumerate(x) if t <= y)
Those are actually pretty direct.
How about a solution (like the bisect one suggested almost as soon as
this thread started) that doesn't iterate over the whole list.
Here's a Haskellinspired one:
len(list(itertools.takewhile(lambda t: y t, x)))
Can you explain how list() works in that statement. I looked up
takewhile() and it returns an iterator that will automatically stop at
the insertion point? So does list() do an internal comprehension with
the iterator?
Any call to list(iterator) works roughly as follows:
def likelist(iterator):
result = []
while True:
try: result.append(iterator.next())
except StopIteration: return result
Alex   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1757
 replies: 19
 date asked: Mar 16 '07
