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
3 réponses
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]
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)
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')