From f6ae8515d4140f959d3f1d4a83a19156acd151f2 Mon Sep 17 00:00:00 2001 From: David Gowers <00ai99@gmail.com> Date: Mon, 29 Dec 2008 00:17:55 +1030 Subject: [PATCH] * functions to calculate ** common denominator ** factorials ** exact divisors ** number of permutations (corrected, efficient routine) * better pylint conformance for ion.n.coord * better, numpy standard conformant docstrings for many things --- ion/__init__.py | 19 ++++--- ion/n/__init__.py | 75 ++++++++++++++++++++++++++- ion/n/coord.py | 150 ++++++++++++++++++++++++++++-------------------------- ion/n/random.py | 94 +++++++++++++++++++++++++++++----- ion/sort.py | 43 ++++++++++------ 5 files changed, 272 insertions(+), 109 deletions(-) diff --git a/ion/__init__.py b/ion/__init__.py index 2982cf6..9ae3023 100644 --- a/ion/__init__.py +++ b/ion/__init__.py @@ -17,7 +17,7 @@ class LengthMismatch (ValueError): pass -def seqorsingle (v, datatype): +def seqorsingle (value, datatype): """Return a sequence of 'scalar's from a scalar or sequence of scalars. Parameters @@ -32,18 +32,21 @@ def seqorsingle (v, datatype): Returns ------- seq : sequence (or unmatched scalar) + + + XXX could be apropos to numpy.alen / numpy.asarray """ - vtype = type (v) + vtype = type (value) try: _ = datatype.__iter__ - for T in datatype: - if vtype == T: - return (v,) - return v + for type in datatype: + if vtype == type: + return (value,) + return value except AttributeError: if datatype == vtype: - return (v,) - return v + return (value,) + return value def limititer (iter, num = 1): """Iterates through the first of the items in an iterable. diff --git a/ion/n/__init__.py b/ion/n/__init__.py index b5ea3ee..9ddca0e 100644 --- a/ion/n/__init__.py +++ b/ion/n/__init__.py @@ -190,6 +190,79 @@ def limits (kind): return info.min, info.max raise ValueError ('Invalid input %r' % kind) +def common_denominator (src, dest): + """ Find a common denominator between two numbers. + + Parameters + ---------- + src : {integer, float} + Must be <= dest + dest : {integer, float} + + Returns + ------- + common : {integer, float, None} + src * n where n is an integer, + such that common / dest is also an integer. + After 256 iterations without success, bails out, returning None. + + Examples + -------- + + >>> common_denominator (6, 48) + 48 + + thus, the second term can be expressed as 48/48, and the first as 6/48 + ; or as 8/8 and 1/8. + + """ + i = 1 + while i < 256: + if (i * src) % dest == 0: + return i * src + i += 1 + return None + +def factorial (value): + """Return the factorial of an integer. + + Parameters + ---------- + value: integer + + Returns + ------- + factorial: {integer, long} + Product of all the terms in the series + N * N - 1 * N - 2 ... * 1 + """ + i = 1 + curvalue = 1 + while i <= value: + curvalue *= i + i += 1 + return curvalue + +def npermutations_new (nsamples, nitems): + if (nitems < 1) or (nsamples < 0) or (nsamples > nitems): + raise ValueError ('nitems out of range') + return factorial (nitems) / factorial (nitems - nsamples) + + +def divisors (value): + """Return all values that divide exactly into a target value. + + Parameters + ---------- + value: integer + + Returns + ------- + divisors: list of integers + All integers less than ``value`` which divide into ``value`` + with no remainder. + """ + return [v for v in range (1, (value + 2) / 2) if (value % v) == 0] import math golden = golden_ratio = (1 + math.sqrt(5)) / 2 @@ -226,4 +299,4 @@ def interplog_factor (factor = .5, base = 2): import math ifactor = 1.0 - factor logfactor = math.log(((base ** 1) * ifactor) + ((base ** 2) * factor), base) - 1.0 - return logfactor \ No newline at end of file + return logfactor diff --git a/ion/n/coord.py b/ion/n/coord.py index f1b06d4..8fb6823 100644 --- a/ion/n/coord.py +++ b/ion/n/coord.py @@ -2,23 +2,24 @@ from math import cos, sin, sqrt, atan class Grid: - def __init__(self, w = 16, h = 16, ox = 0, oy = 0): - self.w = w - self.h = h - self.offsetx = ox - self.offsety = oy + def __init__(self, width = 16, height = 16, + offsetx = 0, offsety = 0): + self.w = width + self.h = height + self.offsetx = offsetx + self.offsety = offsety - def snap (self,*coord): + def snap (self, *coord): """Return the specified coordinates snapped to the grid.""" try: result = [] for i in range (0, len(coord), 2): - x,y = coord[i:i+2] + x, y = coord[i:i+2] x = ((x - self.offsetx + (self.w / 2 + 1)) / self.w) * self.w y = ((y - self.offsety + (self.h / 2 + 1)) / self.h) * self.h - x += self.offsetx; - y += self.offsety; - result.append ((x,y)) + x += self.offsetx + y += self.offsety + result.append ((x, y)) return result except TypeError: raise TypeError ('coords (%r) are of wrong type' % coords) @@ -27,13 +28,13 @@ class Grid: try: result = [] for i in range (0, len(coord), 2): - x,y = coord[i:i+2] + x, y = coord[i:i+2] x = (x - self.offsetx) / self.w y = (y - self.offsety) / self.h - result.append ((x,y)) + result.append ((x, y)) return result except TypeError: - raise TypeError ('coords (%r) are of wrong type' % coords) + raise TypeError ('coords (%r) are of wrong type' % (coord,)) def cellspan (self, *cells): """Return slices corresponding to the area of the given cells. @@ -56,66 +57,70 @@ class Grid: return [True] * len (cells) def __repr__ (self): - return '%s (%d, %d, %d, %d)' % (self.__class__.__name__, self.w, self.h, self.offsetx, self.offsety) + return '%s (%d, %d, %d, %d)' % (self.__class__.__name__, + self.w, self.h, + self.offsetx, self.offsety) def subdivide (values, n = 1): """ Subdivide the array-like 'values'. for example - >>> subdivide ([0, 1]) + >>> subdivide ([0, 1]) [0, 0.5, 1] - - Linear subdivision is always available. Quadratic (n=2), cubic (n = 3) and quintic (n = 5) subdivision - is only available if scipy is. - - Returns an array-like object (always an array if numpy is available) + + Linear subdivision is always available. + Quadratic (n=2), cubic (n = 3) and + quintic (n = 5) subdivision is only available if scipy is. + + Returns an array-like object (always an array if numpy is available) """ assert len(values) > 1 finalsize = (len (values) * 2) - 1 try: - import numpy - if n == 1: - result = numpy.zeros(shape = (finalsize,)) - result[0::2] = values - result[1::2] = (values[0:-1] + values [1:]) / 2.0 - return result - else: - from scipy.interpolate import InterpolatedUnivariateSpline as SPL - x = list (range (len (values))) - y = values - samplepoints = subdivide (x, n = 1) - spline = SPL (x, y, n = n) - return spline (samplepoints) + import numpy + if n == 1: + result = numpy.zeros(shape = (finalsize,)) + result[0::2] = values + result[1::2] = (values[0:-1] + values [1:]) / 2.0 + return result + else: + from scipy.interpolate import InterpolatedUnivariateSpline as SPL + x = list (range (len (values))) + y = values + samplepoints = subdivide (x, n = 1) + spline = SPL (x, y, n = n) + return spline (samplepoints) except: - assert (n == 1) - result = [0] * finalsize - result[0::2] = values - result[1::2] = [(a + b) / 2.0 for a,b in zip (values[0:-1], values[1:])] - return result + assert (n == 1) + result = [0] * finalsize + result[0::2] = values + result[1::2] = [(a + b) / 2.0 \ + for a, b in zip (values[0:-1], values[1:])] + return result def iSpline (x, y, k = 3, check = None): """ Sanitized spline-fitting. Returns a InterpolatedUnivariateSpline, with certain guarantees about generated y-values. - - For example, on a segment like: - [0, 300, 1000, -100, 300, 0, 1000, 50, 0], - - where values < 0 show up in the last segment (eg -398.59 at midpoint) - we can subdivide using 'averageslope' (divide the greater value by the lesser value on each side, average these and add - it to the lesser value) - - in this position, averageslope is ((1000 / 50) + ( 0 / 0 (assumed 0))) / 2, = 10. - 0 + 10 = 10 - - a bad spot is still present between 50 and 10 (-23), so another averageslope subdiv: - - ((50 / 10) + (0 / 0 (assumed 0))) / 2. = 2.5 - 10 + 2.5 = 12.5 - - Solved! - - """ + + For example, on a segment like: + [0, 300, 1000, -100, 300, 0, 1000, 50, 0], + + where values < 0 show up in the last segment (eg -398.59 at midpoint) + we can subdivide using 'averageslope' (divide the greater value by the lesser value on each side, average these and add + it to the lesser value) + + in this position, averageslope is ((1000 / 50) + ( 0 / 0 (assumed 0))) / 2, = 10. + 0 + 10 = 10 + + a bad spot is still present between 50 and 10 (-23), so another averageslope subdiv: + + ((50 / 10) + (0 / 0 (assumed 0))) / 2. = 2.5 + 10 + 2.5 = 12.5 + + Solved! + + """ def polardistance (r1, t1, r2, t2): # per wikipedia 'polar distance' @@ -130,16 +135,16 @@ def cartesian (rad, theta, roundness = 1.0): x = rad * cos (theta) y = rad * sin (theta) - return x,y + return x, y #@testing -def polar (x,y, roundness = 1.0): +def polar (x, y, roundness = 1.0): """Maps cartesian->polar coordinates. Expects values in the range [-inf..0..+inf], not [0..+inf]. """ # XXX simplify using atan2() - if (x,y) == (0,0): - return (0,0) + if (x, y) == (0, 0): + return (0, 0) elif x == 0: # # 90deg @@ -151,7 +156,7 @@ def polar (x,y, roundness = 1.0): # -90deg # theta = -1.5707963267948966 * max (-1, min(y,1)) - return abs(y), theta + return abs(y), theta rad = sqrt (x*x + y*y); theta = atan (y/x); return rad, theta @@ -165,9 +170,9 @@ def polar (x,y, roundness = 1.0): #y z # # r a -# Given that the point o is the centre of the triangle, o = 0,0 polar +# Given that the point o is the centre of the triangle, o = 0, 0 polar # -# x = 1,0 +# x = 1, 0 # y = 1, # z = 1, # a good depiction for color weighting is @@ -179,7 +184,8 @@ def polar (x,y, roundness = 1.0): # y.......z # yyyyyyzzzzz # -# where xyz are the respective colors, . is the resultant color, and % is the triangle position of the weighting. +# where xyz are the respective colors, . is the resultant color, and % +# is the triangle position of the weighting. # # 11x11 triangle # @@ -203,7 +209,7 @@ _twz = (1.0, 4.1887902047863905) # x yz y xz z xy _twordermap = {0:(1,2), 1:(0,2), 2:(0,1)} -def triangleWeighting (radius, theta, *xyz): +def triangle_weighting (radius, theta, *xyz): """Convert polar coords relative to the center of a triangle, to weights. Parameters @@ -229,17 +235,19 @@ def triangleWeighting (radius, theta, *xyz): """ if radius == 0: - return (1,1,1) + return (1, 1, 1) # first, find the point that's furthest. - disttocorners = [polardistance (radius, theta, r, t) for r,t in (_twx,_twy,_twz)] + disttocorners = [polardistance (radius, theta, r, t) \ + for r,t in (_twx,_twy,_twz)] # for the two others, it's useful to also know their radial distance # (ie distance if the point was on the edge of the triangle) - raddistance = [polardistance (1.0, theta, r, t) for r,t in (_twx,_twy,_twz)] + raddistance = [polardistance (1.0, theta, r, t) \ + for r,t in (_twx,_twy,_twz)] opposing = disttocorners.index (max (disttocorners)) close, closest = _twordermap[opposing] if raddistance[close] > raddistance[closest]: close, closest = closest, close - muls = [0,0,0] + muls = [0, 0, 0] muls[close] = raddistance[close] muls[closest] = raddistance[closest] muls[opposing] = (1.0 - radius) * 0.5 @@ -255,4 +263,4 @@ def triangleWeighting (radius, theta, *xyz): #for i in [0,8,16,24,32,40,48]: # print((i+5,i+5),g.snap(i+1,i+1)) -__ALL__ = ('triangleWeighting', 'polar', 'cartesian', 'polardistance', 'Grid') +__ALL__ = ('triangle_weighting', 'polar', 'cartesian', 'polardistance', 'Grid') diff --git a/ion/n/random.py b/ion/n/random.py index ba621fc..dc2feb1 100644 --- a/ion/n/random.py +++ b/ion/n/random.py @@ -88,6 +88,10 @@ def boxfill (seq, status, weights = None): spread using this when the option to drop one of several is available. Returns an element from seq; Updates status in-place. + + See also + -------- + dispense """ # could optimize this using digitization if weights: @@ -155,13 +159,29 @@ def weightedSample (seq, weights): # DODO use generator instead def dispense (contents, status, n = 1): """Dispense the contents of a box. - Status should be an empty container. It will mirror the box contents, except things will actually be removed from it. - - Supplying a value for n will dispense more than one item at a time, similar to stdlib's random.sample() - - Box remains unchanged. Status is sure to change. + + Parameters + ---------- + contents: sequence + Collection of items to dispense + status: list + Which items have not been dispensed already. + If you pass ``status = []`` it will be automatically initialized to all of the contents. + Status will be modified in-place during calls to ``dispense()`` + num: integer + Number of items to dispense + + Returns + ------- + items: sequence + Collection of items dispensed. May include None, when there are + not enough items remaining in the box to dispense ``num`` items. + + Notes + ----- + Save the contents of ``status`` if you want to persist the state. + ``contents`` is never modified. - The box may be refilled initially. When deciding which items to return, it will not be refilled; an empty box means that None values will be added instead. """ if len(status) < 1: # init @@ -174,15 +194,33 @@ def dispense (contents, status, n = 1): return tmp[0] return tmp -def affinitySample (items, data, samples): - """since 2007-05-17 - Sampling weighted by affinity. - - Picks one or more items related to *items* and returns it. +def affinitySample (items, data, samples = 1): + """Sampling weighted by affinity. + + Parameters + ---------- + items: sequence + Group of 1 or more items which are related, represented as IDs + data: map + Intimacy data. + Keys are item IDs, values are sequences of related item IDs + All item IDs referenced must have an entry in ``data``. + samples: integer + Number of related items to find + + Returns + ------- + sampled: sequence + sequence of item IDs of length ``samples`` + + Notes + ----- + Good for selecting partially or entirely themed sets. + + Sparse matrix might work better here. The first sample is picked randomly, if items[] is empty. Subsequent samples are required to be related increasingly intimately with the other samples. - This is good for selecting themed or mostly-themed sets of items. data should hold intimacy data. { @@ -333,7 +371,18 @@ def cumulative_to_simple_weights (factors): def percent(p): - " Return True p% of the time, else False" + """Return True p% of the time, + + Parameters + ---------- + p: integer + Percentage chance + + Returns + ------- + success: bool + Whether the percentage roll succeeded + """ if randint (1, 100) <= p: return True else: @@ -440,7 +489,24 @@ def chain (pairs): raise StopIteration() def diceroll (dice, sides): - """Rolls dice infinitely""" + """Roll dice infinitely + + Parameters + ---------- + dice: integer + Number of dice to roll + sides: integer + Number of sides on the dice + + Returns + ------- + value,...: integer + Values in the range [``dice``..``dice*sides``] + + Notes + ----- + Normally used in combination with ``ion.limititer()`` + """ minval = sides maxval = dice * sides while 1: diff --git a/ion/sort.py b/ion/sort.py index 91969f8..904bb52 100644 --- a/ion/sort.py +++ b/ion/sort.py @@ -40,19 +40,32 @@ def byweighted_template (sequence, key, weight = (1, )): return seq def bytemplate (template, src, key, weight = (1, )): - """Arrange src to closest match template. Each item in src is only - used once in the result. + """Reorder sequence to closest match template. - key is a function that accepts an item and returns a number or - tuple of numbers. - Tuples must all have same length. - It is used, along with weight[] to calculate distance between two items. - Weight specifies the weight of each component of the tuples; - So for instance, when sorting colors via RGB, you could specify - - Items in template and src must all be understandable to key(). - - Returns a new list with the items in sorted order. + Parameters + ---------- + template: sequence + Each item must be of a type suitable to pass to ``key()`` + src: sequence + Must also produce comparable values when items are passed to ``key()`` + key: function + Must return + weight: sequence + each item must contain one or more weights, according to the + dimensionality of ``template`` and ``src``, + indicating how important it is to map each ``src`` value accurately. + weight can match src in one of three ways: + weight.shape = (1,NCHANNELS) # a weight for each data channel + weight.shape = (NITEMS, 1) # a weight for each data item + weight.shape = (NITEMS, NCHANNELS) # a weighting for each part of + each item + + Returns + ----- + sorted: list + New list, containing items from ``src`` sorted to match + ``template``. + Each item from ``src`` occurs exactly once in ``sorted``. """ def key2 (v): return v[1] @@ -63,7 +76,7 @@ def bytemplate (template, src, key, weight = (1, )): # make sure that all comparable values in the template get placed first. todo = enumerate (tempval) # todo = weightedSort (todo, key2, weight) - completed = [None] * len (template) + sorted = [None] * len (template) # todo.reverse() # try to randomize suitability # import random @@ -85,7 +98,7 @@ def bytemplate (template, src, key, weight = (1, )): closest = i diff = thisdiff # closest should always be non-None, now. - completed[targindex] = src.pop (closest) + sorted[targindex] = src.pop (closest) srcval.pop (closest) - return completed + return sorted -- 2.11.4.GIT