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

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

 

[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 for i in range(len(x)) ) - 1

Replace it with:

n = sum(y > i for i in x) - 1

Tobias K.

 

[Paul McGuire]

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

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

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):
x.insert(i, y)
inserted = True
break
if(not inserted): x.append(y)

print x
------------

 

[Matimus]

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]

 

[Paul Rubin]

Or with a generator comprehension
n = sum ( y>x 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]

Or with a generator comprehension
n = sum ( y>x 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
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!

 

[Paul Rubin]

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

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]

How about:

-----------
x = [0, 100, 200, 1000]
y = -1
inserted = False

for i in range(len(x)):
if(y <= x):
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):
x.insert(i, y)
break
else: x.append(y)

Python is cool

IMHO. HTH.
Martin

 

[John Machin]

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]

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

 

[John Machin]

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]

How about:

for i in range(len(x)):
if(y <= x):
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):
x.insert(i, y)
break
else: x.append(y)

Python is cool

IMHO. HTH.
Martin

for-else? Neat.

 

[Paul Rubin]

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]

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]

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