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_ro
:
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
) {
85 scList
= kCoords
.get(i
);
86 zscList
= zielCoords
.get(i
);
87 x
= new PermutationGenerator(scList
.size());
88 for (int j
=0; j
<scList
.size(); ++j
) {
89 minSum
+= scList
.get(j
).distanz(zscList
.get(j
));
93 indices
= x
.getNext();
94 for (int j
=0; j
<scList
.size(); ++j
) {
95 tmpSum
+= scList
.get(j
).distanz(zscList
.get(indices
[j
]));
97 // System.out.println(i + " " + tmpSum);
98 if (minSum
> tmpSum
) {
113 //--------------------------------------
114 // Systematically generate permutations.
115 //--------------------------------------
117 class PermutationGenerator
{
120 private BigInteger numLeft
;
121 private BigInteger total
;
123 //-----------------------------------------------------------
124 // Constructor. WARNING: Don't make n too large.
125 // Recall that the number of permutations is n!
126 // which can be very large, even when n is as small as 20 --
127 // 20! = 2,432,902,008,176,640,000 and
128 // 21! is too big to fit into a Java long, which is
129 // why we use BigInteger instead.
130 //----------------------------------------------------------
132 public PermutationGenerator (int n
) {
134 throw new IllegalArgumentException ("Min 1");
137 total
= getFactorial (n
);
145 public void reset () {
146 for (int i
= 0; i
< a
.length
; i
++) {
149 numLeft
= new BigInteger (total
.toString ());
152 //------------------------------------------------
153 // Return number of permutations not yet generated
154 //------------------------------------------------
156 public BigInteger
getNumLeft () {
160 //------------------------------------
161 // Return total number of permutations
162 //------------------------------------
164 public BigInteger
getTotal () {
168 //-----------------------------
169 // Are there more permutations?
170 //-----------------------------
172 public boolean hasMore() {
173 return numLeft
.compareTo (BigInteger
.ZERO
) == 1;
180 private static BigInteger
getFactorial (int n
) {
181 BigInteger fact
= BigInteger
.ONE
;
182 for (int i
= n
; i
> 1; i
--) {
183 fact
= fact
.multiply (new BigInteger (Integer
.toString (i
)));
188 //--------------------------------------------------------
189 // Generate next permutation (algorithm from Rosen p. 284)
190 //--------------------------------------------------------
192 public int[] getNext () {
194 if (numLeft
.equals (total
)) {
195 numLeft
= numLeft
.subtract (BigInteger
.ONE
);
201 // Find largest index j with a[j] < a[j+1]
203 int j
= a
.length
- 2;
204 while (a
[j
] > a
[j
+1]) {
208 // Find index k such that a[k] is smallest integer
209 // greater than a[j] to the right of a[j]
211 int k
= a
.length
- 1;
212 while (a
[j
] > a
[k
]) {
216 // Interchange a[j] and a[k]
222 // Put tail end of permutation after jth position in increasing order
224 int r
= a
.length
- 1;
235 numLeft
= numLeft
.subtract (BigInteger
.ONE
);