469,591 Members | 1,601 Online

# Finding the insertion point in a list

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

Mar 16 '07 #1
19 1880
You might look at the bisect module (part of the standard
distribution).

Mar 16 '07 #2
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 built-in 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

Mar 16 '07 #3
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
Mar 16 '07 #4
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!

Mar 16 '07 #5

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

Mar 16 '07 #6
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]

Mar 16 '07 #7
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.

Mar 16 '07 #8
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.

n = len([y t for t in x])
Mar 17 '07 #9
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.

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

Mar 17 '07 #10
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.
Mar 17 '07 #11
Steven D'Aprano <st***@REMOVE.THIS.cybersource.com.auwrites:
or even

len(filter(lambda t, y=y: y>t, x))

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.
Mar 17 '07 #12
"7stud" schrieb

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

Mar 17 '07 #13
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))

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

Mar 17 '07 #14
Paul Rubin wrote:
Steven D'Aprano <st***@REMOVE.THIS.cybersource.com.auwrites:
>or even

len(filter(lambda t, y=y: y>t, x))

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

Mar 17 '07 #15
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))
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.
Mar 17 '07 #16
On Mar 17, 4:12 am, "Martin Blume" <mbl...@socha.netwrote:
"7stud" schrieb
-----------
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
for-else? Neat.

Mar 17 '07 #17
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 Haskell-inspired 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)
Mar 18 '07 #18
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 Haskell-inspired 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?

Mar 18 '07 #19
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 Haskell-inspired 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
Mar 18 '07 #20

### This discussion thread is closed

Replies have been disabled for this discussion.