Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Wed, 02 Oct 2013 12:42:06 +0200
From: Antoon Pardon <antoon.pardon@rece.vub.ac.be>
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:10.0.12) Gecko/20130116 Icedove/10.0.12
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Lowest Value in List
References: <dc6edb07-4f5a-4b1a-aa40-b287325196a2@googlegroups.com>
In-Reply-To: <dc6edb07-4f5a-4b1a-aa40-b287325196a2@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.608.1380710528.18130.python-list@python.org>
Lines: 93
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:55301

Op 02-10-13 12:04, subhabangalore@gmail.com schreef:
> 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.

You may consider a merge phase from the merge sort. Something like the
following: (Pseudo code; not tested)

iters = [iter(list1), iter(list2), iter(list3)]
heads = [(itr.next() for itr in Iters]

index, value = find_smallest_from(heads) # This function finds the
smalles value and returns it with its index

last = value
result = [value]
heads[index] = iters[index].next()
while len(results) < 10:
    index, value = find_smallest_from(heads)
    if value == last:
        continue
    last = value
    result.append(value)
    heads[index] = iters[index].next()