在perl中随机化矩阵，保持行和列的总数相同

Question

我有一个矩阵，我想随机化几千次，同时保持行和列总数相同：

     1 2 3 
   A 0 0 1 
   B 1 1 0 
   C 1 0 0      

有效随机矩阵的一个例子是：

     1 2 3
   A 1 0 0
   B 1 1 0
   C 0 0 1

我的实际矩阵要大得多（大约 600x600 个项目），所以我确实需要一种计算效率高的方法。

我最初的（低效）方法包括使用 Perl Cookbook shuffle

我在下面粘贴了当前的代码。如果在 while 循环中找不到解决方案，我已经准备好了额外的代码，可以从新的打乱后的数字列表开始。该算法对于小矩阵工作得很好，但是一旦我开始扩大规模，就需要很长时间才能找到符合要求的随机矩阵。

有没有更有效的方法来完成我正在寻找的事情？ 多谢！

#!/usr/bin/perl -w
use strict;

my %matrix = ( 'A' => {'3'  => 1 },
           'B' => {'1'  => 1,
               '2'  => 1 },
           'C' => {'1'  => 1 }
    );

my @letters = ();
my @numbers = ();

foreach my $letter (keys %matrix){
    foreach my $number (keys %{$matrix{$letter}}){
    push (@letters, $letter);
    push (@numbers, $number);
    }
}

my %random_matrix = ();

&shuffle(\@numbers);
foreach my $letter (@letters){
    while (exists($random_matrix{$letter}{$numbers[0]})){
    &shuffle (\@numbers);
    }
    my $chosen_number = shift (@numbers);
    $random_matrix{$letter}{$chosen_number} = 1;
}

sub shuffle {
    my $array = shift;
    my $i = scalar(@$array);
    my $j;
    foreach my $item (@$array )
    {
        --$i;
        $j = int rand ($i+1);
        next if $i == $j;
        @$array [$i,$j] = @$array[$j,$i];
    }
    return @$array;
}

Answer 1

当前算法的问题在于，您试图通过洗牌摆脱死胡同 - 具体来说，当您的 @letters 和 @numbers 数组（在初始洗牌之后） @numbers) 多次产生相同的单元格。当矩阵很小时，这种方法很有效，因为不需要太多尝试就能找到可行的重新洗牌。然而，当列表很大时，它就是一个杀手。即使您可以更有效地寻找替代方案（例如，尝试排列而不是随机洗牌），这种方法也可能注定失败。

您可以通过对现有矩阵进行少量修改来解决问题，而不是重新排列整个列表。

例如，让我们从示例矩阵（称为 M1）开始。随机选择一个单元格进行更改（例如 A1）。此时矩阵处于非法状态。我们的目标是通过最少的编辑次数来修复它——具体来说是再进行 3 次编辑。您可以通过围绕矩阵“行走”来实现这 3 个附加编辑，每次修复行或列都会产生另一个需要解决的问题，直到您走完一圈（呃……完整的矩形）。

例如，将A1从0改为1后，下次修复的行走方式有3种：A3、B1、C1。让我们决定第一次编辑应该修复行。所以我们选择A3。在第二次编辑时，我们将修复该列，因此我们有选择：B3 或 C3（例如 C3）。最终修复只提供一个选择（C1），因为我们需要返回到原始编辑的栏。最终结果是一个新的有效矩阵。

    Orig         Change A1     Change A3     Change C3     Change C1
    M1                                                     M2

    1 2 3        1 2 3         1 2 3         1 2 3         1 2 3
    -----        -----         -----         -----         -----
A | 0 0 1        1 0 1         1 0 0         1 0 0         1 0 0
B | 1 1 0        1 1 0         1 1 0         1 1 0         1 1 0
C | 1 0 0        1 0 0         1 0 0         1 0 1         0 0 1

如果编辑路径通向死胡同，你就会原路返回。如果所有修复路径都失败，则可以拒绝初始编辑。

这种方法将快速生成新的有效矩阵。它不一定会产生随机结果：M1 和 M2 仍将彼此高度相关，随着矩阵大小的增长，这一点将变得更加明显。

如何增加随机性？您提到大多数单元格（99% 或更多）都是零。一种想法是这样进行：对于矩阵中的每个 1，将其值设置为 0，然后使用上面概述的 4 编辑方法修复矩阵。实际上，您会将所有这些都移动到新的随机位置。

这是一个例子。这里可能还有进一步的速度优化，但这种方法在我的 Windows 机器上在 30 秒左右的时间内以 0.5% 的密度生成了 10 个新的 600x600 矩阵。不知道这样够不够快。

use strict;
use warnings;

