78945612103
71014568932
10924567831
68715491032
10194567823
78106519234
81096571342
86935721041
76891023514
61081547932
10876549231 (interesting: mostly reversed)

80, 79, 75, 67, 65, 57, 72, 62, 71, 61, 52, 95, 68, 87, 83, 82, 59, 78, 58, 77, 100, 64, 88, 97, 99, 74, 96, 1, 94, 3, 4, 98, 6, 8, 15, 17, 20, 22, 24, 26, 30, 31, 33, 34, 38, 39, 40, 44, 49, 50, 51, 53, 54, 55, 56, 60, 63, 66, 69, 70, 73, 76, 81, 84, 85, 86, 89, 90, 91, 92, 93, 35, 36, 10, 29, 48, 7, 32, 28, 42, 25, 47, 16, 41, 14, 46, 13, 45, 12, 11, 43, 9, 5, 21, 23, 37, 2, 18, 27, 19

91, 52, 84, 85, 86, 53, 88, 56, 51, 59, 94, 74, 72, 83, 61, 54, 95, 81, 82, 78, 55, 96, 2, 97, 4, 98, 99, 7, 100, 10, 13, 15, 17, 19, 20, 22, 26, 27, 28, 31, 32, 34, 35, 37, 38, 41, 42, 43, 47, 50, 57, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 79, 80, 87, 89, 90, 92, 93, 33, 48, 49, 40, 12, 1, 3, 5, 46, 8, 36, 14, 45, 44, 30, 11, 9, 39, 29, 16, 18, 24, 25, 23, 6, 21

93, 95, 78, 79, 99, 90, 74, 61, 92, 77, 100, 64, 98, 97, 63, 73, 85, 67, 54, 56, 80, 1, 2, 89, 4, 91, 6, 94, 8, 96, 10, 14, 15, 18, 21, 23, 24, 25, 27, 29, 30, 31, 34, 37, 39, 41, 45, 47, 49, 50, 51, 52, 53, 55, 57, 58, 59, 60, 62, 65, 66, 68, 69, 70, 71, 72, 75, 76, 81, 82, 83, 84, 86, 87, 88, 20, 35, 17, 33, 19, 22, 48, 3, 11, 46, 44, 38, 40, 36, 32, 16, 13, 12, 9, 7, 26, 42, 43, 28, 5

I don't have the mathematical background to correctly analyze this, but based on what I know about quicksort, this doesn't surprise me a lot. It feels strange, anyway.

This kind of stuff makes me wish I'd taken more math, but my intuition tells me Bruce Schneier would not approve... :-)

#!/usr/bin/perl -w

use strict;

my @oldList = (1 .. 100);
my @newList = sort {rand > .5} @oldList;

print "Numbers:\n", (join "\n", @newList), "\n";
[download]

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;
}
[download]

If there is a problem with my methodology for testing this, I would appreciate it being pointed out.

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

Looks random to me. Check this out:

$loop=5;
{
$total=100000;
for (1..$total) {
  rand > .5 and $x++ and next;
  $y++;
}
$xp=$x/$total*100; $yp=$y/$total*100;
$xd=50-$xp; $yd=50-$yp;
print "X: $x ($xp%) $xd\nY: $y ($yp%) $yd\n";
$loop-- and redo;
}
[download]

Results:

X: 49790 (49.79%) 0.210000000000001
Y: 50211 (50.211%) -0.210999999999991
X: 50071 (50.071%) -0.070999999999998
Y: 49930 (49.93%) 0.0700000000000003
X: 49781 (49.781%) 0.219000000000001
Y: 50220 (50.22%) -0.219999999999999
X: 50080 (50.08%) -0.0800000000000054
Y: 49921 (49.921%) 0.0790000000000006
X: 49898 (49.898%) 0.102000000000004
Y: 50103 (50.103%) -0.102999999999994
X: 50033 (50.033%) -0.0330000000000084
Y: 49968 (49.968%) 0.0319999999999965
[download]