2016-03-03 19 views
5

Ho un problema con la randomizzazione di un elenco con restrizioni in Python (3). Ho visto alcune altre domande relative a questo, ma nessuno di loro sembra davvero risolvere il mio problema. Sono un principiante, quindi qualsiasi aiuto è molto apprezzato!shuffling di un elenco con restrizioni in Python

Sto progettando un esperimento utilizzando due tipi di stimoli: forme e colori (quattro di ciascuno). Ho bisogno di generare permutazioni di tutte le 16 combinazioni, che ho fatto con random.shuffle funzione:

import random 

# letters are shapes, numbers are colors 
x=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"] 

random.shuffle(x) 

Fin qui tutto bene. Tuttavia, voglio evitare che una forma (lettera) o un colore (numero) appaiano due volte di seguito nel mio risultato (ad esempio "a2" seguito da "a4" o "c2" seguito da "a2").

C'è un modo per rendere tale restrizione?
Grazie in anticipo!

+3

Fin qui tutto bene? 'random.shuffle (x)' restituisce None perché mischia 'x' al posto. Pertanto, 'result' sarà None. – zondo

+0

Questo sembra un problema con il grafico. Ogni nodo ha un bordo che punta a tutti gli altri nodi ad eccezione di quelli con la stessa forma o colore (quindi (n-1)^2 spigoli per nodo). E poi vuoi una traversata casuale che colpisca ogni vertice esattamente una volta - penso un percorso hamiltoniano. –

+0

@zondo Oh, giusto grazie per averlo indicato. Ho corretto l'esempio. – Frederik

risposta

1

Qualcosa del genere dovrebbe dare una risposta ragionevole in un tempo ragionevole

import random 
while 1: 
    choices = ["a1", "a2","a3","b1","b2","b3","c1","c2","c3"] 

    shuffle = [] 

    last = "" 

    while choices: 
     l = choices 
     if last: 
      l = [x for x in l if x[0] != last[0] and x[1] != last[1]] 
     if not l: 
      #no valid solution 
      break 
     newEl = random.choice(l) 
     last = newEl 
     shuffle.append(newEl) 
     choices.remove(newEl) 
    if not choices: 
     print(shuffle) 
     break 
+0

Grazie per il downvote ;-) se hai una soluzione migliore sei libero di dirti che lo sai –

+1

Sono curioso anche del downvote. Ho provato la tua soluzione e sembra funzionare. –

+0

Ho provato il codice prima di consegnarlo ;-) –

4

Un modo per gestire questo potrebbe essere quello di avere due liste una di forme e una di colori. Mescola ogni lista individualmente. Ora mescola le due liste. Poiché ogni elenco è stato creato a caso, anche la lista mista è casuale, ma non si hanno due voci insieme.

Si noti che l'utilizzo di zip consente di ottenere set di coppie che consentono di gestire il test ottenendo ogni coppia dal risultato.

In questo caso particolare ogni colore è un membro delle forme LIST mentre ogni colore è un membro della lista colori

shapes = ['a', 'b', 'c', 'd'] 
colors = ['1', '2', '3', '4'] 
zip(shapes, colors) 
[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4')] 

Questo ci dà ogni singolo casuale piuttosto che generare tutti i 16 elementi alla volta e poi mischiandoli. Questo potrebbe consentire di generare meglio il test.

Se si desidera assicurarsi che due serie di elenchi non abbiano lo stesso colore o la stessa forma nella stessa posizione del precedente gruppo di quattro, è possibile verificarla dopo lo shuffle rispetto all'impostazione precedente.

testing = True 
while testing: 
    newcolors = colors 
    random.shuffle(newcolors) 
    # perform the test that you want to make get testresult True or False 
    if testresult: 
     colors = newcolors 
     testing = False 

Ciò manterrà rimescolamento fino TestResult diventa vero e scartare tutti i risultati non validi da random.shuffle()

-1

Mentre si potrebbe tecnicamente utilizzare itertools.permutations (ho provato prima), che avrebbe preso troppo tempo.

Utilizzare questo per generare sequenze casuali senza gli elementi che condividono una proprietà seguente vicenda:

from random import shuffle 

x=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"] 

def pairwise(some_list): 
    one = iter(some_list) 
    two = iter(some_list) 
    next(two) 
    for first, second in zip(one, two): 
     yield first, second 

while True: 
    shuffle(x) 
    for first, second in pairwise(x): 
     if first[0] == second[0] or first[1] == second[1]: 
      break 
    else: # nobreak: 
     print(x) 
-1

Si può costruire il pezzo lista saggio confrontando l'opzione casuale per l'ultimo valore.

import random 

options = ["a1", "a2", "a3", "a4", "b1", "b2", "b3", "b4", 
      "c1", "c2", "c3", "c4", "d1", "d2", "d3", "d4"] 

j = random.choice(range(len(options))) 
result = [options.pop(j)] 
last = result[-1] 
while options: 
    j = random.choice(range(len(options))) 
    candidate = options[j] 
    if all([x != y for x, y in zip(last, candidate)]): 
     result.append(options.pop(j)) 
     last = result[-1] 
1

dubito che questo sia il modo migliore , ma è un modo di fare questo. Se pensate al vostro ingresso come una matrice come questo

a1, b1, c1, d1 
a2, b2, c2, d2 
a3, b3, c3, d3 
a4, b4, c4, d4 

Allora sei obiettivo diventa la scelta di un indice casuale ad ogni iterazione in modo tale che il nuovo indice non è nella stessa riga, né la stessa colonna della matrice come l'indice precedente e tale che il nuovo elemento non è stato scelto prima.Mettendo in codice ingenuamente, diventa

import random 
shapes_and_colors=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"] 
nRows = 4 
nCols = 4 
inds = [(x,y) for x in range(nRows) for y in range(nCols)] 
def make_random(someArr): 
    toRet = [] 
    n = len(someArr) 
    for i in range(n): 
     possible = [thing for thing in someArr if thing not in toRet] 
     prev = poss = None 
     while poss is None: 
      next_val = random.choice(possible) 
      if next_val == prev: 
       #failed so try again 
       return make_random(someArr) 
      if not toRet or (next_val[0] != toRet[-1][0] and next_val[1] != toRet[-1][1]): 
       poss = next_val 
      prev = next_val 
     toRet += poss, 
    return toRet 



ans= [thing for thing in make_random(shapes_and_colors)] 
print ans 

uscite dopo un paio Esegue

['c3', 'd4', 'c1', 'd3', 'b1', 'a4', 'b3', 'c4', 'a3', 'b2', 'a1', 'c2', 'd1', 'a2', 'b4', 'd2'] 
['d4', 'b3', 'c1', 'a4', 'b2', 'c4', 'd3', 'a1', 'c3', 'a2', 'b4', 'd2', 'a3', 'b1', 'c2', 'd1'] 

responsabilità

Poiché si tratta di un approccio totalmente ingenuo, a volte si blocca! Quindi supponiamo che gli ultimi due indici rimanenti siano [(2, 2), (3, 2)]. Quindi, non è possibile che l'algoritmo proceda senza rompere le restrizioni. In questo momento, lo gestisco con una chiamata ricorsiva, che non è l'ideale.