| 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 |
///////////////////////////////////////////////////////////////////////////////////////////////////
|
implement enumeration of permutations in linear time. This hopefully speeds up all solvers.