comment générer des permutations de tableau en python?
J'ai un tableau de 27 éléments,et je ne veux pas générer toutes les permutations de tableau (27!) j'ai besoin de 5000 permutations choisies au hasard, toute astuce sera utile...
6 réponses
Pour générer une permutation utilisation random.shuffle et de conserver une copie du résultat. Répétez cette opération dans une boucle et vérifiez à chaque fois les doublons(il n'y en aura probablement pas). Une fois que vous avez 5000 articles dans votre jeu de résultats, arrêtez.
Pour répondre au point dans le commentaire, le module aléatoire de Python {[5] } est basé sur le Mersenne Twister et a une période de 2**19937-1, ce qui est considérablement plus grand que 27! donc il devrait convenir à votre utilisation.
import random
perm_list = []
for i in range(5000):
temp = range(27)
random.shuffle(temp)
perm_list.append(temp)
print(perm_list)
10888869450418352160768000000 j'aime les grands nombres! :)
Et
10888869450418352160768000001 est PREMIER!!
Modifier:
#with duplicates check as suggested in the comment
perm_list = set()
while len(perm_list)<5000:
temp = range(27)
random.shuffle(temp)
perm_list.add(tuple(temp)) # `tuple` because `list`s are not hashable. right Beni?
print perm_list
Attention: cela ne s'arrêtera jamais si RNG est mauvais!
itertools.permutations. C'est un générateur, donc il ne créera pas toute la liste des permutations. Vous pouvez sauter au hasard jusqu'à ce que vous avez 5000.
# apermindex should be a number between 0 and factorial(len(alist))
def perm_given_index(alist, apermindex):
for i in range(len(alist)-1):
apermindex, j = divmod(apermindex, len(alist)-i)
alist[i], alist[i+j] = alist[i+j], alist[i]
return alist
Utilisation: perm_given_index(['a','b','c'], 3)
Cela utilise le code de Lehmer pour la permutation car les valeurs de j correspondent à cela.
Vous pouvez vouloir les itertools.fonction permutations (). Je dois aimer ce module itertools!
NOTE: nouveau dans 2.6
Vous pouvez essayer d'implémenter le random_permutation itertools recettes . Pour plus de commodité, j'utilise une bibliothèque tierce, more_itertools, cela met en œuvre cette recette pour nous:
import more_itertools as mit
iterable = range(27)
mit.random_permutation(iterable)
# (24, 3, 18, 21, 17, 22, 14, 15, 20, 8, 4, 7, 13, 6, 25, 5, 12, 1, 9, 19, 23, 11, 16, 0, 26, 2, 10)
Une permutation aléatoire est créée pour chaque appel de la fonction. Nous pouvons créer un générateur qui donne ces résultats pour les appels n. Nous allons implémenter ce générateur et démontrer des résultats aléatoires avec un exemple abrégé:
def random_permute_generator(iterable, n=10):
"""Yield a random permuation of an iterable n times."""
for _ in range(n):
yield mit.random_permutation(iterable)
list(random_permute_generator(range(10), n=20))
# [(2, 7, 9, 6, 5, 0, 1, 3, 4, 8),
# (7, 3, 8, 1, 2, 6, 4, 5, 9, 0),
# (2, 3, 1, 8, 7, 4, 9, 0, 6, 5),
# (0, 5, 6, 8, 2, 3, 1, 9, 4, 7),
# (0, 8, 1, 9, 4, 5, 7, 2, 3, 6),
# (7, 2, 5, 8, 3, 4, 1, 0, 9, 6),
# (9, 1, 4, 5, 8, 0, 6, 2, 7, 3),
# (3, 6, 0, 2, 9, 7, 1, 4, 5, 8),
# (8, 4, 0, 2, 7, 5, 6, 1, 9, 3),
# (4, 9, 0, 5, 7, 1, 8, 3, 6, 2)
# ...]
Pour votre problème spécifique, remplacez le itérable et le nombre des appels n, avec les valeurs appropriées, par exemple random_permute_generator(iterable, n=5000).
Voir aussi more_itertools docs pour de plus amples informations sur cet outil.
Détails
Pour ceux qui sont intéressés, voici la recette réelle.
À partir des recettes itertools :
def random_permutation(iterable, r=None):
"Random selection from itertools.permutations(iterable, r)"
pool = tuple(iterable)
r = len(pool) if r is None else r
return tuple(random.sample(pool, r))