Matrix Permutationen mit contraint

Question

Ich habe folgende Matrix:

1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 
0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 
0 0 0 0 1 1 1 1 2 2 2 2 0 0 0 0 1 1 1 1 2 2 2 2 

I zufällig möchte die Spalten permutieren, mit der Einschränkung, dass alle vier Zahlen in der zweiten Reihe eine Form von

0 0 1 2 

enthalten sollen,

z Spalten 1: 4, 5: 8, 09.12, 13.16, 17.20, 21.24 in dem folgenden Beispiel enthalten jeweils die Zahlen 0 0 1 2.

0 1 0 2 2 0 1 0 0 0 2 1 1 2 0 0 2 0 1 0 1 0 0 2 

Jede Spalte in der Matrix permutiert sollte eine entsprechende in der ersten Matrix haben. Mit anderen Worten, nichts sollte innerhalb einer Spalte verändert werden.

Ich kann nicht an eine intuitive Lösung dafür denken - Gibt es eine andere Möglichkeit, eine Form der Ausgangsmatrix zu finden, die sowohl die Bedingung erfüllt als auch die Integrität der Spalten beibehält? Jede Spalte steht für Bedingungen in einem Experiment, weshalb ich möchte, dass sie ausgewogen sind.

Answer 1

Sie könnten ein rejection method verwenden: Versuchen Sie, zufällige Permutationen, gleichwertig ausgewählt, bis man die Anforderung erfüllt. Dies garantiert, dass alle gültigen Permutationen dieselbe Wahrscheinlichkeit haben, ausgewählt zu werden.

A = [ 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 
     0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 
     0 0 0 0 1 1 1 1 2 2 2 2 0 0 0 0 1 1 1 1 2 2 2 2 ]; % data matrix 
required = [0 0 1 2]; % restriction 
row = 2; % row to which the resitriction applies 

sorted_req = sort(required(:)); % sort required values 
done = false; % initiallize 
while ~done 
    result = A(:, randperm(size(A,2))); % random permutation of columns of A 
    test = sort(reshape(result(row,:), numel(required), []), 1); % reshape row 
     % into blocks, each block in a column; and sort each block 
    done = all(all(bsxfun(@eq, test, sorted_req))); % test if valid 
end 

Hier ist ein Beispiel Ergebnis:

result = 
    2 1 1 1 1 2 1 2 1 2 2 1 2 2 1 2 2 2 1 1 1 2 1 2 
    2 0 0 1 2 1 0 0 0 1 0 2 2 0 1 0 1 2 0 0 2 0 1 0 
    2 1 2 2 1 2 2 0 1 1 1 2 1 1 0 0 0 0 0 0 0 2 1 2 

Answer 2

Sie können die Permutationen direkt auf folgende Weise berechnen: Zuerst permutieren alle Spalten mit 0 in der zweiten Reihe unter sich, dann alle 1 s unter sich und schließlich alle 2 s untereinander. Dies stellt sicher, dass beispielsweise zwei beliebige 0-Spalten gleichermaßen wahrscheinlich die ersten beiden Spalten in der resultierenden Permutation von A sind.
Der zweite Schritt besteht darin, alle Spalten in Blöcken von 4 zu permutieren: Spalten 1-4 willkürlich vertauschen, Spalten 5-8 zufällig permutieren usw. Sobald Sie dies tun, haben Sie eine Matrix, die das Muster (0 0 1 2) beibehält für jeden Block von 4 Spalten, aber jede Menge von (0 0 1 2) ist gleichermaßen wahrscheinlich in irgendeinem gegebenen Block von 4, und die (0 0 1 2) sind gleichermaßen wahrscheinlich in irgendeiner Reihenfolge.

A = [1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 
0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 
0 0 0 0 1 1 1 1 2 2 2 2 0 0 0 0 1 1 1 1 2 2 2 2]; 

%% Find the indices of the zeros and generate a random permutation with that size 
zeroes = find(A(2,:)==0); 
perm0 = zeroes(randperm(length(zeroes))); 

%% Find the indices of the ones and generate a random permutation with that size 
wons = find(A(2,:) == 1); 
perm1 = wons(randperm(length(wons))); 
%% NOTE: the spelling of `zeroes` and `wons` is to prevent overwriting 
%% the MATLAB builtin functions `zeros` and `ones`  

%% Find the indices of the twos and generate a random permutation with that size 
twos = find(A(2,:) == 2); 
perm2 = twos(randperm(length(twos))); 

%% permute the zeros among themselves, the ones among themselves and the twos among themselves 
A(:,zeroes) = A(:,perm0); 
A(:,wons) = A(:,perm1); 
A(:,twos) = A(:,perm2); 

%% finally, permute each block of 4 columns, so that the (0 0 1 2) pattern is preserved, but each column still has an 
%% equi-probable chance of being in any position 
for i = 1:size(A,2)/4 
    perm = randperm(4) + 4*i-4; 
    A(:, 4*i-3:4*i) = A(:,perm); 
end 

Beispiel Ergebnis:

A = 
    Columns 1 through 15 
    1  1  2  2  2  2  1  1  2  2  1  2  2  1  2 
    0  0  2  1  0  2  0  1  0  2  1  0  1  2  0 
    0  1  2  2  2  0  1  1  1  1  2  0  0  2  0 
    Columns 16 through 24 
    2  1  1  1  1  1  2  2  1 
    0  2  0  0  1  0  0  1  2 
    1  1  2  2  0  0  2  1  0 

konnte ich 100000 gezwungen Permutationen von A in etwa 9,32 Sekunden 2016a laufen MATLAB zu erzeugen, um Ihnen eine Vorstellung davon zu geben, wie lange dieser Code nimmt. Es gibt sicherlich Möglichkeiten, die Permutationsauswahl zu optimieren, so dass Sie nicht so viele zufällige Draws erstellen müssen, aber ich bevorzuge immer den einfachen, direkten Ansatz, bis es nicht mehr ausreicht.