Randomize matrix in perl, keeping row and column totals the same

By : Lucas
Source: Stackoverflow.com
Question!

I have a matrix that I want to randomize a couple of thousand times, while keeping the row and column totals the same:

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

An example of a valid random matrix would be:

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

My actual matrix is a lot bigger (about 600x600 items), so I really need an approach that is computationally efficient.

My initial (inefficient) approach consisted of shuffling arrays using the Perl Cookbook shuffle

I pasted my current code below. I've got extra code in place to start with a new shuffled list of numbers, if no solution is found in the while loop. The algorithm works fine for a small matrix, but as soon as I start scaling up it takes forever to find a random matrix that fits the requirements.

Is there a more efficient way to accomplish what I'm searching for? Thanks a lot!

#!/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;
}
By : Lucas


Answers

Not sure if it will help, but you can try going from one corner and for each column and row you should track the total and actual sum. Instead of trying to hit a good matrix, try to see the total as amount and split it. For each element, find the smaller number of row total - actual row total and column total - actual column total. Now you have the upper bound for your random number. Is it clear? Sorry I don't know Perl, so I cannot show any code.



Like @Gabriel I'm not a Perl programmer so it's possible that this is what your code already does ...

You've only posted one example. It's not clear whether you want a random matrix which has the same number of 1s in each row and column as your start matrix, or one which has the same rows and columns but shuffled. If the latter is good enough you could create an array of row (or column, it doesn't matter) indexes and randomly permute that. You can then read your original array in the order specified by the randomised index. No need to modify the original array or create a copy.

Of course, this might not meet aspects of your requirements which are not explicit.

Regards

Mark



I'm not a mathematician, but I figure that if you need to keep the same column and row totals, then random versions of the matrix will have the same quantity of ones and zeros.

Correct me if I'm wrong, but that would mean that making subsequent versions of the matrix would only require you to shuffle around the rows and columns.

Randomly shuffling columns won't change your totals for rows and columns, and randomly shuffling rows won't either. So, what I would do, is first shuffle rows, and then shuffle columns.

That should be pretty fast.

By : Tim Rupe


This video can help you solving your question :)
By: admin