Python: Como gerar todas as combinações de listas de tuplas sem repetir o conteúdo da tupla

9

Estou trabalhando com um enigma:

Dado um dicionário com tuplas de chaves: dictionary = {(p,q):n} , eu preciso gerar uma lista de novos dicionários de cada combinação, de modo que nem p nem q repitam dentro do novo dicionário. E durante a geração dessa lista de dicionários, ou depois, escolha um dos dicionários como o desejado, com base em um cálculo usando os valores do dicionário.

exemplo do que quero dizer (mas muito menor):

dictionary = {(1,1): 1.0, (1,2): 2.0, (1,3): 2.5, (1,4): 5.0, (2,1): 3.5, (2,2): 6.0, (2,3): 4.0, (2,4): 1.0}

torna-se

listofdictionaries = [{(1,1): 1.0, (2,2): 6.0}, {(1,1): 1.0, (2,3): 4.0}, (1,1): 1.0, (2,4): 1.0}, {(1,2): 2.0, (2,1): 3.5}, {(1,2): 2.0, (2,3): 4.0}, etc.

um dicionário como: {(1,1): 1.0, (2,1): 3.5} não é permitido porque q repete.

Agora, minha história triste: sou novo na codificação ... mas estou tentando escrever esse script para analisar alguns dos meus dados. Mas também acho que é um enigma de algoritmo interessante. Eu escrevi algo que funciona com dicionários muito pequenos, mas quando eu digito um grande, ele demora muito para ser executado (copiado abaixo). Na tentativa do meu script, na verdade, eu criei uma lista de combinações de tuplas que eu uso para me referir ao meu dicionário mestre mais tarde no script. Vou copiá-lo abaixo:

As chaves da tupla do dicionário foram geradas usando duas listas: "ExpList1" e "ExpList2"

#first, I generate all the tuple combinations from my ExpDict dictionary
combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2))))

#then I generate a list of only the combinations that don't repeat p or q
uniquecombolist = []
for foo in combos:
    counter = 0
    listofp = []
    listofq = []
    for bar in foo:
        if bar[0] in listofp or bar[1] in listofq:
            counter=+1
            break
        else:
            listofp.append(bar[0])
            listofq.append(bar[1])
    if counter == 0:
        uniquecombolist.append(foo)

Após gerar esta lista, eu aplico uma função a todas as combinações de dicionário (iterando através das listas de tuplas e chamando seus respectivos valores do dicionário mestre) e escolho a combinação com o menor valor resultante daquela função.

Eu também tentei aplicar a função enquanto iterava as combinações escolhendo as únicas p, q e então verificando se o valor resultante é menor que o anterior e mantendo-o se é (isso é ao invés de gerar aquela lista "uniquecombolist ", Acabo gerando apenas a lista final de tupla) - ainda demora muito.

Eu acho que a solução é incorporar a função p, q-no-repeat e a seleção final DURANTE a geração de combinações. Eu estou apenas tendo problemas para entender como realmente fazer isso.

Obrigado pela leitura! Sara

EDITAR:

Para esclarecer, eu escrevi uma alternativa ao meu código que incorpora a função final (basicamente quadrados médios) aos conjuntos de pares.

'combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2))))


prevRMSD = float('inf')
for foo in combos:
    counter = 0
    distanceSUM = 0
    listofp = []
    listofq = []
    for bar in foo:
        if bar[0] in listofp or bar[1] in listofq:
            counter=+1
            break
        else:
            listofp.append(bar[0])
           listofq.append(bar[1])
        distanceSUM = distanceSUM + RMSDdict[bar]
    RMSD = math.sqrt (distanceSUM**2/len(foo))
    if counter == 0 and RMSD< prevRMSD:
        chosencombo = foo
        prevRMSD = RMSD'

Então, se eu pudesse incorporar o cálculo do RMS durante a geração do conjunto e apenas manter o menor, acho que isso resolveria o meu problema combinatório.

    
por Sara 04.10.2017 в 04:31
fonte

2 respostas

1

Se eu entendi seu problema, você está interessado em todas as combinações possíveis de pares (p, q) com p's únicos eqs respeitando um dado conjunto de valores possíveis para p's e q's. Na minha resposta, presumo que esses valores possíveis estejam, respectivamente, em list_p e list_q (acho que isso é o que você tem em ExpList1 e ExpList2 estou certo?)

min_size = min(len(list_p), len(list_q))

combos_p = itertools.combinations(list_p, min_size)
combos_q = itertools.permutations(list_q, min_size)
prod = itertools.product(combos_p, combos_q)
uniquecombolist = [tuple(zip(i[0], i[1])) for i in prod]

Deixe-me saber se é isso que você está procurando. A propósito, bem-vindo ao SO, ótima pergunta!

Editar:

Se você achar que sua lista pode se tornar enorme, você sempre pode usar uma expressão geradora e aplicar qualquer função que desejar, por exemplo,

min_size = min(len(list_p), len(list_q))

combos_p = itertools.combinations(list_p, min_size)
combos_q = itertools.permutations(list_q, min_size)
prod = itertools.product(combos_p, combos_q)
uniquecombo = (tuple(zip(y[0], y[1])) for y in prod) # this is now a generator expression, not a list -- observe the parentheses

def your_function(x):
    # do whatever you want with the values, here I'm just printing and returning
    print(x)
    return x

# now prints the minimum value
print(min(itertools.imap(your_function, uniquecombo)))

Quando você usa geradores em vez de listas, os valores são calculados conforme são necessários. Aqui, como estamos interessados no valor mínimo, cada valor é computado e descartado imediatamente, a menos que seja o mínimo.

    
por Hugo Sadok 04.10.2017 / 05:43
fonte
1

Esta resposta assume que você está tentando gerar conjuntos com | S | elementos, onde S é o menor conjunto de coordenadas da tupla. O maior conjunto será denotado L.

Como o conjunto conterá | S | pares sem elementos repetidos, cada elemento de S deve ocorrer exatamente uma vez. A partir daqui, combine as permutações de L, onde | S | os elementos são escolhidos com os elementos ordenados de S. Isso gerará todos os conjuntos solicitados exaustivamente e sem repetição .

Note que P (| L |, | S |) é igual a | L |! / (| L | - | S |)!

Dependendo dos tamanhos dos conjuntos de coordenadas de tupla, pode haver muitas permutações para enumerar.

Algum código para replicar esta enumeração pode parecer com:

from itertools import permutations 

S, L = range(2), range(4) # or ExpList1, ExpList2
for p in permutations(L, len(S)):
    print(zip(S, p))

No total, seu código final pode ser parecido com:

S, L = ExpList1, ExpList2
pairset_maker = lambda p: zip(S, p)

if len(S) > len(L):
    S, L = L, S
    pairset_maker = lambda p: zip(p, S)

n = len(S)   
get_perm_value = lambda p: math.sqrt(sum(RMSDdict[t] for t in pairset_maker(p))**2/n)

min_pairset = min(itertools.permutations(L, n), key=get_perm_value)

Se isso não levar você a uma ordem ou magnitude ou duas de seu tempo de execução desejado, talvez seja necessário considerar um algoritmo que não produza uma solução ideal.

    
por Jared Goguen 04.10.2017 / 05:38
fonte