Talk:Generating all integer lattice points (Python)

From LiteratePrograms
Jump to: navigation, search

To do 1: generalize to n dimensions

To do 2: figure out how to do it by Euclidean distance. I'm kind of stuck here -- any ideas? Maybe something similar to the classical functional algorithm for Hamming numbers is possible? Perhaps first generate all combinations having the next distance (if so, how?) and for each combination generate each of its permutations? Help would be appreciated. Fredrik 04:37, 26 July 2006 (PDT)

I've now implemented the case n=2 with the simplest geometrical approach I could think of... the solution seems decent to me, but perhaps d should be increased (dynamically) for efficiency. Fredrik 07:30, 26 July 2006 (PDT)

[edit] Animation code

Code used to view animation/generate the animation frames:

from pygame import *
from pygame.draw import rect
from pygame.image import save
from time import sleep
from random import randrange

midpoint, gridsize = 200, 20
colors = [(255,127,0),(247,216,4),(0,143,210),(0,214,236),(78,44,163)]
screen = display.set_mode((midpoint*2, midpoint*2), 0, 32)
screen.fill((255, 255, 255))

def blitpoint(x, y, color, frame):
    xpos = midpoint + gridsize*x
    ypos = midpoint + gridsize*y
    rect(screen, color, Rect(xpos-9,ypos-9,18,18))
    save(screen, "lattice%03i.bmp"%frame)

def plotlattice(generator):
    for x in range(0, midpoint*2+1, gridsize):
        for y in range(0, midpoint*2+1, gridsize):
            rect(screen, (128, 128, 128), Rect(x-1,y-1,2,2))
    frame = 0
    for p in generator(8):
        frame += 1
        while True:
            ev = event.poll()
            if ev.type == NOEVENT: break
            if ev.type == QUIT or ev.type == KEYDOWN: raise SystemExit

For the Euclidean plot, I changed the color selection code to colors[int(distance(p[0],p[1])**0.5+0.5)%5]. Fredrik 07:53, 26 July 2006 (PDT)