Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como calcular a intersecção de dois conjuntos de números com e sem pre-sorting?

+1 voto
93 visitas
perguntada Jul 6 em Ciência da Computação por IgorNascimento (51 pontos)  
Compartilhe

1 Resposta

+1 voto
respondida Jul 6 por IgorNascimento (51 pontos)  
editado Jul 7 por IgorNascimento

Considere o conjunto \(X\) formado com \(n\) valores \(x_i\) distintos e o conjunto \(Y\) formado com \(m\) valores \(y_i\) distintos.

Com base apenas nessas informações, o cálculo da intersecção entre os conjuntos pode ser feito percorrendo todo o conjunto \(Y\) para cada elemento existente em \(X\).

Dessa forma, a complexidade de um algoritmo para solucionar esse problema é \( \Theta(f(n,m)) =n*m\). O código a seguir é uma sugestão de implementação:

def intersect_forca_bruta(x,y):
    vec = []
    for i in range(len(x)):
        for j in range(len(y)):
            if (x[i] == y[j]):
                vec.append(x[i])
    return(vec)

Caso os conjuntos estejam pré ordenados, isto é, utilizando a estratégia de "transforme e conquiste", a complexidade do algoritmo é reduzida.

O código a seguir é uma exemplo de implementação.

def intersect_pre_sort(x,y): #  Em resposta ao comentário de Peng em 07/07/2017
    k = 1
    i = 0
    j = 0
    vec = []
    print("X = ",x)
    print("Y = ",y)

    while(i<len(x) and j<len(y)):
        if(k == 1):
            if(x[i]<y[j]):
                print("--------- Comparando valores de X no vetor Y (k=1) ----------------------------------")
                print("i=",i," e j=",j,"                                          ")
                print("x[",i,"]=",x[i],"<y[",j,"]=",y[j]," então vamos pular esse valor X:          ")
                print("i = i + 1 =",i+1, " e                                 ")
                print("agora vamos comparar valores de Y no vetor X               ")
                print("k = 0                                                      ")
                i = i + 1
                k = 0
            elif(x[i]==y[j]):
                print("--------- Comparando valores de X no vetor Y (k=1) ----------------------------------")
                print("i=",i," e j=",j,"                                          ")
                print("x[",i,"]=",x[i],"=y[",j,"]=",y[j]," então vamos armazenar esse valor e andar nos dois vetores:")
                print("i = i + 1  =",i+1, " e j = j + 1 =",j+1)
                print("vamos continuar comparando os valores de Y no vetor y               ")
                print("k = 1                                                      ")
                vec.append(x[i])
                i = i + 1
                j = j + 1
            else:
                print("--------- Comparando valores de X no vetor Y (k=1) ----------------------------------")
                print("i=",i," e j=",j,"                                          ")
                print("x[",i,"]=",x[i],">y[",j,"]=",y[j]," então vamos pular esse valor Y:          ")
                print("j = j + 1 -> j =",j+1, " e                                 ")
                print("vamos continuar comparando os valores de X no vetor Y               ")
                print("k = 1                                                      ")
                j = j + 1

        else:
            if(x[i]>y[j]):
                print("--------- Comparando valores de Y no vetor X (k=0) ----------------------------------")
                print("i=",i," e j=",j,"                                          ")
                print("x[",i,"]=",x[i],">y[",j,"]=",y[j]," então vamos pular esse valor Y:          ")
                print("j = j + 1  =",j+1, " e                                 ")
                print("agora vamos comparar valores de X no vetor Y               ")
                print("k = 1                                                      ")
                j = j + 1
                k = 1
            elif(x[i]==y[j]):
                print("--------- Comparando valores de Y no vetor X (k=0) ----------------------------------")
                print("i=",i," e j=",j,"                                          ")
                print("x[",i,"]=",x[i],"=y[",j,"]=",y[j]," então vamos armazenar esse valor e andar nos dois vetores:")
                print("i = i + 1 =",i+1, " e j = j + 1 =",j+1)
                print("vamos continuar comparando os valores de Y no vetor X               ")
                print("k = 0                                                      ")
                vec.append(x[i])
                i = i + 1
                j = j + 1
            else:
                print("--------- Comparando valores de Y no vetor X (k=0) ----------------------------------")
                print("i=",i," e j=",j,"                                          ")
                print("x[",i,"]=",x[i],">y[",j,"]=",y[j]," então vamos pular esse valor X:          ")
                print("i = i + 1 = ",i+1, " e                                 ")
                print("vamos continuar comparando os valores de Y no vetor X               ")
                print("k = 0      ")
                i = i + 1        
    return(vec)

