Allegato "pigeonhole-fixed.pl"
Scarica 1 #!/usr/bin/env perl
2
3 $pigeons=shift;
4 $holes=shift;
5
6 $pigeons > 0 and $holes > 0 or die "Usage: $0 m n\n";
7 @formula=();
8
9 # Variables:
10 # x1,1 ~ 1
11 # ...
12 # xm,1 ~ m
13 # x1,2 ~ m+1
14 # ...
15 # xm,2 ~ 2*m
16 # ...
17 # x1,n ~ (n-1)*m+1
18 # ...
19 # xm,n ~ n*m
20 #
21 # So: xi,j ~ (j-1)*m+i
22
23 # Each pigeon has to be put into some hole.
24 for($i=1; $i <= $pigeons; $i++) {
25 @clause=();
26 for($j=1; $j <= $holes; $j++) {
27 push(@clause, ($j-1)*$pigeons + $i);
28 }
29 push(@formula,join(" ",@clause) . " 0");
30 }
31
32 # At most one hole per pigeon.
33
34 for($i=1; $i <= $pigeons; $i++) {
35 for($j=1; $j <= $holes; $j++) {
36 for($k=1; $k <= $holes; $k++) {
37 if($k != $j) {
38 push(@formula,sprintf("-%d -%d 0", ($j-1)*$pigeons + $i , ($k-1)*$pigeons + $i ));
39 }
40 }
41 }
42 }
43
44 # At most one pigeon per hole.
45
46 for($i=1; $i <= $pigeons; $i++) {
47 for($j=1; $j <= $holes; $j++) {
48 for($k=1; $k <= $pigeons; $k++) {
49 if($k != $i) {
50 push(@formula,sprintf("-%d -%d 0", ($j-1)*$pigeons + $i , ($j-1)*$pigeons + $k ));
51 }
52 }
53 }
54 }
55
56 printf("p cnf %d %d\n",$pigeons*$holes,$#formula+1);
57 foreach (@formula)
58 {
59 print "$_\n";
60 }
Allegati
Non รจ consentito inserire allegati su questa pagina.