Ich hoffe mal, ich habe die Aufgabenstellung nicht total falsch verstanden. Abgesehen von Threads beim Iterieren der Zeilen sehe ich die einzige Optimiermöglichkeit auch nur bei der Spaltenwahl.
Die etwas genaueren rechten Intervallgrenzen wären hier
[0-0.222(|(0.222-0,667)|(0,667-1,0]
, oder?
Nimm die als Zeilen einer Hilfsmatrix und mache darauf eine simple binäre Suche. Da kannst Du maximal O(log n) herausholen, indem Du zur Ur-Matrix eine Hilfsmatrix konstruierst, deren Zeilen eben die rechten Intervallgrenzen enthalten. Dann brauchst Du bei der Suche für N=100 im Schnitt 6-7 Tests im Gegensatz zu 50 bei linearer Suche.
Das Problem mit dem Verbot der Auswahl bereits ausgewählter Spalten ist mir nicht ganz klar: Nehmen wir an, wir sind in der dritten Zeile einer 10x10 Matrix und die Spalten 2 und 5 sind schon "verboten": Sollen dann die Spalten 1,3-4 und 6-10 erlaubt sein und mit Wahrscheinlichkeit relativ zu Ihrer Breite gewählt werden?
Einfacher: Angenommen im Beispiel oben sei in der ersten Zeile die Spalte 2 ausgewählt worden, wären die Spalten 1 (0.2) und 3 (0,3) noch erlaubt? Dann würde Spalte 1 mit Wahrscheinlichkeit 0,4 und Spalte 3 mit Wahrscheinlichkeit 0,6 gewählt?