# Args: N rows, N columns, density, N iterations.
main(@ARGV);

sub main {
    my $n_iter = pop;
    my $matrix = init_matrix(@_);
    print_matrix($matrix);
    for my $n (1 .. $n_iter){
        warn $n, "\n"; # Show progress.
        edit_matrix($matrix);
        print_matrix($matrix);
    }
}

sub init_matrix {
    # Generate initial matrix, given N of rows, N of cols, and density.
    my ($rows, $cols, $density) = @_;
    my @matrix;
    for my $r (1 .. $rows){
        push @matrix, [ map { rand() < $density ? 1 : 0  } 1 .. $cols ];
    }
    return \@matrix;
}

sub print_matrix {
    # Dump out a matrix for checking.
    my $matrix = shift;
    print "\n";
    for my $row (@$matrix){
        my @vals = map { $_ ? 1 : ''} @$row;
        print join("\t", @vals), "\n";
    }
}

sub edit_matrix {
    # Takes a matrix and moves all of the non-empty cells somewhere else.
    my $matrix = shift;
    my $move_these = cells_to_move($matrix);
    for my $cell (@$move_these){
        my ($i, $j) = @$cell;
        # Move the cell, provided that the cell hasn't been moved
        # already and the subsequent edits don't lead to a dead end.
        $matrix->[$i][$j] = 0
            if $matrix->[$i][$j]
            and other_edits($matrix, $cell, 0, $j);
    }
}

sub cells_to_move {
    # Returns a list of non-empty cells.
    my $matrix = shift;
    my $i = -1;
    my @cells = ();
    for my $row (@$matrix){
        $i ++;
        for my $j (0 .. @$row - 1){
            push @cells, [$i, $j] if $matrix->[$i][$j];
        }
    }
    return \@cells;
}

sub other_edits {
    my ($matrix, $cell, $step, $last_j) = @_;

    # We have succeeded if we've already made 3 edits.
    $step ++;
    return 1 if $step > 3;

    # Determine the roster of next edits to fix the row or
    # column total upset by our prior edit.
    my ($i, $j) = @$cell;
    my @fixes;
    if ($step == 1){
        @fixes = 
            map  { [$i, $_] }
            grep { $_ != $j and not $matrix->[$i][$_] }
            0 .. @{$matrix->[0]} - 1
        ;
        shuffle(\@fixes);
    }
    elsif ($step == 2) {
        @fixes = 
            map  { [$_, $j] }
            grep { $_ != $i and $matrix->[$_][$j] }
            0 .. @$matrix - 1
        ;
        shuffle(\@fixes);
    }
    else {
        # On the last edit, the column of the fix must be
        # the same as the column of the initial edit.
        @fixes = ([$i, $last_j]) unless $matrix->[$i][$last_j];
    }

    for my $f (@fixes){
        # If all subsequent fixes succeed, we are golden: make
        # the current fix and return true.
        if ( other_edits($matrix, [@$f], $step, $last_j) ){
            $matrix->[$f->[0]][$f->[1]] = $step == 2 ? 0 : 1;
            return 1;
        }
    }

    # Failure if we get here.
    return;
}

sub shuffle {
    my $array = shift;
    my $i = scalar(@$array);
    my $j;
    for (@$array ){
        $i --;
        $j = int rand($i + 1);
        @$array[$i, $j] = @$array[$j, $i] unless $i == $j;
    }
}

Answer 2

步骤 1：首先，我将矩阵初始化为零并计算所需的行和列总计。

步骤 2：现在选择一个随机行，按该行中必须存在的 1 计数进行加权（因此计数为 300 的行比权重为 5 的行更有可能被选择）。

步骤 3：对于这一行，选择一个随机列，按该列中 1 的计数进行加权（忽略任何可能已包含 1 的单元格 - 稍后会详细介绍）。

步骤 4：在此单元格中放置一个 1，并减少相应行和列的行数和列数。

步骤 5：返回步骤 2，直到没有行具有非零计数。

但问题是这个算法可能无法终止，因为你可能有一行需要放置一个 1，一列需要一个 1，但你已经在该单元格中放置了一个，所以你会“卡住” '。我不确定这种情况发生的可能性有多大，但如果这种情况发生得非常频繁，我也不会感到惊讶——足以使算法无法使用。如果这是一个问题，我可以想出两种方法来解决它：

a）递归地构造上述算法并允许在失败时回溯。

b) 如果没有其他选项，则允许单元格包含大于 1 的值并继续。然后，最后您得到了正确的行数和列数，但某些单元格可能包含大于 1 的数字。您可以通过查找如下所示的分组来解决此问题：

2 . . . . 0
. . . . . .
. . . . . .
0 . . . . 1

并将其更改为：

1 . . . . 1
. . . . . .
. . . . . .
1 . . . . 0

如果满足以下条件，应该很容易找到这样的分组：你有很多零。我认为 b) 可能会更快。

我不确定这是最好的方法，但它可能比洗牌数组更快。我将跟踪这个问题，看看其他人的想法。

Answer 3

我不是数学家，但我认为如果您需要保持相同的列和行总数，那么矩阵的随机版本将具有相同数量的 1 和 0。

如果我错了，请纠正我，但这意味着制作矩阵的后续版本只需要您对行和列进行洗牌。

随机打乱列不会改变行和列的总计，随机打乱行也不会。因此，我要做的就是首先打乱行，然后打乱列。

那应该是相当快的。

Answer 4

不确定这是否有帮助，但您可以尝试从一个角落开始，对于每一列和行，您应该跟踪总和和实际总和。不要试图找到一个好的矩阵，而是尝试将总数视为金额并将其拆分。对于每个元素，找到行总计 - 实际行总计和列总计 - 实际列总计中较小的数字。现在您已经有了随机数的上限。
清楚了吗？抱歉，我不懂 Perl，所以我无法显示任何代码。

Answer 5

就像@Gabriel一样，我不是一名Perl程序员，所以这可能是你的代码已经做的事情......

你只发布了一个例子。目前尚不清楚您是否想要一个在每行和每列中具有与起始矩阵相同数量的 1 的随机矩阵，或者具有相同行和列但已打乱的随机矩阵。如果后者足够好，您可以创建一个行（或列，没关系）索引数组并随机排列它。然后，您可以按照随机索引指定的顺序读取原始数组。无需修改原始数组或创建副本。

当然，这可能无法满足您不明确的要求。

Answer 6

感谢 FMc 的 Perl 代码。基于这个解决方案，我用Python重写了它（供我自己使用，为了更清楚而在这里分享），如下所示：

matrix = numpy.array( 
    [[0, 0, 1], 
     [1, 1, 0], 
     [1, 0, 0]]
)

def shuffle(array):
    i = len(array)
    j = 0
    for _ in (array):
        i -= 1;
        j = random.randrange(0, i+1) #int rand($i + 1);
        #print('arrary:', array)
        #print(f'len(array)={len(array)}, (i, j)=({i}, {j})')
        if i != j: 
            tmp = array[i]
            array[i] = array[j]
            array[j] = tmp
    return array

def other_edits(matrix, cell, step, last_j):
    # We have succeeded if we've already made 3 edits.
    step += 1
    if step > 3: 
        return True

    # Determine the roster of next edits to fix the row or
    # column total upset by our prior edit.
    (i, j) = cell
    fixes = []
    if (step == 1):
        fixes = [[i, x] for x in range(len(matrix[0])) if x != j and not matrix[i][x] ]
        fixes = shuffle(fixes)
    elif (step == 2):
        fixes = [[x, j] for x in range(len(matrix)) if x != i and matrix[x][j]]
        fixes = shuffle(fixes)
    else:
        # On the last edit, the column of the fix must be
        # the same as the column of the initial edit.
        if not matrix[i][last_j]: fixes = [[i, last_j]]

    for f in (fixes):
        # If all subsequent fixes succeed, we are golden: make
        # the current fix and return true.
        if ( other_edits(matrix, f, step, last_j) ):
            matrix[f[0]][f[1]] = 0 if step == 2 else 1
            return True

    # Failure if we get here.
    return False # return False

def cells_to_move(matrix):
    # Returns a list of non-empty cells.
    i = -1
    cells = []
    for row in matrix:
        i += 1;
        for j in range(len(row)):
            if matrix[i][j]: cells.append([i, j])
    return cells

def edit_matrix(matrix):
    # Takes a matrix and moves all of the non-empty cells somewhere else.
    move_these = cells_to_move(matrix)
    for cell in move_these:
        (i, j) = cell
        # Move the cell, provided that the cell hasn't been moved
        # already and the subsequent edits don't lead to a dead end.
        if matrix[i][j] and other_edits(matrix, cell, 0, j):
            matrix[i][j] = 0
    return matrix

def Shuffle_Matrix(matrix, N, M, n_iter):
    for n in range(n_iter):
        print(f'iteration: {n+1}') # Show progress.
        matrix = edit_matrix(matrix)
        #print('matrix:\n', matrix)
    return matrix

print(matrix.shape[0], matrix.shape[1]) 

# Args: N rows, N columns, N iterations.
matrix2 = Shuffle_Matrix(matrix, matrix.shape[0], matrix.shape[1], 1) 

print("The resulting matrix:\n", matrix2)