Toutes mes excuses si cette question a été posée, je n'ai peut-être pas le vocabulaire nécessaire pour trouver la bonne question.

Si j'ai des listes de longueur égale (ou des tuples) de choses comme ceci:

[6, 4, 7] [gold, blue, red] [dog, cat, echidna] [hot, cold, rainy]

Et un ensemble de clés qui sont des entiers consécutifs dans une plage connue qui est égale au nombre de combinaisons uniques (dans ce cas 81).

Est-il possible de sélectionner un élément de chaque liste pour chaque clé, de sorte que la combinaison est garantie unique? (et obtenez également la clé de la combinaison).

Pour que

0 pourrait donner (6, or, chat, chaud)

1 pourrait céder (chat, 4, or, pluvieux)

2 pourraient céder (chaud, rouge, échidné, 7)

Etc...

Et sachez que (chaud, rouge, échidné, 7) la sélection est-elle produite par 2?

En supposant que la longueur et l'ordre des listes sont connus et fixes, les éléments des listes sont garantis uniques dans chaque liste et dans toutes les listes, et chaque liste peut être ordonnée / triée

2
Alexander 5 mars 2016 à 03:06

3 réponses

Meilleure réponse

Vous pouvez créer un mappage efficace sans matérialiser une structure de données à l'aide d'une formule. Disons que nous prenons à plusieurs reprises n mod la longueur de chaque séquence et divisons par les longueurs. Cela nous donne:

def get_nth(seqs, n):
    out = []
    for seq in seqs:
        i = n % len(seq)
        n //= len(seq)
        out.append(seq[i])
    return out

Après quoi nous avons

>>> seqs = [[6, 4, 7], ['gold', 'blue', 'red'],
        ['dog', 'cat', 'echidna'], ['hot', 'cold', 'rainy']]
>>> get_nth(seqs, 0)
[6, 'gold', 'dog', 'hot']
>>> get_nth(seqs, 1)
[4, 'gold', 'dog', 'hot']
>>> get_nth(seqs, 80)
[7, 'red', 'echidna', 'rainy']
>>> len(set(tuple(get_nth(seqs, i)) for i in range(81)))
81

Cela fonctionnera très rapidement même sur de longues listes:

>>> seqs = [list(range(10**3))]*10**3
>>> %timeit get_nth(seqs, 0)
1000 loops, best of 3: 592 µs per loop
>>> %timeit get_nth(seqs, (10**3)**(10**3)-1)
100 loops, best of 3: 11.2 ms per loop
>>> get_nth(seqs, (10**3)**(10**3)-1)[:10]
[999, 999, 999, 999, 999, 999, 999, 999, 999, 999]
0
DSM 5 mars 2016 à 11:28

Tous les éléments de toutes les listes sont uniques

Si les valeurs d'entrée sont toutes uniques dans une liste différente, vous pouvez simplement. Réduit les éléments pour moins de sortie

import itertools

input = [[6, 4], ['gold', 'blue'], ['dog', 'cat'], ['hot', 'cold']];
output = list(itertools.product(*input))
print output

Donc list[0] -> (6, 'gold', 'dog', 'hot')

Sortie

 [(6, 'gold', 'dog', 'hot'), (6, 'gold', 'dog', 'cold'), (6, 'gold', 'cat', 'hot'), (6, 'gold', 'cat', 'cold'), 
 (6, 'blue', 'dog', 'hot'), (6, 'blue', 'dog', 'cold'), (6, 'blue', 'cat', 'hot'), (6, 'blue', 'cat', 'cold'), 
 (4, 'gold', 'dog', 'hot'), (4, 'gold', 'dog', 'cold'), (4, 'gold', 'cat', 'hot'), (4, 'gold', 'cat', 'cold'), 
 (4, 'blue', 'dog', 'hot'), (4, 'blue', 'dog', 'cold'), (4, 'blue', 'cat', 'hot'), (4, 'blue', 'cat', 'cold')]

Tous les éléments de toutes les listes ne sont pas uniques

Ensuite, utilisez simplement itertools.groupby

import itertools

input = [[1, 2], [1, 2], [1, 2], [1, 2]];
output = [k for k,_ in list(itertools.groupby(itertools.product(*input)))]
print output

Sortie

[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 2], [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], 
[1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 2, 2, 2]]   

Performance

Avec votre exemple timeit avec nombre = 1000

0.00650215148926 (without group by)
0.02952003479    (with group by)
0.0323181152344  (algorithm from @GarrettR)
1
Kordi 5 mars 2016 à 11:12

Quelque chose comme ça pourrait fonctionner. Je pensais que cela ne supposait pas que vous ayez une liste de clés. Au lieu de cela, il génère des clés à la volée en énumérant le produit de vos listes.

a,b,c,d = [6, 4, 7], ['gold', 'blue', 'red'], ['dog', 'cat', 'echidna'], ['hot', 'cold', 'rainy']
from itertools import product
forward = {}
backward = {}
for i,thing in enumerate(product(a,b,c,d)):
    forward[i] = thing
    backward[thing] = i

Exemples de mappages vers l'avant

77 -> (7, 'red', 'cat', 'rainy')
78 -> (7, 'red', 'echidna', 'hot')
79 -> (7, 'red', 'echidna', 'cold')
0
Garrett R 5 mars 2016 à 00:32