stripes

Você realmente consegue juntar duas ou mais listas em uma?

Uma situação relativamente rotineira é a necessidade de juntarmos duas coleções de dados em uma só. Por exemplo: temos um array A = [1, 2] e queremos juntá-lo com B = [3, 4], parar formar um C = [1, 2, 3, 4]. Para este caso, não há nenhum mistério e a solução é bem trivial. Nosso caso é um pouco diferente.

Obs.: Em python, se resumiria a C = A + B

Problema:

Escreva uma função que combine duas listas em uma, alternando entre seus elementos. Ex.: A = [1, 2], B = [3, 4] -> [1, 3, 2, 4]

Entrada:

  • Duas listas, A e B, de tamanho n, onde 0 >= n <= 100

Saída:

  • Uma lista L, de tamanho n * 2,  cujos elementos correspondem as itens alternados de A e B.

Antes de ler o resto, sugiro que você pare um pouco e tente formular uma solução, mesmo que em pseudocódigo.


Casos de testes e exemplos:

O formato usado para descrição é de: ƒ(Entrada) -> Saída.

Retorna a combinação intercalada das entradas

ƒ([1, 2], [‘a’, ‘b’]) -> [1, ‘a’, 2, ‘b’]

A combinação de duas listas vazias, é uma lista vazia

ƒ([], []) -> []

Se as duas listas tiverem tamanhos diferentes, retorna um erro

ƒ([1, 2, 3], [1, 2]) -> Error

Não faz distinção entre o valor dos itens

ƒ([‘a’, ‘a’, 1,  {}], [‘a’, ‘a’, ‘1’, []]) -> [‘a’, ‘a’, ‘a’, ‘a’, 1, ‘1’, {}, []]

Tendo em vista os exemplos acima e a descrição, já temos condições de observar que L = [A[0], B[0], A[1], B[1],…, A[n], B[n]].

Em python, podemos utilizar a função built-in zip que  ao receber dois iteráveis (no nosso caso, listas) como entrada, retorna um iterável de tuplas, onde a i-ésima tupla, corresponde aos i-ésimos elementos das listas de entrada, resultando em  L’ = [ (A[0], B[0]) , (A[1], B[1]) ,…, (A[n], B[n])] que é uma estrutura bem próxima da que nós queremos. Nosso propósito agora é transformar a estrutura de L’em L e, para isso, usaremos chain do módulo itertools.

from itertools import chain

# listas mocks exemplificando o primeiro teste
l1 = ['a', 'b']
l2 = [1, 2]

list_comb = list(chain.from_iterable(zip(l1, l2)))

assert list_comb == alternate_comb(l1, l2)

programming-languages

Com isso, já sabemos o python way de se lidar com esse tipo de problema no dia-a-dia. Mas, como o objetivo aqui não é só falar sobre a linguagem, vamos escrever nossa solução!

Solução com duas listas

def alternate_comb(first: list, second: list) -> list:
    assert len(first) == len(second)

    n = len(first)
    combined = []

    for i in range(n):
        combined.append(first[i])
        combined.append(second[i])

    return combined

As duas listas devem ter a mesma quantidade de elementos. Para isso, uma verificação é feita na segunda linha.

    assert len(first) == len(second)

Inicializamos uma lista vazia combined, que será retornada após as operações de combinação que adicionarão os itens de first e second. Agora basta iterar por valores de i de 0 até n e adicionar a combined a cada iteração, através do método append, o i-ésimo item de first e second. Ao final deste laço, temos nossa resposta em combined.

for i in range(n):
    combined.append(first[i])
    combined.append(second[i])

Podemos “melhorar” essa solução? O trecho acima pode ser substituído por uma forma mais pythonica, que deixa o código um pouco mais limpo.

for i in range(n):
    combined += first[i], second[i]

Essa é somente uma das soluções possíveis, mas não é tão interessante assim, né? Vamos utilizar algumas coisas mais bacanas em uma outra solução possível deste problema 🙂

Ao longo desta solução, conseguimos observar que o padrão que queremos chegar é o de L = [A[0], B[0], A[1], B[1],…, A[n], B[n]], mas será que não é possivel chegar a essa resposta com um nível maior de abstração utilizando um pouco de matemática?

Neste caso, temos 2 listas. Vamos considerar A como a lista 0, e B como 1 e descrever L de uma forma um pouco diferente: L = [lists[0][0], lists[1][0], lists[0][1], lists[1][1], …,lists[0][n], lists[1][n]]. Dessa forma, só precisamos saber quais expessões geram m e n para lists[m][n] e poderemos então pensar em uma nova forma para gerar L.

Sabemos que o tamanho de L será n * 2, então, para sabermos se A ou B deve ser a lista para a i-ésima posição, basta utilizar o resto da divisão de i por 2 (quantidade de listas). Para sabermos qual índice de A ou B corresponde a i-ésima posição de L, basta utilizarmos a parte inteira da divisão de i por 2(quantidade de listas).

Que para listas 2 de 3 elementos resulta em:

i=0, n=2 -> (i % n) = 0 e (i / n) = 0
i=1, n=2 -> (i % n) = 1 e (i / n) = 0
i=2, n=2 -> (i % n) = 0 e (i / n) = 1
i=3, n=2 -> (i % n) = 1 e (i / n) = 1
i=4, n=2 -> (i % n) = 0 e (i / n) = 2
i=5, n=2 -> (i % n) = 1 e (i / n) = 2

Agora que já sabemos como acessar as listas corretas e seus respectivos indices na hora certa, fica fácil condensar uma solução:

def alternate_comb(first: list, second: list) -> list:
    assert len(first) == len(second)

    lists = (first, second)
    final_length = len(first) * 2

    return [lists[i % 2][int(i / 2)] for i in range(final_length)]

Vale lembrar que a linha 7 é equivalente a:

    combined = []
    for i in range(final_length):
        combined.append(lists[i % 2][int(i / 2)])
    return combined

Vamos dar um passo adiante, aproveitar essa solução e gerar uma função capaz de fazer o mesmo para 3, 4, 5,… n listas de entrada!

Solução para n listas

Com poucas modificações, somos capazes de criar uma solução que comporta n listas como entrada:

def alternate_comb_nlists(*lists) -> list:
    list_itens_count = len(lists[0])

    for l in lists[1:]:
        assert len(l) == list_itens_count

    n = len(lists)
    final_length = list_itens_count * n

    return [lists[i % n][int(i / n)] for i in range(final_length)]

Desta forma, podemos chamar alternate_comb_nlists com quantos argumentos quisermos, desde que todos sejam listas com a mesma quantidade de elementos.

l1 = ['a', 'b', 'c']
l2 = [1, 2, 3]
l3 = [5.0, 6.0, 7.0]
l4 = [[], {}, 'x']

print(alternate_comb_nlists(l1, l2))
>>> ['a', 1, 'b', 2, 'c', 3]

print(alternate_comb_nlists(l1, l2, l3))
>>> ['a', 1, 5.0, 'b', 2, 6.0, 'c', 3, 7.0]

print(alternate_comb_nlists(l1, l2, l3, l4))
>>> ['a', 1, 5.0, [], 'b', 2, 6.0, {}, 'c', 3, 7.0, 'x']

Conclusão

Espero que tenham gostado do desafio :). Qualquer dúvida, crítica ou correção, entre em contato e deixe seu feedback para que eu possa aparar arestas e dar uma melhor forma aos posts.

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s