add generators, list and permutations libs.

laurentluce · laurentluce · commit a6d780cb1291 · 2010-12-01T13:00:39.000-08:00
diff --git a/generators.py b/generators.py
@@ -0,0 +1,15 @@
+def fib(n):
+  """
+  Generator for Fibonacci serie
+
+  Each call to fib() returns the next value in the serie
+  Example: for i in fib(5): print i
+  @param n fib range upper bound
+  """
+  a, b = 0, 1
+  i = 0
+  while i < n:
+    yield b
+    a, b = b, a+b
+    i += 1
+
diff --git a/list.py b/list.py
@@ -0,0 +1,25 @@
+def find_max_sub(l):
+  """
+  Find subset with higest sum
+
+  Example: [-2, 3, -4, 5, 1, -5] -> (3,4), 6
+  @param l list
+  @returns subset bounds and highest sum
+  """
+  # max sum
+  max = l[0]
+  # current sum
+  m = 0
+  # max sum subset bounds
+  bounds = (0, 0)
+  # current subset start
+  s = 0
+  for i in range(len(l)):
+    m += l[i]
+    if m > max:
+      max = m
+      bounds = (s, i)
+    elif m < 0:
+      m = 0
+      s = i+1
+  return bounds, max
diff --git a/permutations.py b/permutations.py
@@ -0,0 +1,18 @@
+def permutations(l):
+  """
+  Generator for list permutations
+  
+  Example: [1,2,3] = [1,2,3], [1,3,2], [2,1,3] ...
+
+  @param l list to generate permutations for
+  @result yield each permutation
+  """
+  print 'permutations: ',l
+  if len(l) <= 1:
+    yield l
+  else:
+    a = [l.pop(0)]
+    for p in permutations(l):
+      for i in range(len(p)+1):
+        yield p[:i] + a + p[i:]
+
