Randomisierte Buchstaben Matrix

[hsw]

halllo python forum,

ich möchte mit python eine randomisierte buchstaben matrix erstellen.
die matrix besteht aus 26 zeilen und 26 spalten. jedoch muss jede zeile und spalte genau einmal jeden buchstaben des alphabets enthält.

mein bisheriger code:

Code: Alles auswählen

import random
import string


# functions
def row_check(x, y, ch, row):
	for i in range(x):
		if ch == row[i]:
			return False 		
	return True		

# hier sollte der fehler liegen
def column_check(x, y, ch, matrix):
	for i in range(y):
		if ch == matrix[i][x]:
			return False
	return True


def create_matrix(matrix, row):
	for y in range(26):
		for x in range(26):
			while True:
				ch = random.choice(string.ascii_uppercase)
				check_r = row_check(x, y, ch, row)
				if check_r == False:
					continue	
				check_c = column_check(x, y, ch, matrix)
				if check_c == False:
					continue
				else:
					break
			row = row + ch
		matrix.append(row)
		row = "" 	# reset


def print_matrix(matrix):
	for y in range(26): 	
		for x in range(26):
			print matrix[y][x],
		print


# main
matrix = []
row = ""
create_matrix(matrix, row)	
print_matrix(matrix)

die endlosschleife in der funktion create_matrix prüft solange einen zufälligen buchstaben, bis row_check und column_check True zurückgeben.
der code erzeugt leider eine endlosschleife. ich schätze, dass der fehler irgendwas mit der funktion column_check zu tun hat.
hat irgendwer einen tipp für mein problem?

[pixewakb]

Ohne deinen Ansatz jetzt genau zu verstehen.

Schau dir mal random.shuffle an, die schüttelt die Elemente einer Liste gehörig durch. M. E. musst du dann die Spalten und Reihen solange sortieren, bis es passt, d. h. a, b = b, a, falls die Elemente in der Reihe oder Spalte nicht passen.

Interessant fände ich hier, wie man das modellieren kann.

Matrix = [ [Zeile1] [Zeile2] ... [Zeile26]] oder kann man das auch anders modellieren???

[karolus]

Hallo

Code: Alles auswählen

from random import shuffle
from string import ascii_uppercase

preline = list(ascii_uppercase)

shuffle(preline)
rstring = ''.join( preline )

out = []
for _  in range(len( rstring )):
    rstring = rstring[1:] + rstring[:1]
    out.append( rstring )

shuffle(out)

print '\n'.join(out)

Karolus

[BlackJack]

@karolus: Da fehlt jetzt noch der Beweis, dass damit alle Matrixen erstellt werden können, welche die Anforderungen erfüllen.

Edit: Alternative für `out`:

Code: Alles auswählen

out = [rstring[i:] + rstring[:i] for i in xrange(len(rstring))]

[pillmuncher]

@hsw: Hier ist meine Version (randmatrix.py), die nicht - wie deine - das Problem hat, dass die Abbruchbedingung möglicherweise niemals erreicht wird:

Code: Alles auswählen

import random
import string
import pprint
from itertools import permutations

def random_square_matrix(items):
    matrix = [random.sample(items, len(items)) for _ in items]
    for i in range(1, len(items)):
        cols = list(zip(*matrix[:i]))
        for row in permutations(matrix[i]):
            if all(c not in cs for c, cs in zip(row, cols)):
                matrix[i] = row
                break
    return matrix

def test(n):
    return random_square_matrix(string.ascii_uppercase[:n])

if __name__ == '__main__':
    pprint.pprint(test(6))

Du kannst es mittels

Code: Alles auswählen

$ python randmatrix.py

ausprobieren, oder mittels

Code: Alles auswählen

$ python -m timeit -s "import randmatrix" "randmatrix.test(...)"

wobei du statt der ... angeben musst, wie viele Buchstaben die Matrix breit sein soll. Hier meine Ergebnisse bis 9:

1: 21.9 usec
2: 62 usec
3: 185 usec
4: 724 usec
5: 4 msec
6: 22.8 msec
7: 196 msec
8: 1.71 sec
9: 13.1 sec

Wie lange es für 26 dauern würde solltest du damit abschätzen können.

[Sirius3]

kleiner Tipp:
wenn Du mit einer sortierten Matrix, A auf der Diagonalen, B daneben usw.
und dann erst ganze Zeilen durcheinander würfelst und danach immer ganze
Spalten durcheinanderwürfelst, dann bleibt Deine Bedingung, dass jeder
Buchstabe nur einmal in jeder Spalte und jeder Zeile enthalten ist, immer erfüllt.

[hsw]

@blackjack: danke für das editieren.
@karolus: hätte nicht gedacht, dass man es so leicht lösen kann. wow, danke!

@pillmuncher: danke!
leider versteh ich noch nicht ganz was zip und all machen.
das werde ich mir aber in den nächsten tagen genauer anschauen.