Revision a80e95e4
Added by Leszek Koltunski 12 months ago
src/main/java/org/distorted/objectlib/tablebases/TablebaseHelpers.java | ||
---|---|---|
79 | 79 |
|
80 | 80 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
81 | 81 |
|
82 |
public static void test2(TablebasesAbstract tb, int num)
|
|
83 |
{
|
|
84 |
Random rnd = new Random();
|
|
85 |
int size = tb.getSize();
|
|
82 |
private final static int MAX_PERM=12; // biggest N for which N! is still less than 2^32
|
|
83 |
private final static int[] avail = new int[MAX_PERM];
|
|
84 |
private final static int[] pos = new int[MAX_PERM];
|
|
85 |
private final static int[] fact = new int[MAX_PERM];
|
|
86 | 86 |
|
87 |
for(int i=0; i<num; i++) |
|
88 |
{ |
|
89 |
int next = rnd.nextInt(size-1); |
|
90 |
int[][] moves = tb.solution(next,null,null); |
|
91 |
String moveSeq = print(moves); |
|
92 |
android.util.Log.e("D", (moves==null ? 0 : moves.length)+" Trying "+next+" : "+moveSeq); |
|
93 |
} |
|
94 |
} |
|
87 |
static |
|
88 |
{ |
|
89 |
fact[0] = 1; |
|
90 |
for(int i=1; i<MAX_PERM; i++) fact[i] = fact[i-1]*i; |
|
91 |
}; |
|
95 | 92 |
|
96 | 93 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
97 | 94 |
|
98 |
private static int swaps(int val, int[] buffer, int len)
|
|
95 |
public static void getPermutationFromNum(int[] buffer,int permSize, int permNum)
|
|
99 | 96 |
{ |
100 |
int ret = 0; |
|
97 |
avail[0] = pos[0] = 0; |
|
98 |
for(int i=1; i<permSize; i++) avail[i] = pos[i] = permSize-i; |
|
101 | 99 |
|
102 |
for(int i=0; i<len; i++)
|
|
100 |
for(int i=0; i<permSize-1; i++)
|
|
103 | 101 |
{ |
104 |
if( buffer[i] >val ) ret++; |
|
105 |
else if( buffer[i]==val ) return ret; |
|
102 |
int m = fact[permSize-1-i]; |
|
103 |
int k = permNum/m; |
|
104 |
permNum %= m; |
|
105 |
buffer[i] = avail[k]; |
|
106 |
int y = avail[permSize-1-i]; |
|
107 |
pos[y] = k; |
|
108 |
avail[k] = y; |
|
106 | 109 |
} |
107 | 110 |
|
108 |
return -1;
|
|
111 |
buffer[permSize-1] = avail[0];
|
|
109 | 112 |
} |
110 | 113 |
|
111 | 114 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
112 |
|
|
113 |
public static boolean permutationIsEven(int[] buffer) |
|
115 |
// Enumeration of permutations in linear time. |
|
116 |
// 1) notice that 'avail' and 'pos' are always inverses: avail[m]=n iff pos[n]=m |
|
117 |
// 2) notice that that implies that after the i-th execution of the loop, avail[0 ... n-1-i] |
|
118 |
// contains the n-i elements of the permutation we haven't scanned yet |
|
119 |
// ( that is because this is true initially, and during each loop, we remove avail[k] from |
|
120 |
// this list - but k = pos[buffer[i]] implies buffer[i] = avail[k] so we are really removing |
|
121 |
// buffer[i] - i.e. exactly the permutation element we have just scanned! ) |
|
122 |
// 3) each 'k' is a digit of the permutation in a strange ( n-1,n-2,...,2 ) notation where the most |
|
123 |
// significant digit can be one of the {0...,n-1}, the next most significant - one of the {0,...,n-2}, |
|
124 |
// etc. |
|
125 |
// 4) the ret = ret*(permSize-i) + k is a transform from this ( n-1,n-2,...,2 ) notation to an index. |
|
126 |
|
|
127 |
public static int computePermutationNum(int[] buffer) |
|
114 | 128 |
{ |
115 |
int len = buffer.length; |
|
116 |
int numOfSwaps = 0; |
|
117 |
for(int i=0; i<len-1; i++) numOfSwaps += swaps(i,buffer,len); |
|
118 |
return (numOfSwaps%2==0); |
|
119 |
} |
|
120 |
|
|
121 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
129 |
int permSize = buffer.length; |
|
130 |
avail[0] = pos[0] = 0; |
|
131 |
for(int i=1; i<permSize; i++) avail[i] = pos[i] = permSize-i; |
|
122 | 132 |
|
123 |
public static int computeEvenPermutationNum(int[] permutation) |
|
124 |
{ |
|
125 |
int len = permutation.length-2; |
|
126 | 133 |
int ret = 0; |
127 |
int mul = 4; |
|
128 | 134 |
|
129 |
for(int i=0; i<len; i++)
|
|
135 |
for(int i=0; i<permSize-1; i++)
|
|
130 | 136 |
{ |
131 |
ret += swaps(len-1-i,permutation,len+2); |
|
132 |
|
|
133 |
if( i<len-1 ) |
|
134 |
{ |
|
135 |
ret *= mul; |
|
136 |
mul++; |
|
137 |
} |
|
137 |
int k = pos[buffer[i]]; |
|
138 |
ret = ret*(permSize-i) + k; |
|
139 |
int y = avail[permSize-1-i]; |
|
140 |
pos[y] = k; |
|
141 |
avail[k] = y; |
|
138 | 142 |
} |
139 | 143 |
|
140 | 144 |
return ret; |
... | ... | |
142 | 146 |
|
143 | 147 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
144 | 148 |
|
145 |
public static void getEvenPermutationFromNum(int[] buffer, int permNum)
|
|
149 |
public static int computeEvenPermutationNum(int[] buffer)
|
|
146 | 150 |
{ |
147 |
int permSize = buffer.length; |
|
148 |
int index = permSize; |
|
149 |
int len = permSize-2; |
|
150 |
int totalSwaps = 0; |
|
151 |
|
|
152 |
for(int i=0; i<permSize; i++) buffer[i]=-1; |
|
153 |
|
|
154 |
for(int i=0; i<len; i++) |
|
155 |
{ |
|
156 |
int swaps = (permNum%index); |
|
157 |
permNum /= index; |
|
158 |
index--; |
|
159 |
totalSwaps += swaps; |
|
160 |
|
|
161 |
for(int j=0; j<permSize; j++) |
|
162 |
{ |
|
163 |
if( buffer[j]==-1 ) |
|
164 |
{ |
|
165 |
if( swaps==0 ) |
|
166 |
{ |
|
167 |
buffer[j] = i; |
|
168 |
break; |
|
169 |
} |
|
170 |
swaps--; |
|
171 |
} |
|
172 |
} |
|
173 |
} |
|
174 |
|
|
175 |
int lower, upper; |
|
176 |
|
|
177 |
if( (totalSwaps%2)==0 ) |
|
178 |
{ |
|
179 |
lower = permSize-2; |
|
180 |
upper = permSize-1; |
|
181 |
} |
|
182 |
else |
|
183 |
{ |
|
184 |
lower = permSize-1; |
|
185 |
upper = permSize-2; |
|
186 |
} |
|
151 |
int index = computePermutationNum(buffer); |
|
152 |
return index/2; |
|
153 |
} |
|
187 | 154 |
|
188 |
boolean first=true;
|
|
155 |
///////////////////////////////////////////////////////////////////////////////////////////////////
|
|
189 | 156 |
|
190 |
for(int i=0; i<permSize; i++) |
|
191 |
if( buffer[i]==-1 ) |
|
192 |
{ |
|
193 |
if( first ) |
|
194 |
{ |
|
195 |
buffer[i] = lower; |
|
196 |
first=false; |
|
197 |
} |
|
198 |
else |
|
199 |
{ |
|
200 |
buffer[i] = upper; |
|
201 |
break; |
|
202 |
} |
|
203 |
} |
|
157 |
public static void getEvenPermutationFromNum(int[] buffer, int permNum) |
|
158 |
{ |
|
159 |
getPermutationFromNum(buffer, buffer.length, 2*permNum); |
|
160 |
boolean even = permutationIsEven(buffer); |
|
161 |
if( !even ) getPermutationFromNum(buffer, buffer.length, 2*permNum+1 ); |
|
204 | 162 |
} |
205 | 163 |
|
206 | 164 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
207 | 165 |
|
208 |
public static int computePermutationNum(int[] permutation)
|
|
166 |
private static int swaps(int val, int[] buffer, int len)
|
|
209 | 167 |
{ |
210 |
int len = permutation.length; |
|
211 | 168 |
int ret = 0; |
212 |
int mul = 3; |
|
213 | 169 |
|
214 |
for(int i=0; i<len-2; i++)
|
|
170 |
for(int i=0; i<len; i++) |
|
215 | 171 |
{ |
216 |
ret += swaps(len-2-i,permutation,len); |
|
217 |
ret *= mul; |
|
218 |
mul++; |
|
172 |
if( buffer[i] >val ) ret++; |
|
173 |
else if( buffer[i]==val ) return ret; |
|
219 | 174 |
} |
220 | 175 |
|
221 |
ret += swaps(0,permutation,len); |
|
222 |
|
|
223 |
return ret; |
|
176 |
return -1; |
|
224 | 177 |
} |
225 | 178 |
|
226 | 179 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
227 | 180 |
|
228 |
public static void getPermutationFromNum(int[] buffer,int permSize, int permNum)
|
|
181 |
public static boolean permutationIsEven(int[] buffer)
|
|
229 | 182 |
{ |
230 |
int index = permSize; |
|
231 |
int len = permSize-1; |
|
232 |
|
|
233 |
for(int i=0; i<permSize; i++) buffer[i]=-1; |
|
234 |
|
|
235 |
for(int i=0; i<len; i++) |
|
236 |
{ |
|
237 |
int swaps = (permNum%index); |
|
238 |
permNum /= index; |
|
239 |
index--; |
|
240 |
|
|
241 |
for(int j=0; j<permSize; j++) |
|
242 |
{ |
|
243 |
if( buffer[j]==-1 ) |
|
244 |
{ |
|
245 |
if( swaps==0 ) |
|
246 |
{ |
|
247 |
buffer[j] = i; |
|
248 |
break; |
|
249 |
} |
|
250 |
swaps--; |
|
251 |
} |
|
252 |
} |
|
253 |
} |
|
254 |
|
|
255 |
for(int i=0; i<permSize; i++) |
|
256 |
if( buffer[i]==-1 ) |
|
257 |
{ |
|
258 |
buffer[i] = permSize-1; |
|
259 |
break; |
|
260 |
} |
|
183 |
int len = buffer.length; |
|
184 |
int numOfSwaps = 0; |
|
185 |
for(int i=0; i<len-1; i++) numOfSwaps += swaps(i,buffer,len); |
|
186 |
return (numOfSwaps%2==0); |
|
261 | 187 |
} |
262 | 188 |
|
263 | 189 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
Also available in: Unified diff
implement enumeration of permutations in linear time. This hopefully speeds up all solvers.