ho un array di 27 elementi, e io non voglio generare tutte le permutazioni di array (27!) ho bisogno permutazioni 5000 choosed a caso, qualsiasi suggerimento sarà utile ...come generare permutazioni di array in python?
Per generare una permutazione utilizzare random.shuffle e memorizzare una copia del risultato. Ripeti questa operazione in un ciclo e controlla ogni volta i duplicati (probabilmente non ce ne saranno altri). Una volta che hai 5000 elementi nel set di risultati, fermati.
per affrontare il punto nel commento, Python random module si basa sulla Mersenne Twister e ha un periodo di 2**19937-1, che è notevolmente più grande di 27! quindi dovrebbe essere adatto per il vostro uso.
+1, ma si noti che 'random.shuffle' ha una grave debolezza: il periodo della maggior parte degli RNG è inferiore al numero totale di permutazioni quando _n_ diventa più grande. Ciò significa che quasi tutte le permutazioni possibili per un _n_ abbastanza grande non possono mai essere generate, quindi questo non è veramente casuale. –
Infatti, John. Il generatore casuale di Python ha un periodo di 2 ** 19937-1, anche se probabilmente è abbastanza buono. Un altro pungolo è che per i numeri casuali veri occorrerebbe una vera fonte casuale (ad esempio dal decadimento radioattivo), il modulo casuale di Python fornisce solo numeri pseudo-casuali. Ma nell'uso comune quando la gente dice "casuale" ciò che in realtà significa è "pseudo-casuale", e presumo che questo sia ciò che significa il manifesto qui. –
+1 Cool! Si tratta di un grosso dado con 1088886945041835216076800000000 volti probabilità di uno di loro alzarsi è 1/10888869450418352160768000000. Duplicati NO WAY !! –
itertools.permutations. È un generatore, quindi non creerà l'intera lista di permutazioni. È possibile saltare casualmente fino a che non si ottengono 5000 unità.
potrebbe richiedere molto tempo per fare con questo metodo .... –
che non è proprio "random",! poiché 'itertools' li crea in un ordine definito, e ci sono un numero finito di permutazioni. Quello che sarebbe meglio è fare quanto segue: (1) determinare ** quante permutazioni ci sono (chiamate questo numero 'N'), (2) quindi generare 5.000 indici casuali distinti nell'intervallo' 0..N- 1', (3) scegli le permutazioni dal generatore itertools.permutations che corrispondono a questi indici. –
Sì, lo so che non è il migliore. La prima volta che ho letto la domanda in qualche modo non ho notato quella parte "scelta a caso". Non lo eliminerò, forse qualcuno che sta cercando "come generare permutazioni di array in python?" lo troverà utile –
Si consiglia la funzione itertools.permutations(). Devo amare il modulo itertools!
NOTA: Nuovo in 2,6
Questo sarà troppo lento - ha detto che ha 27 elementi. –
import random
perm_list = []
for i in range(5000):
temp = range(27)
random.shuffle(temp)
perm_list.append(temp)
print(perm_list)
10888869450418352160768000000 amo grandi numeri! :)
E
10888869450418352160768000001 è primo !!
EDIT:
#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
ATTENZIONE: Questa abitudine mai fermarsi se RNG è male!
Per controllare anche i duplicati come suggerisce Mark, usa un 'perms = set()', 'perms.add (tuple (temp))', e 'while len (perms) <5000' invece del ciclo for. –
@Beni Non ho seguito il tuo suggerimento 'tuple (temp)' all'inizio, ma poi ho capito che ero un pazzo !! Grazie uomo! –
# 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
Usage: perm_given_index(['a','b','c'], 3)
Questo utilizza il codice Lehmer per la permutazione come i valori di j corrispondano questo.
Questo può essere molto utile, ad esempio per la compressione se è necessario memorizzare molte permutazioni per utilizzare invece la rappresentazione di numeri interi. Mi sono ispirato a scrivere https://gist.github.com/lukmdo/7049748 – lukmdo
È possibile provare a implementare lo random_permutationitertools recipes. Per comodità io uso una libreria di terze parti, more_itertools, che implementa questa ricetta per noi:
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)
una permutazione casuale viene creato per ogni chiamata della funzione. Possiamo creare un generatore che produca questi risultati per le chiamate n. Implementeremo questo generatore e dimostrare risultati casuali con una lista abbreviata:
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)
# ...]
Per il problema specifico, sostituire iterable numero di chiamate n con i valori appropriati, ad esempio random_permute_generator(iterable, n=5000).
Vedere anche more_itertools docs per ulteriori informazioni su questo strumento.
dettagli
Per chi fosse interessato, ecco la ricetta vera e propria.
Dal itertools recipes:
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))
forse vale la pena di ricordare che '' 27 è 10888869450418352160768000000. –