Nessa estratégia, como os dados estão pré ordenados, é necessário passar apenas uma vez por cada elemento dos conjuntos. Na prática isso é feito por meio das comparação sucessivas somente entre \(x_i\) e \(y_j\), pois a relação \( i\) < \(k\) implica em \(x_i\) < \(x_k\) . O mesmo vale para o conjunto \(Y\).

Por tanto, a complexidade desse problema é, no máximo, \( O(f(n,m)) =n + m\) . O código a seguir é um exemplo para esse problema nas duas situações apresentadas.

if __name__ == '__main__': 

    print('Intersect com força bruta')
    x = [7 ,1 , 4 ,  2 ,  8]
    y = [4 , 5 , 2, 3 , 8]
    print(intersect_forca_bruta(x,y))
    print('Intersect com pre sorting')
    x = [1, 2 , 4 ,7 , 8]
    y = [2, 3 , 4 , 5 , 8]
   print(intersect_pre_sort(x,y))

Para ambos a solução é o conjunto [2 , 4, 8].

A seguir os detalhes gerados pela função de intersecção com pre-sorting.

X =  [1, 2, 4, 5, 7]
Y =  [2, 3, 4, 5, 8]
--------- Comparando valores de X no vetor Y (k=1) ----------------------------------
i= 0  e j= 0                                           
x[ 0 ]= 1 <y[ 0 ]= 2  então vamos pular esse valor X:          
i = i + 1 = 1  e                                 
agora vamos comparar valores de Y no vetor X               
k = 0                                                      
--------- Comparando valores de Y no vetor X (k=0) ----------------------------------
i= 1  e j= 0                                           
x[ 1 ]= 2 =y[ 0 ]= 2  então vamos armazenar esse valor e andar nos dois vetores:
i = i + 1 = 2  e j = j + 1 = 1
vamos continuar comparando os valores de Y no vetor X               
k = 0                                                      
--------- Comparando valores de Y no vetor X (k=0) ----------------------------------
i= 2  e j= 1                                           
x[ 2 ]= 4 >y[ 1 ]= 3  então vamos pular esse valor Y:          
j = j + 1  = 2  e                                 
agora vamos comparar valores de X no vetor Y               
k = 1                                                      
--------- Comparando valores de X no vetor Y (k=1) ----------------------------------
i= 2  e j= 2                                           
x[ 2 ]= 4 =y[ 2 ]= 4  então vamos armazenar esse valor e andar nos dois vetores:
i = i + 1  = 3  e j = j + 1 = 3
vamos continuar comparando os valores de Y no vetor y               
k = 1                                                      
--------- Comparando valores de X no vetor Y (k=1) ----------------------------------
i= 3  e j= 3                                           
x[ 3 ]= 5 =y[ 3 ]= 5  então vamos armazenar esse valor e andar nos dois vetores:
i = i + 1  = 4  e j = j + 1 = 4
vamos continuar comparando os valores de Y no vetor y               
k = 1                                                      
--------- Comparando valores de X no vetor Y (k=1) ----------------------------------
i= 4  e j= 4                                           
x[ 4 ]= 7 <y[ 4 ]= 8  então vamos pular esse valor X:          
i = i + 1 = 5  e                                 
agora vamos comparar valores de Y no vetor X               
k = 0  
comentou Jul 7 por Peng Yaohao (101 pontos)  
Boa solução, as implementações estão corretas, bem como o código disponibilizado para replicação. O exercício ilustra bem a ideia da "tranformação e conquista": transformar o problema original numa versão mais fácil de se resolver. No caso, a ordenação (cujo algoritmo mais eficiente tem complexidade média de \(\mathcal{O}(nlogn)\)) dispensa a necessidade de se comparar todos os possíveis pares dos dois conjuntos.

Como adendo final, sugiro inserir alguns comentários no código, em especial no "intersect_pre_sort", ou utilizar uma figura para ilustrar como o algoritmo está atacando o problema.
comentou Jul 7 por IgorNascimento (51 pontos)  
Obrigado pelos comentários Peng. Adicionei alguns prints que auxiliam acompanhar os passos do código.
...