-
Notifications
You must be signed in to change notification settings - Fork 0
/
mdis.pl
executable file
·168 lines (143 loc) · 7.58 KB
/
mdis.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#!/usr/bin/perl --
use warnings;
use strict;
sub min_dist
{
my $inp= @_ ? shift @_ : undef;
my $len=scalar(@{$inp});
my @pos;
for(my $i=0; $i<$len;$i++)
{
my $v=$inp->[$i];
if( !defined($v) || ($v<0) || ($v>=$len) )
{
die "Found illegal val at $i\n";
}
$pos[$v]=$i;
}
my $min_dist=$len;
my $min_dist_pos;
for( my $i=0; $i<$len-1; $i++)
{
my $p=$i+1;
my $pp;
my $r;
if( $i<$len-2 )
{
$pp=$i+2;
}
$r= abs($pos[$i]-$pos[$p]);
if( defined($pp) && ( abs($pos[$i]-$pos[$pp])<$r ) )
{
$r=abs($pos[$i]-$pos[$pp]);
}
if( ($r<$min_dist) || ($r==$min_dist) && (rand(1)<0.5) )
{
$min_dist=$r;
$min_dist_pos=$i;
}
}
return ($min_dist,$min_dist_pos);
}
my $x;
my $word_size_in_bits = 64;
if( defined( $ARGV[0] ) && ( $ARGV[0] =~ /^\d+$/ ) )
{
$word_size_in_bits = ( $ARGV[0] + 0 );
}
for( my $i=0; $i<$word_size_in_bits; $i++)
{
push( @$x, $i );
}
my $curmin=0;
my $curmin_round=0;
my $len=scalar(@$x);
srand();
my $random_match=0;
my $min_match=0;
my ($min_dist,$min_dist_pos)=min_dist( $x );
for(my $round=1;;$round++)
{
if( $min_dist>$curmin )
{
print "Round: $round, random matches: $random_match, min matches: $min_match\n";
print "$min_dist: ".join(",",@$x )."\n";
$curmin=$min_dist;
$curmin_round=$round;
} elsif ( $round % 100000 == 0 ) {
print "Round: $round, random matches: $random_match, min matches: $min_match\n";
}
my @old;
my $subroundsize=3;
my ( $a,$v,$min_dist2,$min_dist_pos2 );
if( ( int(1.8 * $curmin_round)+3000 < $round) && ($curmin>2) )
{
$curmin-=2;
$curmin_round=$round;
$min_dist=$curmin;
print "Round: $round, set back to $curmin\n";
$subroundsize=$len;
} else {
@old = @$x;
do
{
$a=int( rand($len) );
} while( $a == $min_dist_pos );
$v=$x->[$min_dist_pos];
$x->[$min_dist_pos]=$x->[$a];
$x->[$a]=$v;
($min_dist2,$min_dist_pos2)=min_dist( $x );
if($min_dist2>=$min_dist)
{
$min_dist=$min_dist2;
$min_dist_pos=$min_dist_pos2;
$min_match++;
} else {
@$x=@old;
}
}
for( my $subround=0,my $stop=0; ($stop<$subroundsize*8) && ($subround<$subroundsize); $stop++)
{
@old = @$x;
my $b=int( rand($len) );
do
{
$a=int( rand($len) );
} while( $a == $b );
$v=$x->[$b];
$x->[$b]=$x->[$a];
$x->[$a]=$v;
($min_dist2,$min_dist_pos2)=min_dist( $x );
if($min_dist2>=$min_dist)
{
$min_dist=$min_dist2;
$min_dist_pos=$min_dist_pos2;
$random_match++;
$subround++;
} else {
@$x=@old;
}
}
}
# 16
# 5: 5,8,11,14,1,4,7,10,13,0,3,6,9,15,12,2
# 5: 10,7,4,1,14,11,8,5,2,15,12,9,6,3,0,13
# 5: 10,7,4,1,14,11,8,5,2,15,12,9,6,3,0,13
# 32
# 9: 5,8,15,19,22,25,11,28,31,1,4,14,17,7,23,20,26,29,10,0,3,16,13,6,21,24,27,30,9,2,18,12
# 9: 26,29,23,16,19,13,10,7,4,1,27,24,30,21,15,12,18,9,6,0,3,31,22,25,14,28,17,11,8,5,2,20
# 64
# 19: 58,52,61,39,8,2,55,5,11,14,17,42,20,45,23,48,32,29,35,26,51,60,38,63,1,54,4,7,57,13,16,10,41,22,19,47,44,34,28,50,25,31,37,0,53,62,6,59,56,15,9,12,40,21,18,3,46,43,49,27,24,36,33,30
# 19: 33,30,11,8,5,27,24,46,2,61,43,58,49,52,40,21,18,15,37,34,31,12,55,9,28,6,25,3,0,62,44,47,59,41,22,50,19,16,38,35,13,56,53,10,29,26,32,4,1,63,7,60,45,42,23,48,20,39,36,17,14,57,51,54
# 19: 27,61,24,55,58,49,21,18,52,12,46,43,9,15,6,0,3,40,34,37,28,31,25,56,62,59,22,50,53,19,44,47,13,16,10,7,4,41,38,1,35,32,26,29,63,23,57,51,20,60,45,48,54,17,8,5,42,39,2,36,14,33,30,11
# 19: 2,39,55,58,33,52,27,36,30,18,24,21,15,46,12,62,49,9,43,6,0,40,59,3,53,56,37,34,31,28,25,22,16,13,19,50,47,10,44,7,63,41,4,1,60,57,54,38,35,29,26,23,14,17,20,48,51,32,11,8,42,5,45,61
# 19: 58,18,27,21,24,43,52,55,46,49,12,3,40,37,15,34,9,6,31,59,62,28,0,25,19,22,56,53,44,47,50,41,38,13,35,16,7,4,32,10,29,63,1,26,60,57,23,20,54,51,48,45,39,36,17,14,42,33,8,11,30,2,5,61
# 19: 24,27,12,15,18,21,61,58,52,55,9,49,46,40,43,34,31,37,0,6,28,3,25,16,13,22,19,62,59,56,53,50,47,44,10,41,32,38,7,35,29,4,1,26,23,17,20,63,14,54,60,51,45,11,42,57,48,8,39,36,5,33,2,30
# 19: 24,11,14,2,5,61,58,8,46,55,21,52,31,49,43,34,28,40,37,18,25,15,12,0,3,62,59,9,56,6,22,53,50,44,47,32,41,35,38,19,16,26,29,1,13,63,60,10,7,23,4,57,54,48,51,42,33,36,45,39,17,20,30,27
# 128
# 36: 11,119,116,2,110,33,30,73,70,113,36,27,5,8,86,104,67,107,55,92,58,24,52,61,101,98,95,89,18,49,21,126,64,46,43,40,77,123,120,117,80,83,15,74,12,31,111,114,71,3,6,9,37,108,0,28,34,68,53,25,102,105,93,96,56,50,99,22,65,59,47,44,90,62,19,41,87,127,78,121,13,124,84,81,16,72,115,7,38,75,109,4,32,10,112,1,69,118,26,94,35,51,106,100,54,57,23,66,97,45,20,103,63,60,48,88,42,91,122,85,17,29,125,82,39,14,79,76
# 35: 42,77,2,14,64,89,92,98,86,125,83,80,122,61,104,95,101,116,113,5,24,110,119,27,8,58,36,74,33,107,46,55,71,18,30,11,52,21,49,15,39,68,65,1,90,43,84,81,126,62,87,93,96,114,99,4,78,117,123,7,120,59,111,34,102,108,56,75,105,25,72,53,31,28,47,19,40,50,16,37,10,44,69,0,22,63,13,82,91,66,127,94,79,3,6,118,88,124,97,112,121,109,60,115,100,103,85,32,76,106,73,54,48,51,38,35,29,70,45,20,26,17,9,57,12,23,67,41
# 34: 11,2,17,81,14,48,20,97,33,119,122,23,69,113,75,107,72,78,63,66,85,88,60,110,116,91,94,51,54,57,26,42,39,29,104,1,36,4,101,13,7,10,82,45,123,126,16,32,19,98,22,120,70,76,79,67,86,64,73,61,114,49,52,117,58,55,95,111,105,25,92,108,3,89,40,102,37,28,9,6,0,46,83,43,31,127,18,124,21,68,34,99,15,74,80,71,77,121,62,50,12,59,65,56,53,112,24,93,90,87,118,103,38,115,8,5,47,96,41,84,106,44,30,27,109,125,100,35
# 256
# 60: 19,50,117,189,25,22,170,217,44,92,68,249,28,125,201,245,150,15,192,223,129,132,64,105,71,38,147,204,47,87,207,81,75,220,153,101,156,111,144,34,41,84,135,165,31,159,95,162,141,114,236,239,233,9,186,54,183,138,253,98,60,57,0,230,227,180,51,216,174,78,6,20,171,210,250,177,12,23,121,197,16,213,168,200,243,108,3,194,124,63,128,66,48,88,203,91,224,152,219,246,45,131,102,155,35,191,26,158,72,134,29,39,82,112,164,149,115,94,146,206,188,161,118,137,240,237,55,97,52,231,185,228,7,234,143,140,182,176,254,42,79,18,179,209,199,21,173,169,85,58,76,32,215,106,251,212,13,69,126,10,90,247,49,61,109,103,225,202,196,122,4,100,65,133,1,154,37,221,166,73,151,244,24,218,205,241,113,130,119,53,187,46,193,163,27,142,232,116,160,43,96,136,93,139,181,148,178,184,86,175,77,83,238,229,235,56,252,208,157,30,70,172,17,190,80,40,107,11,198,127,123,14,226,255,5,8,99,214,59,211,222,36,89,67,167,74,242,62,145,248,110,120,2,195,33,104
# 59: 228,2,220,149,19,160,81,189,152,78,217,186,232,103,66,125,225,25,57,5,183,106,89,208,163,39,95,42,211,84,128,141,29,214,170,180,157,193,71,196,174,248,54,239,202,45,22,254,48,60,92,242,137,51,177,205,74,134,236,199,121,36,131,251,118,222,109,229,167,98,219,63,146,245,233,12,101,112,190,26,80,6,18,124,226,115,153,164,15,209,86,140,212,143,3,30,181,0,9,156,67,161,171,150,83,44,77,33,184,215,240,90,56,104,21,178,41,237,127,73,203,38,93,50,175,206,70,197,53,200,59,130,230,246,252,218,234,223,249,96,243,133,47,27,113,122,116,107,255,188,16,13,142,4,110,210,168,119,136,87,227,145,10,148,158,155,32,79,99,151,82,139,194,35,62,182,165,185,7,24,102,238,75,91,162,207,1,191,69,204,176,65,173,129,231,43,179,235,52,198,58,55,132,46,213,216,94,105,253,114,14,201,247,123,241,20,49,244,117,224,28,108,250,88,144,154,159,97,126,85,135,147,31,221,111,37,34,72,138,169,166,195,17,40,100,11,187,68,120,76,64,8,192,172,23,61