2012-12-30 4 views
5

Mentre lavoravo su un problema relativo alla congettura di Weisstein (https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf), avevo bisogno di generare tutto n x n (0,1) matrici per n = 2, 3, 4, ... Non è troppo difficile se si pensa alle giuste sequenze binarie e partizionate di conseguenza. Ad esempio, qui sono tutti i 3 x 3 matrici:Genera tutte le matrici nxn (0,1)

With[{n = 3}, 
lis = PadLeft[IntegerDigits[#, 2], n^2]& /@ Range[0, 2^n^2 - 1]; 
mats = (Partition[#, n] &) /@ lis 
]; 

congettura di Weisstein comporta, per ogni n = 2, 3, ..., contando il numero di matrici le cui autovalori sono tutti reali e positivo. Per n = 2, ci sono 3; per n = 3, ci sono 25; per n = 4, ci sono 543; e così via. I calcoli degli autovalori richiedono molto tempo ma sono semplici.

Quello che mi interessava, però, è stato trovare altri modi di enumerare i n x n matrici. Per ottenerli tutti ho usato le rappresentazioni di base 2 degli interi fino a 2^(n^2) e partizionato per fare le matrici. Ci devono essere altri modi (più efficienti?).

+0

Potrebbe essere più adatto per [cstheory] (http://cstheory.stackexchange.com), anche se potrebbero snobbare il loro naso perché troppo basico .. =^_^= –

risposta

8

Possiamo utilizzare la funzione incorporata Mathematica Tuples. Il vostro esempio 3x3 diventa semplicemente

ms = Tuples[{1, 0}, {3, 3}]; 

L'enumerazione di ordinamenti può essere fatto da numeri binari

FromDigits[#, 2] & /@ Flatten /@ ms 

enter image description here

Per visualizzare gli ordinamenti:

ArrayPlot[#, ImageSize -> 20, Mesh -> All] & /@ ms 

enter image description here