有约束的矩阵排列

Question

我有以下矩阵：

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

我想随机排列列，第二行中的每四个数字应包含某种形式的

0 0 1 2

例如以下示例中的 1:4、5:8、9:12、13:16、17:20、21:24 列各包含数字 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

置换矩阵中的每一列都应该在第一个矩阵中有一个对应的列。换句话说，列中的任何内容都不应更改。

我似乎想不出一个直观的解决方案 - 是否有另一种方法可以提出某种形式的初始矩阵，既满足约束又保持列的完整性？每列代表实验中的条件，这就是为什么我希望它们是平衡的。

Answer 1

您可以使用 rejection method：继续尝试随机排列，等概率地选择，直到满足要求。这保证了所有有效排列被选中的概率相同。

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

这是一个示例结果：

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

可以直接按以下方式计算排列：首先，将第二行中具有 0 的所有列相互排列，然后将所有 1 排列在一起，最后将所有 2s 在他们中间。这确保了，例如，任何两个 0 列同样可能是 A.
的结果排列中的前两列第二步是排列 4 块中的所有列：随机排列 1-4 列，随机排列 5-8 列，等等。一旦你这样做，你就有了一个矩阵，它为每个保持 (0 0 1 2) 模式4 列的块，但每组 (0 0 1 2) 同样可能出现在任何给定的 4 块中，并且 (0 0 1 2) 同样可能处于任何顺序。

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

示例结果：

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

我能够在大约 9.32 秒内生成 A 的 100000 个约束排列运行 MATLAB 2016a，让您了解这段代码需要多长时间。当然有一些方法可以优化排列选择，这样您就不必进行那么多随机抽取，但我总是更喜欢简单、直接的方法，直到证明它不够用。

有约束的矩阵排列

Matrix Permutations with Contraint

arrays

matlab

permutation

matrix