Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #55407

Re: Lowest Value in List

Show key headers only | View raw

subhabangalore@gmail.com wrote:

> Dear Group,
> 
> I am trying to work out a solution to the following problem in Python.
> 
> The Problem:
> Suppose I have three lists.
> Each list is having 10 elements in ascending order.
> I have to construct one list having 10 elements which are of the lowest
> value among these 30 elements present in the three given lists.
> 
> The Solution:
> 
> I tried to address the issue in the following ways:
> 
> a) I took three lists, like,
> list1=[1,2,3,4,5,6,7,8,9,10]
> list2=[0,1,2,3,4,5,6,7,8,9]
> list3=[-5,-4,-3,-2,-1,0,1,2,3,4]
> 
> I tried to make sum and convert them as set to drop the repeating
> elements: set_sum=set(list1+list2+list3)
> set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1, -5, -4, -3, -2])
> 
> In the next step I tried to convert it back to list as,
> list_set=list(set_sum)
> gave the value as,
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1, -5, -4, -3, -2]
> 
> Now, I imported heapq as,
> import heapq
> 
> and took the result as,
> result=heapq.nsmallest(10,list_set)
> it gave as,
> [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]
> 
> b) I am thinking to work out another approach.
> I am taking the lists again as,
> 
> list1=[1,2,3,4,5,6,7,8,9,10]
> list2=[0,1,2,3,4,5,6,7,8,9]
> list3=[-5,-4,-3,-2,-1,0,1,2,3,4]
> 
> as they are in ascending order, I am trying to take first four/five
> elements of each list,like,
> 
> list1_4=list1[:4]
>>>> list2_4=list2[:4]
>>>> list3_4=list3[:4]
> 
> Now, I am trying to add them as,
> 
> list11=list1_4+list2_4+list3_4
> 
> thus, giving us the result
> 
> [1, 2, 3, 4, 0, 1, 2, 3, -5, -4, -3, -2]
> 
> Now, we are trying to sort the list of the set of the sum as,
> 
> sort_sum=sorted(list(set(list11)))
> 
> giving us the required result as,
> 
> [-5, -4, -3, -2, 0, 1, 2, 3, 4]
> 
> If by taking the value of each list portion as 4 gives as less number of
> elements in final value, as we are making set to avoid repeating numbers,
> we increase element count by one or two and if final result becomes more
> than 10 we take first ten.
> 
> Are these approaches fine. Or should we think some other way.
> 
> If any learned member of the group can kindly let me know how to solve I
> would be helpful enough.

A bit late to the show here's my take. You could separate your problem into 
three simpler ones:

(1) combine multiple sequences into one big sequence
(2) filter out duplicate items
(3) find the largest items

(1) is covered by the stdlib:

items = itertools.chain.from_iterable([list1, list2, list3])

(2) is easy assuming the items are hashable:

def unique(items):
    seen = set()
    for item in items:
        if item not in seen:
            seen.add(item)
            yield item

items = unique(items)

(3) is also covered by the stdlib:

largest = heapq.nlargest(3, items)

This approach has one disadvantage: the `seen` set in unique() may grow 
indefinitely if the sequence passed to it is "long" and has an unlimited 
number of distinct duplicates.

So here's an alternative using a heap and a set both limited by the length 
of the result:

import heapq

def unique_nlargest(n, items):
    items = iter(items)
    heap = []
    seen = set()
    for item in items:
        if item not in seen:
            seen.add(item)
            heapq.heappush(heap, item)
            if len(heap) > n:
                max_discard = heapq.heappop(heap)
                seen.remove(max_discard)
                break
    for item in items:
        if item > max_discard and item not in seen:
            max_discard = heapq.heappushpop(heap, item)
            seen.remove(max_discard)
    return heap


if __name__ == "__main__":
    print(unique_nlargest(3, [1,2,3,4,5,4,3,2,1,6,2,7]))

I did not test it, so there may be bugs, but the idea behind the code is 
simple: you can remove from the set all items that are below the minimum 
item in the heap. Thus both lengths can never grow beyond n (or n+1 in my 
actual implementation).

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Lowest Value in List subhabangalore@gmail.com - 2013-10-02 03:04 -0700
  Re: Lowest Value in List Steven D'Aprano <steve@pearwood.info> - 2013-10-02 10:10 +0000
  Re: Lowest Value in List Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-02 12:42 +0200
  Re: Lowest Value in List dvghana@gmail.com - 2013-10-02 05:56 -0700
  Re: Lowest Value in List Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-02 19:35 +0530
  Re: Lowest Value in List Peter Otten <__peter__@web.de> - 2013-10-03 13:12 +0200

csiph-web