-
Comb sort 11
A Python implementation of the "Comb sort 11" algorithm. See http://en.wikipedia.org/wiki/Comb_sort
1 def combsort11(seq, cmp=None, key=None):
2 """Sort `seq` *in-place* with the CombSort11 algorithm.
3 Optional arguments `cmp` and `key` have same meaning as in the
4 Python `sorted` built-in function.
5
6 Examples::
7
8 >>> seq = [8,4,5,0,2,3,1,6,7]
9 >>> combsort11(seq)
10 >>> seq
11 [0, 1, 2, 3, 4, 5, 6, 7, 8]
12
13 >>> seq = range(9)
14 >>> combsort11(seq, cmp=-cmp)
15 >>> seq
16 [8, 7, 6, 5, 4, 3, 2, 1, 0]
17
18 >>> seq = [(1,0), (2,3), (1,3), (1,-1)]
19 >>> combsort11(seq, key=lambda x: 10*x[0] + x[1])
20 >>> seq
21 [(1, -1), (1, 0), (1, 3), (2, 3)]
22
23 See http://en.wikipedia.org/wiki/Comb_sort for an explanation and
24 the original pseudocode.
25 """
26
27 if cmp is None:
28 cmp = __builtins__.cmp
29 if key is None:
30 key = lambda x: x
31
32 gap = len(seq) # initialize gap size
33 swap_occurred = False
34 while (gap > 1) or swap_occurred:
35 # update the gap value for a next comb
36 if gap > 1:
37 gap = int(gap / 1.247330950103979)
38 # adjust gap size for final steps of the sequence;
39 # see http://en.wikipedia.org/wiki/Comb_sort#Combsort11
40 if gap in (9, 10):
41 gap = 11
42
43 # a single "comb" over the input list
44 swap_occurred = False
45 for i in xrange(len(seq) - gap):
46 j = i + gap
47 if cmp(key(seq[i]), key(seq[j])) > 0:
48 # swap seq[i] and seq[i+gap]
49 seq[i], seq[j] = seq[j], seq[i]
50 swap_occurred = True -
Generate random password
A fully password generator.
1 <?php
2
3 /**
4 * Generate random password
5 *
6 * @param integer $length Length of the generated password
7 * @param boolean $allow_uppercase
8 * @param boolean $allow_lowercase
9 * @param boolean $allow_numbers
10 * @param boolean $allow_special
11 * @param boolean $fix_similar If true, check if string contains mistakeable chars, add if accepted
12 * @param string $valid_charset
13 * @return string
14 */
15 function rpassword($length = 8, $allow_uppercase = 1, $allow_lowercase = 1, $allow_numbers = 1, $allow_special = 0, $fix_similar = 0, $valid_charset = "") {
16 // Create a list of usable chars based upon the parameters
17 if (!$valid_charset) {
18 if ($allow_uppercase) $valid_charset .= 'ABCDEFGHIJKLMNOPQRSTUVXYZ';
19 if ($allow_lowercase) $valid_charset .= 'abcdefghijklmnopqrstuvxyz';
20 if ($allow_numbers) $valid_charset .= '0123456789';
21 if ($allow_special) $valid_charset .= '!#$%&()*+-./;<=>@\_';
22 }
23 // Find the charset length
24 $charset_length = strlen($valid_charset);
25 // If no chars is allowed, return false
26 if ($charset_length == 0) return false;
27 // Initialize the password and loop till we have all
28 $password = "";
29 while(strlen($password) < $length) {
30 // Pull out a random char
31 $char = $valid_charset[mt_rand(0, ($charset_length-1))];
32
33 if (($fix_similar && !strpos('O01lI5S', $char)) || !$fix_similar) $password .= $char;
34 }
35
36 return $password;
37 } -
Group items from iterable into chunks of specified size.
Only tested with Python 2.5, but should work with 2.3+
1 class chunks(object):
2 """Lump items from iterable into chunks of specified size.
3
4 Instanciate the iterator passing a sequence of chunk sizes in
5 argument 1 and an iterable to consume in argument 2::
6
7 >>> for c in chunks([1,1,1], xrange(3)): print c
8 [0]
9 [1]
10 [2]
11
12 The list of chunk sizes may be any kind of sequence, for instance
13 a tuple or even a (possibly infinite) iterable::
14
15 >>> list(chunks((1,2,3), range(6)))
16 [[0], [1, 2], [3, 4, 5]]
17
18 The total size of the chunks may be less than the size of the
19 iterator: remaining items in the iterator are not consumed::
20
21 >>> for c in chunks([1,2], range(6)): print c
22 [0]
23 [1, 2]
24
25 As a special case, if a chunk has size 0, then an empty list is
26 returned in its place and no item from iterable is consumed::
27
28 >>> for c in chunks([2,0,2], range(4)): print c
29 [0, 1]
30 []
31 [2, 3]
32
33 """
34 def __init__(self, sizes, iterable):
35 """Constructor, taking sequence of chunk sizes and iterable to
36 consume."""
37 self.current_chunk = -1
38 self.sizes = sizes
39 self.iterable = iter(iterable)
40 def __iter__(self):
41 return self
42 def next(self):
43 """Return next chunk."""
44 self.current_chunk += 1
45 if self.current_chunk >= len(self.sizes):
46 raise StopIteration
47 return [ self.iterable.next()
48 for x in xrange(self.sizes[self.current_chunk]) ] -
Alter items in a sequence according to a translation table
This is the analogue of Python `str.translate` or `unicode.translate` for general iterables (lists, tuples, etc.) Tested with Python 2.5
1 class itranslate:
2 """Return items from a sequence, substituting them as specified.
3
4 First c'tor argument `subst` is a dictionary, specifying
5 substitutions to be applied. If an item matches a key of the
6 `subst` dictionary, the associated dictionary value is returned
7 instead; unless the value is `None`, in which case the item is
8 skipped altogether.
9
10 *Note:* you should use an appropriate `dict`-subclass if you want
11 to translate items which are not immutable.
12
13 Examples::
14 >>> list(itranslate({0:None, 3:2}, [2,1,0,0,1,3]))
15 [2, 1, 1, 2]
16 """
17 def __init__(self, subst, iterable):
18 self.mappings = subst
19 self.iterable = iter(iterable)
20 def __iter__(self):
21 return self
22 def next(self):
23 while True:
24 next = self.iterable.next()
25 if not self.mappings.has_key(next):
26 return next
27 translated = self.mappings[next]
28 if translated is None:
29 # skip this item
30 continue
31 return translated -
Generate all partitions of an integer
Iterative algorithms to generate all partitions of a given integer. Only tested with Python 2.5
1 import itertools
2
3 class FixedLengthPartitionIterator:
4 """Iterate over partitions of integer `N` into *exactly* `K`
5 positive integers.
6
7 Each returned partition is a list of positive integers in
8 descending order, such that their sum is `N`.
9
10 Arguments `min_` and `max_` bound the values in each partition.
11
12 Examples::
13 >>> list(FixedLengthPartitionIterator(3,1))
14 [(3,)]
15 >>> list(FixedLengthPartitionIterator(3,2))
16 [(2, 1)]
17 >>> list(FixedLengthPartitionIterator(3,3))
18 [(1, 1, 1)]
19 >>> list(FixedLengthPartitionIterator(6,2))
20 [(5, 1), (4, 2), (3, 3)]
21 >>> list(FixedLengthPartitionIterator(8,3))
22 [(6, 1, 1), (5, 2, 1), (4, 3, 1), (4, 2, 2), (3, 3, 2)]
23 >>> list(FixedLengthPartitionIterator(8,4,2))
24 [(2, 2, 2, 2)]
25 >>> list(FixedLengthPartitionIterator(8,3,2))
26 [(4, 2, 2), (3, 3, 2)]
27 >>> list(FixedLengthPartitionIterator(8,3,2,3))
28 [(3, 3, 2)]
29 """
30 def __init__(self, N, K, min_=1, max_=None):
31 # `max_` really defaults to N
32 if max_ is None:
33 max_ = N
34
35 # rule out trivial cases
36 if (K*min_ > N) or (K*max_ < N):
37 self.done = True
38 return
39
40 self._N = N #: integer to be partitioned
41 self._K = K #: maximum number of nonzero parts
42 self._k = 0 #: current number of nonzero parts
43 self._min = min_ #: minimum value of each part
44 self._max = max_ #: maximum value of each part
45 self._p = [0] * K #: current partition
46 self.done = False #: when `True`, enumeration is over
47
48 def __iter__(self):
49 return self
50
51 def next(self):
52 if self.done:
53 raise StopIteration
54 if self._N == self._K * self._min:
55 self.done = True
56 return tuple([self._min]*self._K)
57 else:
58 while self._k <= self._K:
59 i = self._k - 1
60 while i > 0:
61 if (self._p[i]+1 <= self._p[i-1]-1) \
62 and (self._p[i-1]-1 >= self._min) \
63 and (self._p[i]+1 <= self._max):
64 self._p[i-1] -= 1
65 self._p[i] += 1
66 return tuple(self._p)
67 else:
68 i -= 1
69 # only change the first `k` parts
70 self._k += 1
71 head = (self._N - self._k - self._min*self._K + self._min + 1)
72 if (head < self._min+1) or (head > self._max) \
73 or (self._k > self._K):
74 continue
75 # advance to next partition:
76 # [N-2*(k-1)-(K-k), 2, ..., 2, (k-1 times) 1, ..., 1 (K-k times)]
77 self._p = [head] \
78 + ([self._min + 1] * (self._k - 1)) \
79 + ([self._min] * (self._K - self._k))
80 return tuple(self._p)
81 raise StopIteration
82
83
84 def PartitionIterator(N, K, min_=1, max_=None):
85 """Iterate over partitions of integer `N` into *at most* `K`
86 positive integers.
87
88 Each returned partition is a list of positive integers in
89 descending order, such that their sum is `N`.
90
91 Optional arguments `min_` and `max_` bound the values in each
92 partition.
93
94 Examples::
95 >>> list(PartitionIterator(2,1))
96 [(2,)]
97 >>> list(PartitionIterator(3,3))
98 [(3,), (2, 1), (1, 1, 1)]
99 >>> list(PartitionIterator(8,3,2))
100 [(8,), (6, 2), (5, 3), (4, 4), (4, 2, 2), (3, 3, 2)]
101 >>> list(PartitionIterator(8,3,2,3))
102 [(3, 3, 2)]
103 """
104 return itertools.chain(*[FixedLengthPartitionIterator(N,k,min_,max_)
105 for k in xrange(1,K+1)]) -
Cache any function (with its arguments)
original snippet from http://www.djangosnippets.org/snippets/109/
1 import cPickle as pickle
2 import md5
3
4 def cache_function(length):
5 """
6 A variant of the snippet posted by Jeff Wheeler at
7 http://www.djangosnippets.org/snippets/109/
8
9 Caches a function, using the function and its arguments as the key, and the return
10 value as the value saved. It passes all arguments on to the function, as
11 it should.
12
13 The decorator itself takes a length argument, which is the number of
14 seconds the cache will keep the result around.
15
16 It will put in a MethodNotFinishedError in the cache while the function is
17 processing. This should not matter in most cases, but if the app is using
18 threads, you won't be able to get the previous value, and will need to
19 wait until the function finishes. If this is not desired behavior, you can
20 remove the first two lines after the ``else``.
21 """
22 def decorator(func):
23 def inner_func(*args, **kwargs):
24 from django.core.cache import cache
25
26 raw = [func.__name__, func.__module__, args, kwargs]
27 pickled = pickle.dumps(raw, protocol=pickle.HIGHEST_PROTOCOL)
28 key = md5.new(pickled).hexdigest()
29 value = cache.get(key)
30 if cache.has_key(key):
31 return value
32 else:
33 # This will set a temporary value while ``func`` is being
34 # processed. When using threads, this is vital, as otherwise
35 # the function can be called several times before it finishes
36 # and is put into the cache.
37 class MethodNotFinishedError(Exception): pass
38 cache.set(key, MethodNotFinishedError(
39 'The function %s has not finished processing yet. This \
40 value will be replaced when it finishes.' % (func.__name__)
41 ), length)
42 result = func(*args, **kwargs)
43 cache.set(key, result, length)
44 return result
45 return inner_func
46 return decorator -
Convert CamelCase string to lowercase with specified separator.
This is Emacs LISP code. Only tested on GNU Emacs 22.1, but should work on almost any Emacs version.
1 (defun un-camelcase-string (s &optional sep start)
2 "Convert CamelCase string S to lower case with word separator SEP.
3 Default for SEP is a hyphen \"-\".
4
5 If third argument START is non-nil, convert words after that
6 index in STRING."
7 (let ((case-fold-search nil))
8 (while (string-match "[A-Z]" s (or start 1))
9 (setq s (replace-match (concat (or sep "-")
10 (downcase (match-string 0 s)))
11 t nil s)))
12 (downcase s)))
13
14 (defun un-camelcase-string-recursively (s &optional sep start)
15 "Convert CamelCase string S to lower case with word separator SEP.
16 Default for SEP is a hyphen '-'.
17
18 If third argument START is non-nil, convert words after that
19 index in STRING.
20
21 This is the same as `uncamelcase-string', but using a tail-recursive algorithm."
22 (let ((case-fold-search nil))
23 (if (not (string-match "[A-Z]" s (or start 1)))
24 (downcase s)
25 ;; substitute one match, then recurse
26 (un-camelcase-string-recursively (replace-match (concat (or sep "-")
27 (downcase (match-string 0 s)))
28 t nil s)
29 (or sep "-")
30 (match-end 0))))) -
A function to enumerate the items of a set product.
A function to enumerate the items of a set product. A recursive version is also provided for completeness, although it is much slower.
1 """A function to enumerate the items of a set product.
2 """
3 __docformat__ = 'reStructuredText'
4
5
6 def enumerate_set_product(*args):
7 """Iterate over all elements in the cartesian product of its arguments.
8 Each argument to this variadic function *must* be a sequence.
9
10 Examples::
11 >>> list(enumerate_set_product())
12 [[]]
13 >>> list(enumerate_set_product([1]))
14 [[1]]
15 >>> list(enumerate_set_product([1],[1]))
16 [[1, 1]]
17 >>> list(enumerate_set_product([1,2],[1]))
18 [[1, 1], [2, 1]]
19 >>> list(enumerate_set_product([1,2],[1,2]))
20 [[1, 1], [2, 1], [1, 2], [2, 2]]
21 """
22
23 # `assert` guard against invocation with wrong arguments.
24 def __all_items_are_sequences(s):
25 from operator import and_, isSequenceType
26 return reduce(and_,
27 [ isSequenceType(item) for item in s],
28 True)
29 assert __all_items_are_sequences(args), \
30 "All arguments to `enumerate_set_products` must be sequences."
31
32 if len(args) == 0:
33 yield []
34 else:
35 L = len(args)
36 M = [ len(s)-1 for s in args ]
37 m = [0] * L
38 i = 0
39 while i < L:
40 # return element corresponding to current multi-index
41 yield [ s[m[i]] for (i,s) in enumerate(args) ]
42 # advance multi-index
43 i = 0
44 while (i < L):
45 if m[i] == M[i]:
46 m[i] = 0
47 i += 1
48 else:
49 m[i] += 1
50 break
51
52
53 def recursively_enumerate_set_product(*args):
54 """Iterate over all elements in the cartesian product of its arguments.
55 Each argument to this variadic function *must* be a sequence.
56
57 You would probably prefer `enumerate_set_product`, which is faster.
58
59 Examples::
60 >>> list(recursively_enumerate_set_product())
61 [[]]
62 >>> list(recursively_enumerate_set_product([1]))
63 [[1]]
64 >>> list(recursively_enumerate_set_product([1],[1]))
65 [[1, 1]]
66 >>> list(recursively_enumerate_set_product([1,2],[1]))
67 [[1, 1], [2, 1]]
68 >>> list(recursively_enumerate_set_product([1,2],[1,2]))
69 [[1, 1], [2, 1], [1, 2], [2, 2]]
70 """
71
72 # `assert` guard against invocation with wrong arguments.
73 def __all_items_are_sequences(s):
74 from operator import and_, isSequenceType
75 return reduce(and_,
76 [ isSequenceType(item) for item in s],
77 True)
78 assert __all_items_are_sequences(args), \
79 "All arguments to `enumerate_set_products` must be sequences."
80
81 if len(args) == 0:
82 yield []
83 else:
84 for i in args[-1]:
85 for js in recursively_enumerate_set_product(*args[:-1]):
86 yield js+[i]
87
88
89 ## main: run tests
90
91 if "__main__" == __name__:
92 import doctest
93 doctest.testmod(optionflags=doctest.NORMALIZE_WHITESPACE) -
Various algorithms for computing the sign of a permutation.
This is a Python version of the code (and associated commentary) from http://perplexus.info/show.php?pid=4895&op=sol You can run the source file through PyLit (http://pylit.berlios.de/) to get a nicely-formatted reStructuredText file.
1 #! /usr/bin/env python
2 #
3 """Various algorithms for computing the sign of a permutation.
4
5 Ported from http://perplexus.info/show.php?pid=4895&op=sol
6 """
7 __docformat__ = 'reStructuredText'
8
9
10 ## perm_sign by John Burkardt is an example that can be found online
11 ## (see it among the collection at
12 ## http://orion.math.iastate.edu/burkardt/f_src/subset/subset.f90 or
13 ## see http://www.scs.fsu.edu/~burkardt/math2071/perm_sign.m). A
14 ## similar method, that, however, avoids explicit searching, is
15 ## illustrated by the following function::
16
17 def jbsign(p):
18 """Compute sign of permutation `p` by counting the number of
19 interchanges required to change the given permutation into the
20 identity one.
21
22 Examples::
23 >>> jbsign([0,1,2])
24 1
25 >>> jbsign([0,2,1])
26 -1
27 """
28 n = len(p)
29 s = +1
30 # get elements back in their home positions
31 for j in xrange(0,n):
32 q=p[j]
33 if q !=j:
34 p[j],p[q] = p[q],q # interchange p[j] and p[p[j]]
35 s = -s # and account for the interchange
36 # note that q is now in its home position
37 # whether or not an interchange was required
38 return s
39
40
41 ## A somewhat more sophisticated method follows the orbits of elements
42 ## as they are permuted through cycles::
43
44 def sign_by_orbits(p):
45 """Compute sign of permutation `p` by following orbit cycles.
46
47 Examples::
48 >>> sign_by_orbits([0,1,2])
49 1
50 >>> sign_by_orbits([0,2,1])
51 -1
52 """
53 n = len(p)
54 s = +1
55 # follow orbit cycles and tote up signs
56 for j in xrange(0,n):
57 if (p[j] >= 0):
58 # new cycle, follow it, marking each place as "visited"
59 q = j
60 t = +1
61 while (q >= 0):
62 r = p[q]
63 if (r >= 0):
64 p[q] = -1
65 t = -t
66 q = r
67 # factor in contribution of each cycle
68 s *= t
69 return s
70
71
72 ## Lang's Algebra, First Ed. 1965, p. 53, gives an equivalent
73 ## definition of the sign as simply `(-1)^m` where m=n-number of
74 ## orbits. Thus the above can be modified to just count the number of
75 ## orbits and do a little arithmetic at the end, as the following
76 ## function illustrates::
77
78 def sign_lang_formula(p):
79 """Compute sign of permutation `p` as `(-1)^{length of permutation
80 - number of orbits}`.
81
82 Examples::
83 >>> sign_lang_formula([0,1,2])
84 1
85 >>> sign_lang_formula([0,2,1])
86 -1
87 """
88 n = len(p)
89 c = 0
90 # count the orbit cycles
91 for j in xrange(0,n):
92 if (p[j] >= 0):
93 # new cycle, follow it, marking each place
94 q = j
95 while (q >= 0):
96 r = p[q]
97 if (r >= 0):
98 p[q] = -1
99 q = r
100 # increment cycle count
101 c += 1
102 if (n-c) % 2 == 0:
103 return +1
104 else:
105 return -1
106
107
108 ## Another method counts inversions and leads to the following short
109 ## program::
110
111 def sign_counting_inversions(p):
112 """Compute sign of permutation `p` by counting the number of
113 interchanges required to change the given permutation into the
114 identity one.
115
116 Examples::
117 >>> sign_counting_inversions([0,1,2])
118 1
119 >>> sign_counting_inversions([0,2,1])
120 -1
121 """
122 n = len(p)
123 v = 0
124 # count inversions
125 for i in xrange(1,n):
126 for j in xrange(i+1, n):
127 if (p[i] > p[j]):
128 v += 1
129 if (v % 2 == 0):
130 return +1
131 else:
132 return -1
133
134
135 ## And one more: Those with a sufficient background in algebra will
136 ## realize that a simple algorithm exists based on the Laplace
137 ## expansion of the determinant of a permutation matrix. However,
138 ## while rather similar to the algorithm above that counts inversions,
139 ## it turned out to be a bit more complicated to program::
140
141 def lpsign(p):
142 """Compute sign of permutation `p` via Laplace expansion of the
143 determinant of the permutation matrix.
144
145 Examples::
146 >>> lpsign([0,1,2])
147 1
148 >>> lpsign([0,2,1])
149 -1
150 """
151 # Laplace expansion of determinant of permutation
152 # matrix with a 1 in in row p[j] of column j
153 n = len(p)
154 s = 1
155 for j in xrange(1, n):
156 q=p[j]
157 # apply checkerboard sign
158 if (q % 2 == 0):
159 s = -s
160 for k in xrange(j+1, n):
161 r = p[k]
162 # adjust numbers of remaining rows beyond row p[j]
163 # to account for having deleted row p[j]
164 if (r > q):
165 p[k] = r-1
166 return s
167
168
169 def sign_recursive(p):
170 """Recursively compute the sign of permutation `p`.
171
172 A permutation is represented as a linear list: `p` maps
173 `i` to `p[i]`.
174
175 Examples:
176 >>> sign_recursive([0,1,2])
177 1
178 >>> sign_recursive([0,2,1])
179 -1
180 """
181 n = len(p)
182 if 1 >= n:
183 return 1
184 # find highest-numbered element
185 k = p.index(n-1)
186 # remove highest-numbered element for recursion
187 del p[k]
188 # recursively compute
189 if 0 == ((n+k) % 2):
190 s = -1
191 else:
192 s = 1
193 return s * sign_recursive(p)
194
195
196 ## So, based on simplicity, counting inversions appears to have the
197 ## edge over all the other algorithms discussed above. However, based
198 ## on speed, efficiently returning elements to their homes, and
199 ## counting orbits both seem to be quite fast.
200 ##
201 ## Indeed, running 100000 iterations of each function to compute the
202 ## sign of a 5-element permutation, gives::
203 ##
204 ## | $ python2.4 profile.py ./permsign.py
205 ## | ncalls tottime percall cumtime percall function
206 ## | [...]
207 ## | 100002 1.950 0.000 2.480 0.000 jbsign
208 ## | 100002 2.550 0.000 3.140 0.000 sign_counting_inversions
209 ## | 100002 2.810 0.000 3.350 0.000 sign_lang_formula
210 ## | 100002 2.820 0.000 3.510 0.000 sign_by_orbits
211 ## | 100002 3.470 0.000 4.190 0.000 lpsign
212 ## | 100002 11.450 0.000 16.890 0.000 sign_recursive
213 ## | [...]
214 ##
215
216
217
218 ## main: run tests
219
220 if "__main__" == __name__:
221 import doctest
222 doctest.testmod(optionflags=doctest.NORMALIZE_WHITESPACE)
Pages : 1
