449,323 Members | 1,291 Online Need help? Post your question and get tips & solutions from a community of 449,323 IT Pros & Developers. It's quick & easy.

# Finding the insertion point in a list

 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 yx[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 Replies

 P: n/a You might look at the bisect module (part of the standard distribution). Mar 16 '07 #2

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

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

 P: n/a On Mar 16, 2:32 pm, "Paul McGuire" 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

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

 P: n/a On Mar 16, 11:20 am, "Matimus" >from bisect import insortx = [0,100,200,1000]insort(x,10)x [0, 10, 100, 200, 1000] Mar 16 '07 #7

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

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

 P: n/a On Fri, 16 Mar 2007 18:17:08 -0800, Paul Rubin wrote: tk****@hotmail.com writes: >Or with a generator comprehensionn = sum ( y>x[i] for i in range(len(x)) ) - 1But there has to be a cleaner way, as the first approach is unwieldyand does not adapt to changing list lengths, and the second is notobvious 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. Mar 17 '07 #10

 P: n/a Steven D'Aprano

 P: n/a Steven D'Aprano 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. Mar 17 '07 #12

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

 P: n/a On Mar 17, 5:42 pm, Paul Rubin 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 Mar 17 '07 #14

 P: n/a Paul Rubin wrote: Steven D'Aprano or evenlen(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 Mar 17 '07 #15

 P: n/a On Mar 17, 9:46 pm, Steve Holden 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. Mar 17 '07 #16

 P: n/a On Mar 17, 4:12 am, "Martin Blume"

 P: n/a Steve Holden = 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

 P: n/a On Mar 18, 2:23 am, Paul Rubin

 P: n/a 7stud

### This discussion thread is closed

Replies have been disabled for this discussion. 