3 import java
.math
.BigInteger
;
9 SteinCoords(int x
, int y
) {
13 public int distanz(SteinCoords sc
) {
14 return Math
.abs(x
- sc
.x
) + Math
.abs(y
- sc
.y
);
20 Index 2 -> Zweier horizontal
21 Index 3 -> Zweier vertikal
23 ArrayList
< ArrayList
<SteinCoords
> > zielCoords
= new ArrayList
< ArrayList
<SteinCoords
> >();
25 ArrayList
< ArrayList
<SteinCoords
> > findCoords(Knoten k
) {
27 ArrayList
<SteinCoords
> einer
= new ArrayList
<SteinCoords
>();
28 ArrayList
<SteinCoords
> zweier_horiz
= new ArrayList
<SteinCoords
>();
29 ArrayList
<SteinCoords
> zweier_vertik
= new ArrayList
<SteinCoords
>();
30 ArrayList
<SteinCoords
> vierer
= new ArrayList
<SteinCoords
>();
33 int[][] feld
= k
.get_spielfeld();
34 for(int x
= 0; x
< feld
.length
; ++x
) {
35 for(int y
= 0; y
< feld
[0].length
; ++y
) {
38 sc
= new SteinCoords(x
,y
);
41 case Knoten
.zweier_links
:
42 sc
= new SteinCoords(x
,y
);
45 case Knoten
.zweier_oben
:
46 sc
= new SteinCoords(x
,y
);
47 zweier_vertik
.add(sc
);
49 case Knoten
.vierer_lo
:
50 sc
= new SteinCoords(x
,y
);
58 ArrayList
<ArrayList
<SteinCoords
>> coords
= new ArrayList
<ArrayList
<SteinCoords
>>();
60 coords
.add(zweier_horiz
);
61 coords
.add(zweier_vertik
);
67 MinSchritte(Knoten ziel
) {
71 void setZielCoords(Knoten ziel
) {
72 zielCoords
= findCoords(ziel
);
75 int computeLuftlinie(Knoten k
) {
77 PermutationGenerator x
;
80 ArrayList
<ArrayList
<SteinCoords
>> kCoords
= findCoords(k
);
81 ArrayList
<SteinCoords
> scList
, zscList
;
83 for (int i
=0; i
<4; ++i
) {
86 scList
= kCoords
.get(i
);
87 zscList
= zielCoords
.get(i
);
88 x
= new PermutationGenerator(scList
.size());
91 indices
= x
.getNext();
92 for (int j
=0; j
<scList
.size(); ++j
) {
93 tmpSum
+= scList
.get(j
).distanz(zscList
.get(indices
[j
]));
95 if (minSum
> tmpSum
) {
106 //--------------------------------------
107 // Systematically generate permutations.
108 //--------------------------------------
110 class PermutationGenerator
{
113 private BigInteger numLeft
;
114 private BigInteger total
;
116 //-----------------------------------------------------------
117 // Constructor. WARNING: Don't make n too large.
118 // Recall that the number of permutations is n!
119 // which can be very large, even when n is as small as 20 --
120 // 20! = 2,432,902,008,176,640,000 and
121 // 21! is too big to fit into a Java long, which is
122 // why we use BigInteger instead.
123 //----------------------------------------------------------
125 public PermutationGenerator (int n
) {
127 throw new IllegalArgumentException ("Min 1");
130 total
= getFactorial (n
);
138 public void reset () {
139 for (int i
= 0; i
< a
.length
; i
++) {
142 numLeft
= new BigInteger (total
.toString ());
145 //------------------------------------------------
146 // Return number of permutations not yet generated
147 //------------------------------------------------
149 public BigInteger
getNumLeft () {
153 //------------------------------------
154 // Return total number of permutations
155 //------------------------------------
157 public BigInteger
getTotal () {
161 //-----------------------------
162 // Are there more permutations?
163 //-----------------------------
165 public boolean hasMore() {
166 return numLeft
.compareTo (BigInteger
.ZERO
) == 1;
173 private static BigInteger
getFactorial (int n
) {
174 BigInteger fact
= BigInteger
.ONE
;
175 for (int i
= n
; i
> 1; i
--) {
176 fact
= fact
.multiply (new BigInteger (Integer
.toString (i
)));
181 //--------------------------------------------------------
182 // Generate next permutation (algorithm from Rosen p. 284)
183 //--------------------------------------------------------
185 public int[] getNext () {
187 if (numLeft
.equals (total
)) {
188 numLeft
= numLeft
.subtract (BigInteger
.ONE
);
194 // Find largest index j with a[j] < a[j+1]
196 int j
= a
.length
- 2;
197 while (a
[j
] > a
[j
+1]) {
201 // Find index k such that a[k] is smallest integer
202 // greater than a[j] to the right of a[j]
204 int k
= a
.length
- 1;
205 while (a
[j
] > a
[k
]) {
209 // Interchange a[j] and a[k]
215 // Put tail end of permutation after jth position in increasing order
217 int r
= a
.length
- 1;
228 numLeft
= numLeft
.subtract (BigInteger
.ONE
);