Mischen einer Liste mit Einschränkungen in Python

Question

Ich habe ein Problem mit der Randomisierung einer Liste mit Einschränkungen in Python (3). Ich habe ein paar andere Fragen dazu gesehen, aber keine von ihnen scheint wirklich mein Problem zu lösen. Ich bin ein Anfänger, also wird jede Hilfe sehr geschätzt!

Ich entwerfe ein Experiment mit zwei Arten von Reizen: Formen und Farben (jeweils vier). Ich brauche Permutationen aller 16 Kombinationen zu erzeugen, die ich mit random.shuffle-Funktion getan haben:

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) 

So weit so gut. Ich möchte jedoch vermeiden, dass eine Form (Buchstabe) oder Farbe (Nummer) zweimal hintereinander in meinem Ergebnis erscheint (z. B. "a2", gefolgt von "a4" oder "c2", gefolgt von "a2").

Gibt es eine Möglichkeit, eine solche Einschränkung zu machen?
Vielen Dank im Voraus!

Answer 1

So etwas sollte eine angemessene Antwort in einer angemessenen Zeit

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 

Answer 2

Eine Möglichkeit, um dies zu behandeln, könnte sein, zwei Listen eine Form und eine Farbe zu haben. Mischen Sie jede Liste einzeln. Mischen Sie nun die zwei Listen. Da jede Liste zufällig erstellt wurde, ist die gemischte Liste ebenfalls zufällig, aber Sie haben keine zwei Einträge zusammen.

Beachten Sie, dass Sie mit Zip tatsächlich Paare von Paaren erhalten, die es Ihnen ermöglichen, Ihren Test zu handhaben, indem Sie jedes Paar aus dem Ergebnis holen.

In diesem speziellen Fall jede Farbe ist ein Mitglied der Liste Formen, während jede Farbe ein Mitglied der Liste Farben ist

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

Dies gibt uns jede einzelne Shuffle anstatt alle auf einmal 16 Möglichkeiten zu erzeugen und dann schlurfend sie. Dadurch können Sie Ihren Test möglicherweise besser erstellen. nicht die gleiche Farbe oder Form in der gleichen Position wie die vorherige Gruppe von vier haben, dann können Sie nach dem Shuffle gegen die vorherige Einstellung für das Testen

Wenn Sie sicherstellen möchten, dass zwei Sätze von Listen.

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 

Dies wird schlurfenden halten, bis Tester Wahr und verwirft alle ungültigen Ergebnisse von random.shuffle wird()

Answer 3

Während Sie technisch itertools.permutations nutzen können (ich versuchte, die ersten), das würde viel zu lange dauern.

Mit dieser Zufallssequenzen ohne Elemente erzeugen, die eine Eigenschaft folgende miteinander teilen:

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) 

Answer 4

Sie können die Liste Stück bauen weise durch eine zufällige Option auf den letzten Wert zu vergleichen.

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] 

Answer 5

Ich bezweifle, dass dies die Art und Weise besten ist, aber es ist ein Weg, dies zu tun. Wenn Sie dieses über Ihre Eingabe als Matrix denken

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

Dann bist du Ziel wird bei jeder Iteration einen solchen Zufalls Index wählen, dass der neue Index nicht in der gleichen Reihe ist noch die gleiche Spalte der Matrix als der vorherige Index und so, dass das neue Element noch nicht ausgewählt wurde.dass in Code Putting naiv, es wird

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 

Ausgänge Nach ein paar Runs

['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'] 

Haftungsausschluss

Da dies eine völlig naive Ansatz ist, wird es manchmal stecken! Angenommen, die letzten zwei verbleibenden Indizes sind [(2, 2), (3, 2)]. Dann ist es für den Algorithmus nicht möglich, fortzufahren, ohne die Beschränkungen zu brechen. Im Moment handle ich mit einem rekursiven Aufruf, der nicht ideal ist.