Finding the insertion point in a list

[tkpmep]

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

[Matimus]

You might look at the bisect module (part of the standard
distribution).

[kyosohma]

On Mar 16, 12:59 pm, [e-mail] 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

[Paul McGuire]

On Mar 16, 12:59 pm, [e-mail] 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

[kyosohma]

On Mar 16, 2:32 pm, "Paul McGuire" <[e-mail]:

On Mar 16, 12:59 pm, [e-mail] 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!

[7stud]

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

[Matimus]

On Mar 16, 11:20 am, "Matimus" <[e-mail]:

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]

[tobiaskk]

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.

[Paul Rubin]

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

[Steven D'Aprano]

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

[Paul Rubin]

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.

[Paul Rubin]

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.

[Martin Blume]

"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

[John Machin]

On Mar 17, 5:42 pm, Paul Rubin <http://[e-mail]:

Steven D'Aprano <[e-mail]:

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

[Steve Holden]

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 [phone] [phone]
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Recent Ramblings http://holdenweb.blogspot.com

[John Machin]

On Mar 17, 9:46 pm, Steve Holden <[e-mail]:

Paul Rubin wrote:

Steven D'Aprano <[e-mail]:

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.

[7stud]

On Mar 17, 4:12 am, "Martin Blume" <[e-mail]:

"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

for-else? Neat.

[Paul Rubin]

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)

[7stud]

On Mar 18, 2:23 am, Paul Rubin <http://[e-mail]:

Steve Holden <[e-mail]:

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?

[Alex Martelli]

7stud <bb**********@yahoo.comwrote:

On Mar 18, 2:23 am, Paul Rubin <http://[e-mail]:

Steve Holden <[e-mail]:

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