可能な変位 (すなわち、シフト) を距離の増加順に反復したいとします。すべての変位は整数であるため、変位の 2 乗は 2 乗の合計である必要があります。次の Python コードは、 x変位ごとに次に考えられるy変位を追跡します。ペアのリストを生成します。各ペアは変位座標を表します。単一のリスト内のすべての要素は、原点から同じ距離にありますが、後のリストからの要素はより大きな距離になります。したがって、少なくとも距離に関しては、内部リストをどの順序でトラバースするかは問題ではありません。それらをランダム化することもできます。
def iter_distance(maxr = 10):
r = 0
d = [0]
while r <= maxr:
m = maxr*maxr + 1
for x, y in enumerate(d):
sq = x*x + y*y
if sq < m:
m = sq
b = []
if sq == m:
b.append((x, y))
for x, y in b:
d[x] = y + 1
if b[-1][0] == r:
r += 1
d.append(0)
yield (b +
[(x, -y) for x, y in b if y] +
[(-x, y) for x, y in b if x] +
[(-x, -y) for x, y in b if x*y])
for lst in iter_distance():
marker = '*'
for x, y in lst:
print("{:5} {:5} {:10} {}".format(x, y, x*x + y*y, marker))
marker = ' '
出力の最初の行は次のようになります。
0 0 0 *
0 1 1 *
1 0 1
0 -1 1
-1 0 1
1 1 2 *
1 -1 2
-1 1 2
-1 -1 2
0 2 4 *
2 0 4
0 -2 4
-2 0 4
1 2 5 *
2 1 5
1 -2 5
2 -1 5
-1 2 5
-2 1 5
-1 -2 5
-2 -1 5
2 2 8 *
2 -2 8
-2 2 8
-2 -2 8
0 3 9 *
3 0 9
0 -3 9
-3 0 9
400 までの距離 (つまり、引数として 400 を渡すmaxr) の場合、37,556 の異なる距離に対して 502,625 行が得られるため、これらをアプリケーションにハードコードするのではなく、その場で生成する必要があります。ただし、これらの番号を使用して、実装を確認することができます.
パフォーマンスが気になる場合は、配列の代わりにプライオリティ キューを使用して、次のように記述できます。
#include <queue>
#include <utility>
#include <cmath>
#include <iostream>
#include <iomanip>
class displacement {
private:
int _d;
int _x;
int _y;
public:
displacement() : _d(0), _x(0), _y(0) {}
displacement(int x, int y) : _d(x*x + y*y), _x(x), _y(y) {}
int x() const { return _x; }
int y() const { return _y; }
int sqd() const { return _d; }
bool operator<(const displacement& d) const { return sqd() > d.sqd(); }
};
static void print2(int x, int y, int sqd) {
std::cout << std::setw(10) << x << ' '
<< std::setw(10) << y << ' '
<< std::setw(20) << sqd << ' '
<< std::endl;
}
static void print1(int x, int y, int sqd) {
print2(x, y, sqd);
if (y)
print2(x, -y, sqd);
if (x) {
print2(-x, y, sqd);
if (y)
print2(-x, -y, sqd);
}
}
int main(int argc, char** argv) {
int maxr = 400;
int maxrsq = maxr*maxr;
std::priority_queue<displacement> q;
q.push(displacement(0, 0));
while (q.top().sqd() <= maxrsq) {
const displacement& d = q.top();
int x = d.x();
int y = d.y();
int sqd = d.sqd();
print1(x, y, sqd);
q.pop();
q.push(displacement(x, y + 1));
if (x == y) {
q.push(displacement(x + 1, y + 1));
}
else {
print1(y, x, sqd);
}
}
}
この場合、キューには個々の変位が含まれており、結果は同じ距離の個々の変位を任意の (おそらく実装定義の) 順序でリストに収集せずに出力します。指定されたディスプレイスメントのミラー イメージのみがすぐに印刷されます。ここのコードは完全な 8 回対称性を採用しているため、キューに一度に格納される要素の数は、最初の部分を除いて、これまでに生成された最大距離よりもさらに少なくなります。