← Back to branch summary

~dinko-metalac/calculus-app2/trunk

« back to all changes in this revision

Viewing changes to lib/py/sympy/combinatorics/prufer.py

  • Committer: dinko.metalac at gmail
  • Date: 2015-04-14 13:28:14 UTC
  • Revision ID: dinko.metalac@gmail.com-20150414132814-j25k3qd7sq3warup
new sympy

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/py/sympy/combinatorics/prufer.py
 
1
from __future__ import print_function, division
 
2
 
1
3
from sympy.core import Basic
2
 
from sympy.core.compatibility import iterable, as_int
 
4
from sympy.core.compatibility import iterable, as_int, xrange
3
5
from sympy.utilities.iterables import flatten
4
6
 
5
7
from collections import defaultdict
165
167
            # edge involving it.
166
168
            d[edge[0]] += 1
167
169
            d[edge[1]] += 1
168
 
        for i in range(n - 2):
 
170
        for i in xrange(n - 2):
169
171
            # find the smallest leaf
170
 
            for x in range(n):
 
172
            for x in xrange(n):
171
173
                if d[x] == 1:
172
174
                    break
173
175
            # find the node it was connected to
205
207
        References
206
208
        ==========
207
209
 
208
 
        - http://hamberg.no/erlend/2010/11/06/prufer-sequence/
 
210
        - http://hamberg.no/erlend/posts/2010-11-06-prufer-sequence-compact-tree-representation.html
209
211
 
210
212
        See Also
211
213
        ========
219
221
        for p in prufer:
220
222
            d[p] += 1
221
223
        for i in prufer:
222
 
            for j in range(n):
 
224
            for j in xrange(n):
223
225
            # find the smallest leaf (degree = 1)
224
226
                if d[j] == 1:
225
227
                    break
228
230
            d[i] -= 1
229
231
            d[j] -= 1
230
232
            tree.append(sorted([i, j]))
231
 
        last = [i for i in range(n) if d[i] == 1] or [0, 1]
 
233
        last = [i for i in xrange(n) if d[i] == 1] or [0, 1]
232
234
        tree.append(last)
233
235
 
234
236
        return tree
307
309
        """
308
310
        r = 0
309
311
        p = 1
310
 
        for i in range(self.nodes - 3, -1, -1):
 
312
        for i in xrange(self.nodes - 3, -1, -1):
311
313
            r += p*self.prufer_repr[i]
312
314
            p *= self.nodes
313
315
        return r
326
328
        """
327
329
        n, rank = as_int(n), as_int(rank)
328
330
        L = defaultdict(int)
329
 
        for i in range(n - 3, -1, -1):
 
331
        for i in xrange(n - 3, -1, -1):
330
332
            L[i] = rank % n
331
333
            rank = (rank - L[i])//n
332
 
        return Prufer([L[i] for i in range(len(L))])
 
334
        return Prufer([L[i] for i in xrange(len(L))])
333
335
 
334
336
    def __new__(cls, *args, **kw_args):
335
337
        """The constructor for the Prufer object.