CODEWITHSUNDEEP
pythonlistsetintersectionset-intersection
Roberto Arriaga
Roberto Arriaga

Reputation: 1

Intersection of k ordered lists python

I am learning python and trying to intersect k sets (ordered lists) using SvS algorithm (small versus small). My program succeeds but I have to run the function several times until it reaches the intersection. I would be very grateful if you could give me a hint that I am doing wrong.

def SvS_BS(Set_list):
    Set_list = sorted(Set_list)
    candidato = Set_list[0]
    answer_set = []
    for S in Set_list:
        lS=0
        for S in Set_list:
            for e in candidato:
                b = BusquedaBinaria(S,0,len(S)-1,e)
                if b == -1:
                    candidato.remove(e)
                else: 
                    lS += b                
    return candidato

Note: BusquedaBinaria is Binary Search (is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one):

   def BusquedaBinaria( lista, izq, der, x):
    if der >= izq:
        m = izq + ( der-izq ) // 2
        if lista[m] == x:
            return m
        if lista[m] > x:
            return BusquedaBinaria(lista, izq,m - 1, x)
        return BusquedaBinaria(lista, m + 1, der, x)
    return -1

If I run the function with these examples:

A=[8, 316, 456, 802, 907, 1072, 1222, 1227, 1472, 1497, 1552, 1566, 1728, 2025, 2283, 2367, 2383, 2789, 3024, 3108, 3170, 3178, 3224, 3249, 3252]
B=[8, 1222, 10862, 18559, 28129, 41980, 43513, 44066]

The first output is:

SvS_BS([A,B])
output: [8, 907, 1222, 1552, 2283, 3024, 3224]

I run the function again and get:

output: [8, 1222, 3224]

Finally I run it again and get the output (which is the expected result)

output:[8, 1222]

I thank you in advance for you could help me to obtain the result in the first execution

Upvotes: 0

Views: 111

Answers (1)

devintark
devintark

Reputation: 76

I see a few things small mistakes in your code. First, you do two iterations for S in Set_List, only to reset the lS value (which you can do inside 1 loop) but then you never use that variable anyway.

Also, you check candidato List against itself in the loop, which you don't need to do, when you do for S in Set_List. So I changed to

for S in range(1,len(Set_list)):

Which will only iterate over the sets after the first one (candidate). Now you get an integer in S though, so I changed your binary search to

b = BusquedaBinaria(Set_list[S],0,len(Set_list[S])-1,e)

Now this should check the candidate Set against all the other Sets except itself.

Finally, the big problem(s) here I think are of design and one of technical. First technical: You delete from candidato as you're iterating over it, that's a bad idea and makes it skip values.

So, you want to check the first set against all other sets, so I would reverse the order of your loops as seen below. But you also have to make sure you're only returning values that are in all other lists. (I think you were close on this idea in that unused lS variable). Since you never actually use the position returned from your binary search, I made a successful find return a 1, and accumulate that in the b value. If that b value adds to the number of lists after searching all other lists (minus candidato), then it's in all lists and we add it to answer set. We then return answer set.

def BusquedaBinaria( lista, izq, der, x):
    if der >= izq:
        m = izq + ( der-izq ) // 2
        if lista[m] == x:
            return 1
        if lista[m] > x:
            return BusquedaBinaria(lista, izq,m - 1, x)
        return BusquedaBinaria(lista, m + 1, der, x)
    return -1

def SvS_BS_d(Set_list):
    Set_list = sorted(Set_list)
    comp_list_len = len(Set_list)-1
    candidato = Set_list[0]
    answer_set = []
    for e in candidato:
        b = 0
        for S in range(1, len(Set_list)):
            b += BusquedaBinaria(Set_list[S],0,len(Set_list[S])-1,e)
        if b == comp_list_len:
            answer_set.append(e)

    return answer_set

I think this should work, I tried it with an additional array as well but didn't do exhaustive edge case testing, let me know if works for you!

Upvotes: 1

Related Questions