格子点の列挙 in Python DouKaku?

格子点の列挙

二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。

サンプル出力

0, 0
1, 0
0, 1
-1, 0
0, -1
1, 1
-1, 1
1, -1
-1, -1
2, 0

最低でも1000件まで列挙できることを確認してください。また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。

このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。

Perl がなかったので。力技。

use strict;

my $PI = atan2(1, 1) * 4;
my $MAXR = int(sqrt(1000 / $PI) + sqrt(2) + 0.5);
my @res = ();

for (my $i = 0; $i <= $MAXR; $i++) {
    for (my $j = 0; $j <= $MAXR; $j++) {
        my $r = sqrt($i * $i + $j * $j);
        push(@res, [$i, $j, $r, atan2($j, $i)]);
        ($i != 0) && push(@res, [-$i, $j, $r, atan2($j, -$i)]);
        ($j != 0) && push(@res, [$i, -$j, $r, atan2(-$j, $i) + 2 * $PI]);
        ($i * $j != 0) && push(@res, [-$i, -$j, $r, atan2(-$j, -$i) + 2 * $PI]);
    }
}

foreach my $p (sort {($a->[2] <=> $b->[2]) || ($a->[3] <=> $b->[3])} @res) {
    printf("%3d, %3d\n", splice(@{$p}, 0, 2));
}

post comment

Posted feedbacks - Python

1000番目は(-8, 16)？Tkinterで視覚的に表示
するコードもつけました。debug()という関数を
実行してください。

import itertools

def distance2(a):
    x, y = a
    return x * x + y * y

def rotate_90(x, y):
    return -y, x

def grid_points():
    yield (0, 0)
    def grid_points_in_first_quadrant():
        table = [] # index: y, value: x ( y >= 0 and x >= 1 )
        while 1:
            def candidates():
                for y, x in enumerate(table):
                    yield x + 1, y
                yield 1, len(table)
            x, y = min(candidates(), key=distance2)
            yield x, y
            if y < len(table):
                table[y] = x
            else:
                assert y == len(table)
                table.append(x)
    for _, it in itertools.groupby(grid_points_in_first_quadrant(), key=distance2):
        points = list(it)
        for _ in xrange(4):
            for x, y in points:
                yield x, y
            for i in xrange(len(points)):
                points[i] = rotate_90(*points[i])

def debug(): # show points visually
    import Tkinter as Tk
    import math

    root = Tk.Tk()
    canvas = Tk.Canvas(root, width=400, height=400)
    canvas.pack(fill=Tk.BOTH, expand=True)

    def draw_point(x, y):
        y = -y
        n = 10
        m = 5
        offset = 200
        canvas.create_oval(x * n - m + offset, y * n - m + offset, x * n + m + offset, y * n + m + offset, fill="red")

    it = grid_points()
    def command():
        x, y = it.next()
        draw_point(x, y)
        print (x, y), math.hypot(x, y)

    button = Tk.Button(text="Next", command=command)
    button.pack(fill=Tk.X)

    root.mainloop()

def main():
    for x, y in itertools.islice(grid_points(), 1000):
        print "%d, %d" % (x, y)
#   debug()

if __name__ == '__main__':
    main()

xとyのループ範囲の計算方法を#3258から拝借しました(n2の値)。
ただし、なぜこうなるのかは理解できていません。

from math import sqrt

def f0(x, y):
  return (0 if x >= 0 else 1) if y >= 0 else (2 if x < 0 else 3)

def f(a, b):
  return -1 if a[0] < b[0] else 1 if a[0] > b[0] else cmp(a[1], b[1]) if a[1] != b[1] else (-1 if a[2] > b[2] else 1) if a[1] <= 1 else (-1 if a[2] < b[2] else 1)

n = 1000
n2 = int(sqrt(n * 2) / 2)

l = [(sqrt(x**2 + y**2), f0(x, y), x, y) for x in range(-n2, n2+1) for y in range(-n2, n2+1)]

for t in sorted(l, cmp=f)[:n]:
  print t[2], t[3]

ソート用比較関数を見直し。

1000番目の座標は他の人と同じく(-8, 16)になりました。

from math import sqrt

def f((x0, y0, z0), (x1, y1, z1)):
  if z0 < z1: return -1
  if z0 > z1: return 1
  if y0 >= 0:
    if y1 < 0 or x0 > x1: return -1
  else:
    if y1 < 0 and x0 < x1: return -1
  return 1

n = 1000
n2 = int(sqrt(n / 2))

l = [(x, y, sqrt(x**2 + y**2)) for x in range(-n2, n2+1) for y in range(-n2, n2+1)]

for x, y, z in sorted(l, cmp=f)[:n]:
  print x, y

やってることは他の人とほとんど同じだけど、
とりあえず綺麗に書いたつもり。
VBAで仕事した直後で、ループ範囲が混乱したｗ
ちなみに1000番目は(-8, 16)でした

import math

def test(r):
    data = []
    for y in range(-r,r+1):
        for x in range(-r,r+1):
            data.append([x**2 + y **2, x,y])

    def cmp(p1,p2):
        def toInt(d):
            if d<0:
                return -1
            if d>0:
                return 1
            return 0
            
        if p1[0] != p2[0]:
            return toInt(p1[0] - p2[0])
        t1 = math.atan2(p1[2], p1[1])
        t2 = math.atan2(p2[2], p2[1])
        if t1 < 0:
            t1 += math.pi*2
        if t2 < 0:
            t2 += math.pi*2
        return toInt(t1 - t2)

    data.sort(cmp)

    if len(data)> 1000 :
        print "No.1000 is" ,data[1000-1]
    for pos in data:
        print pos[1],pos[2]

test(100)

DouKaku?

格子点の列挙

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq