如何生成列频率与原矩阵一致的行排列矩阵？

核心结论 #

完全可以生成满足要求的矩阵B，且存在高效算法，无需暴力随机尝试。你的随机方法效率极低是因为每行独立随机洗牌后，恰好匹配所有列频率的概率随N、R增大呈指数级下降，几乎不可能命中。

可行算法思路 #

1. 贪心迭代调整法 #

• 步骤：
  • 初始化B为A的每行随机洗牌结果
  • 计算B的列频率与目标频率F_A的差异
  • 寻找两行，交换它们内部的指定位置元素（调整行内置换），针对性缩小频率偏差
  • 重复调整直到列频率完全匹配，且B与A不同
• 优势：每次调整都精准修正偏差，效率远高于暴力随机

2. 二分图匹配构造法 #

• 步骤：
  • 统计原矩阵A中每个值v在每列j的出现次数c(v,j)（即F_A(v,j)）
  • 构建二分图：左侧节点为矩阵的N行，右侧节点为「行位置+值」对（每行对应R个值，共N×R个）
  • 约束：每行必须匹配R个不同值（保证是排列），每个值v在列j的出现次数严格等于c(v,j)
  • 通过二分图最大流/匹配算法直接构造满足所有约束的矩阵B
• 优势：能保证构造出解，且可轻松避免B与A完全一致（只要原问题存在非平凡解，绝大多数场景都满足）

优化后的Matlab实现（贪心迭代版） #

以下代码采用贪心调整策略，比暴力随机高效数个量级：

clear
n = 20;
r = 8;
% 生成原矩阵A（每行是1~r的排列）
A = cell2mat(arrayfun(@randperm, repmat(r, 1, n), 'UniformOutput', false)');

% 计算目标列频率：F_A(v,j)表示值v在第j列的出现次数
F_A = zeros(r, r);
for j = 1:r
    counts = histcounts(A(:,j), 1:r+1);
    F_A(:,j) = counts';
end

% 初始化B：每行随机洗牌
B = A;
for i = 1:n
    B(i,:) = A(i, randperm(r));
end

% 计算当前B的列频率
F_B = zeros(r, r);
for j = 1:r
    counts = histcounts(B(:,j), 1:r+1);
    F_B(:,j) = counts';
end

max_iter = 10000;
iter = 0;
found = false;

while iter < max_iter && ~found
    iter = iter + 1;
    diff = F_A - F_B;
    % 检查是否已匹配所有列频率
    if all(diff(:) == 0)
        if ~isequal(A, B)
            found = true;
        else
            % 若B与A完全相同，重新随机初始化
            for i = 1:n
                B(i,:) = A(i, randperm(r));
            end
            for j = 1:r
                counts = histcounts(B(:,j), 1:r+1);
                F_B(:,j) = counts';
            end
        end
        continue;
    end
    
    % 找到需要修正的频率偏差点
    [v1, j1] = find(diff < 0, 1); % v1在j1列出现过多
    [~, j2] = find(diff(v1,:) > 0, 1); % v1在j2列出现过少
    
    % 找到行i1：B(i1,j1)=v1（需要移走该位置的v1）
    i1 = find(B(:,j1) == v1, 1);
    % 找到行i2：该行j1列的v2，恰好是j2列出现过多、j1列出现过少的元素
    i2 = find(B(:,j2) ~= v1, 1);
    v2 = B(i2,j1);
    while ~(diff(v2,j2) < 0 && diff(v2,j1) > 0)
        i2 = find(B(:,j2) ~= v1, 1, 'next');
        v2 = B(i2,j1);
    end
    
    % 交换两行的j1、j2位置元素，修正频率偏差
    B(i1,[j1,j2]) = B(i1,[j2,j1]);
    B(i2,[j1,j2]) = B(i2,[j2,j1]);
    
    % 更新频率统计
    F_B(v1,j1) = F_B(v1,j1) - 1;
    F_B(v1,j2) = F_B(v1,j2) + 1;
    F_B(v2,j1) = F_B(v2,j1) + 1;
    F_B(v2,j2) = F_B(v2,j2) - 1;
end

% 验证结果
disp('A与B的列频率是否一致：');
disp(all(all(F_A == F_B)));
disp('A与B是否不同：');
disp(~isequal(A, B));

关键说明 #

• 贪心调整法通过局部修正快速逼近目标，适合中小规模矩阵
• 二分图匹配法适合大规模矩阵，能保证找到解，但实现相对复杂（可借助Matlab的graph工具箱或第三方最大流工具）
• 只要原矩阵A不是唯一满足列频率的排列矩阵（绝大多数场景都满足），就一定能找到不同的B

内容的提问来源于stack exchange，提问作者Goudarzi