It looked reasonably random to me. I ran it through the same program I ran my snippet through and got similar results. Maybe slightly less uniform than mine, but still reasonable.
Here is the code I used to test these. I create a list of 100 items, and randomize that list and record the resulting positions 100,000 times. The average positions for each number should hover around the mid-point of the list. Both of these do. Here's the code( yes, it's a quick hack!)
#!/usr/bin/perl
print `date`;
my %count;
my $size = 100000;
foreach (0..99) {
$count{$_} = 0;
};
my @lKeys = sort { $a <=> $b } (keys(%count));
my $arraySize = scalar(@lKeys);
for (1..$size) {
my @lList = crypto(\@lKeys);
my $pos = 0;
my $curr = '';
while (defined($curr = shift(@lList))) {
$count{$curr} += $pos;
$pos++;
}
}
local $\ = "\n";
print "Size:$size";
print "Array Size: $arraySize\n";
foreach my $curr (@lKeys) {
my $total = $count{$curr};
my $average = $total/$size;
my $diff = abs(($arraySize/2)-$average);
print "$curr:\t$diff";
}
print `date`;
exit;
sub crypto {
my $rList = shift;
my @list = @$rList;
my ($lPos, $lRand);
foreach $lPos (1..$#list)
{
$lRand = int(rand($lPos+1));
@list[$lPos, $lRand] = @list[$lRand, $lPos];
}
return @list;
}
sub otherCrypto {
my $rList = shift;
my @list = sort {rand > .5} @$rList;
return @list;
}
If there is a problem with my methodology for testing this, I would appreciate it being pointed out. | [reply]
[d/l] |
Sheesh! What kind of hardware do you have? It's taking me
longer to execute it than it took you to write it!
:-)
Okay, after 14 minutes (!), I saw similar results. The
problem, as I see it, is not the distribution around the
median, but the predictability of successive elements.
Any given number may have an equal chance of being at any
location in the result array. However, there seems to be
a very large probability (certainly greater than random)
that for a given element, the element which starts next to
this one will end up very close to wherever this element
ends up.
At least in the case of pre-sorted input (which we all used), close neighbors tend to not only stay near
each other, but to stay in the same order. Given that Perl
uses a quicksort-based implementation, this will likely be
true of all input data.
Obviously, neither of the two solutions (the
original post and
this one) is suitable
for strong cryptography (no solution which only uses a
pseudo-random number generator will be).
Russ
| [reply] |