Les grands mombres en Python/Sage
In [1]:
factorial(100)
Out[1]:
In [ ]:
In [2]:
l = [2,5,3,4]
In [3]:
l
Out[3]:
In [4]:
l.append(5)
In [5]:
l
Out[5]:
Concatenation de deux listes. Ne change pas la liste parametre
In [6]:
l + [4,3]
Out[6]:
In [7]:
l
Out[7]:
In [8]:
7*[1,2]
Out[8]:
In [9]:
l
Out[9]:
Contanenation en place, ne retourne rien mais modifie la premiere liste
In [10]:
l.extend([8,4,345,12])
In [11]:
l
Out[11]:
Indexation des listes et fonction range
In [12]:
l[5]
Out[12]:
In [13]:
l[5:7]
Out[13]:
In [14]:
l[2:6]
Out[14]:
In [15]:
len(l)
Out[15]:
In [16]:
range(len(l))
Out[16]:
In [17]:
range(9)
Out[17]:
In [18]:
range(2,6)
Out[18]:
In [19]:
range(6,2)
Out[19]:
In [20]:
range(6,2,-1)
Out[20]:
In [21]:
l
Out[21]:
In [22]:
l[6:2:-1]
Out[22]:
In [23]:
l[6::-1]
Out[23]:
In [24]:
l[::-1]
Out[24]:
In [25]:
l
Out[25]:
Definition de listes en comprehension
In [26]:
[x*x for x in l if x % 2 == 0]
Out[26]:
Generation recursive de toutes les listes de n bits
In [27]:
def lbinseq(n):
if n == 0:
return [ [] ]
lrec = lbinseq(n-1)
return [ [0] + s for s in lrec ] + [ [1] + s for s in lrec ]
In [28]:
lbinseq(4)
Out[28]:
In [29]:
len(lbinseq(10))
Out[29]:
Version en utilisant la base 2
In [30]:
def binary(n):
l = [None]*2^n
for i in range(2^n):
l[i] = Integer(i).digits(2, padto=n)[::-1]
return l
In [31]:
binary(4)
Out[31]:
In [32]:
def unrank(n, i):
assert 0 <= i < 2^n
return i.digits(2, padto=n)[::-1]
In [33]:
unrank(10, 832)
Out[33]:
In [34]:
lbinseq(10)[832]
Out[34]:
In [35]:
unrank(40, 121923091283)
Out[35]:
Algorithme First Next
In [36]:
def first(n):
return n * [0]
In [37]:
first(4)
Out[37]:
In [38]:
def next(l):
l = l[:] # copie de l
i = len(l)-1
while i >= 0 and l[i] == 1:
l[i] = 0
i -= 1
if i >= 0:
l[i] = 1
return l
else:
raise StopIteration
In [39]:
next([1,0,1,1])
Out[39]:
In [40]:
next([1,1,1,1])
In [41]:
def random(n):
return [randrange(2) for _ in range(n)]
Iteration sur une liste
In [42]:
l = [1,1,2,4,2,5,3]
In [43]:
it = iter(l)
In [44]:
it.next()
Out[44]:
In [45]:
it.next(), it.next(), it.next()
Out[45]:
In [46]:
list(it)
Out[46]:
Iterateur pour les mots binaires en utilisant la base 2
In [47]:
class binaryIter(object):
def __init__(self, n):
self._n = n
self._2n = 2^n
self._i = 0
def __iter__(self):
return self
def next(self):
if self._i == self._2n:
raise StopIteration
res = Integer(self._i).digits(2, padto=self._n)[::-1]
self._i += 1
return res
In [48]:
it = iter(binaryIter(3))
In [49]:
it.next()
Out[49]:
In [50]:
it.next()
Out[50]:
In [51]:
list(it)
Out[51]:
Mots binaire -> Compositions
In [52]:
def bit2compo(l):
l = l+[1]
res = []
c = 0
for i in range(len(l)):
if l[i] == 0:
c += 1
else:
res.append(c+1)
c = 0
return res
In [53]:
bit2compo([0,1,0,0,1,1,0,1,0,0,1,0,1])
Out[53]:
In [54]:
[bit2compo(l) for l in lbinseq(3)]
Out[54]:
In [55]:
class BitString(object):
def __init__(self, n, k):
self._n = n
self._k = k
def list(self):
if self._k > self._n:
return []
if self._k == 0:
return [self._n*[0]]
return ([[0]+x for x in BitString(self._n-1, self._k).list()] +
[[1]+x for x in BitString(self._n-1, self._k-1).list()])
def first(self):
return (self._n - self._k)*[0] + self._k*[1]
def next(self, x):
c0 = 0
c1 = 0
i = len(x) - 1
while i >= 0 and x[i] == 0:
c0 += 1
i -= 1
while i >= 0 and x[i] == 1:
c1 += 1
i -= 1
if i < 0:
raise StopIteration
x = x[:]
x[i] = 1
x[i+1] = 0
for j in range(i+2, i+2+c0):
x[j] = 0
for j in range(i+2+c0, i+2+c0+c1-1):
x[j] = 1
return x
In [56]:
BitString(5,2).next([0,1,0,0,1])
Out[56]:
In [57]:
BitString(5,2).list()
Out[57]:
In [ ]: