Download code

Jump to: navigation, search

Back to Generating_all_integer_lattice_points_(Python)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

euclidean2d.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Generating_all_integer_lattice_points_(Python)?oldid=17065
14 
15 def distance(p):
16     return p[0]**2 + p[1]**2
17 def generate_N2(limit=None):
18     ymax = [0]
19     d = 0
20     while limit is None or d <= limit:
21         yieldable = []
22         while 1:
23 	    batch = []
24 	    for x in range(d+1):
25 	        y = ymax[x]
26 	        if distance((x, y)) <= d**2:  # Note: distance squared
27 	            batch.append((x, y))
28 	            ymax[x] += 1
29 	    if not batch:
30 	        break
31 	    yieldable += batch
32         yieldable.sort(key=distance)
33         for p in yieldable:
34             yield p
35         d += 1
36         ymax.append(0)     # Extend to make room for column[d]
37 def generate_Z2(limit=None, origin=(0, 0)):
38     for p in generate_N2(limit):
39         p = (p[0]+origin[0], p[1]+origin[1])
40         yield p
41         if p[0] != 0: yield -p[0], p[1]
42         if p[1] != 0: yield p[0], -p[1]
43         if p[0] and p[1]: yield -p[0], -p[1]
44 


hijacker
hijacker
hijacker
hijacker

manhattan2d.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Generating_all_integer_lattice_points_(Python)?oldid=17065
14 
15 def generate_N2(limit=None):
16     d = 0
17     while limit is None or d <= limit:
18         for x in range(d+1):
19             yield x, d-x
20         d += 1
21 def generate_Z2(limit=None, origin=(0, 0)):
22     for p in generate_N2(limit):
23         p = (p[0]+origin[0], p[1]+origin[1])
24         yield p
25         if p[0] != 0: yield -p[0], p[1]
26         if p[1] != 0: yield p[0], -p[1]
27         if p[0] and p[1]: yield -p[0], -p[1]
28 


hijacker
hijacker
hijacker
hijacker

euclidean.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Generating_all_integer_lattice_points_(Python)?oldid=17065
14 
15 def distance(p):
16     return sum(x**2 for x in p)
17 def multirange(dims, m):
18     c = 0
19     for i in xrange(m**dims):
20         x = i
21         r = []
22         for n in range(dims):
23             x, rem = divmod(x, m)
24             r.append(rem)
25         yield tuple(r)[::-1]
26 def generate_Nn(n=2, limit=None):
27     from collections import defaultdict
28     ymax = defaultdict(int) # unknown keys are mapped to 0
29     d = 0
30     while limit is None or d <= limit:
31         yieldable = []
32         while 1:
33             batch = []
34             for x in multirange((n-1), d+1):
35                 y = ymax[x]
36                 pt = x + (y,)
37                 if distance(pt) <= d**2:
38                     batch.append(pt)
39                     ymax[x] += 1
40             if not batch:
41                 break
42             yieldable += batch
43         yieldable.sort(key=distance)
44         for p in yieldable:
45             yield p
46         d += 1
47 testdata = { \
48   0 : [1, 1, 1, 1, 1, 1, 1, 1],
49   1 : [1, 2, 3, 4, 5, 6, 7, 8],
50   2 : [1, 3, 6, 11, 17, 26, 35, 45],
51   3 : [1, 4, 11, 29, 54, 99, 163, 239],
52   4 : [1, 5, 20, 70, 165, 357, 688, 1154],
53   5 : [1, 6, 36, 157, 482, 1203, 2673, 5139],
54   6 : [1, 7, 63, 337, 1319, 3819, 9763, 21374],
55   7 : [1, 8, 106, 702, 3390, 11496, 33792, 83877]
56 }
57 
58 if __name__ == "__main__":
59     for dim in range(8):
60         for lim in range(8):
61             a = list(generate_Nn(n=dim, limit=lim))
62             for i in range(1, len(a)):
63                 assert distance(a[i-1]) <= distance(a[i])
64             assert testdata[dim][lim] == len(a)


hijacker
hijacker
hijacker
hijacker