Dobra robota :) Zajrzałeś do oeis.org albo znalazłeś pomysł na necie, czy wszystko sam wymyśliłeś?
Ja naskrobałem już wersję uogólnioną, która dodatkowo wypisuje parametry scalania:
import java.util.Arrays;
class Tuple {
final int x;
final int y;
final int z;
Tuple(final int x, final int y, final int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
class SmartGenerator {
final int base;
final int length;
int[] values = new int[20];
int[] starts = new int[20];
int[] powers = new int[20];
int direction = 0;
int position = 0;
int upperLimit = 0;
int lowerLimit = 0;
SmartGenerator(final int base, final int length) {
this.base = base;
this.length = length;
Arrays.fill(values, 0);
Arrays.fill(starts, 0);
for (int i = 0, power = 1; i < powers.length; i++) {
powers[i] = power;
power *= base;
}
}
Tuple next() {
if (position == upperLimit) {
upperLimit = lowerLimit;
while (++values[upperLimit] == base) {
values[upperLimit] = 0;
upperLimit++;
}
while (starts[lowerLimit] >= length) {
lowerLimit++;
}
direction ^= (position ^ lowerLimit) & 1;
position = lowerLimit;
} else {
direction ^= 1;
position++;
}
Tuple result = new Tuple(starts[position], powers[position], direction);
starts[position] += powers[position + 1];
return result;
}
}
class DumbGenerator {
final int base;
int[] values = new int[20];
int[] starts = new int[20];
int[] powers = new int[20];
int direction = 0;
int position = 0;
int upperLimit = 0;
DumbGenerator(final int base) {
this.base = base;
Arrays.fill(values, 0);
Arrays.fill(starts, 0);
for (int i = 0, power = 1; i < powers.length; i++) {
powers[i] = power;
power *= base;
}
}
Tuple next() {
if (position == upperLimit) {
upperLimit = 0;
while (++values[upperLimit] == base) {
values[upperLimit] = 0;
upperLimit++;
}
direction ^= position & 1;
position = 0;
} else {
direction ^= 1;
position++;
}
Tuple result = new Tuple(starts[position], powers[position], direction);
starts[position] += powers[position + 1];
return result;
}
}
public class Main {
void run() {
final int base = 3;
int length = 100;
SmartGenerator smartGenerator = new SmartGenerator(base, length);
DumbGenerator dumbGenerator = new DumbGenerator(base);
int start;
int end;
do {
Tuple tuple1;
do {
tuple1 = dumbGenerator.next();
start = tuple1.x;
end = start + tuple1.y * base;
} while (start >= length);
Tuple tuple2 = smartGenerator.next();
if ((tuple1.x != tuple2.x) || (tuple1.y != tuple2.y) || (tuple1.z != tuple2.z)) {
System.out.println("Błąd!");
}
System.out.printf("Start: %8d, stride: %8d, direction: %d\n",
tuple1.x, tuple1.y, tuple1.z);
} while ((start > 0) || (end < length));
}
public static void main(String[] args) {
long nanoTime = System.nanoTime();
new Main().run();
System.out.println("Time: " + (double) (System.nanoTime() - nanoTime) / 1e9 + "s");
}
}
start = od którego miejsca scalać
stride = rozmiary posortowanych podtablic
direction = określa, z której tablicy mamy brać elementy, a do której zapisywać