Mini introduction: les listes en Python

Les grands mombres en Python/Sage


In [1]:
factorial(100)


Out[1]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

In [ ]:


In [2]:
l = [2,5,3,4]

In [3]:
l


Out[3]:
[2, 5, 3, 4]

In [4]:
l.append(5)

In [5]:
l


Out[5]:
[2, 5, 3, 4, 5]

Concatenation de deux listes. Ne change pas la liste parametre


In [6]:
l + [4,3]


Out[6]:
[2, 5, 3, 4, 5, 4, 3]

In [7]:
l


Out[7]:
[2, 5, 3, 4, 5]

In [8]:
7*[1,2]


Out[8]:
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]

In [9]:
l


Out[9]:
[2, 5, 3, 4, 5]

Contanenation en place, ne retourne rien mais modifie la premiere liste


In [10]:
l.extend([8,4,345,12])

In [11]:
l


Out[11]:
[2, 5, 3, 4, 5, 8, 4, 345, 12]

Indexation des listes et fonction range


In [12]:
l[5]


Out[12]:
8

In [13]:
l[5:7]


Out[13]:
[8, 4]

In [14]:
l[2:6]


Out[14]:
[3, 4, 5, 8]

In [15]:
len(l)


Out[15]:
9

In [16]:
range(len(l))


Out[16]:
[0, 1, 2, 3, 4, 5, 6, 7, 8]

In [17]:
range(9)


Out[17]:
[0, 1, 2, 3, 4, 5, 6, 7, 8]

In [18]:
range(2,6)


Out[18]:
[2, 3, 4, 5]

In [19]:
range(6,2)


Out[19]:
[]

In [20]:
range(6,2,-1)


Out[20]:
[6, 5, 4, 3]

In [21]:
l


Out[21]:
[2, 5, 3, 4, 5, 8, 4, 345, 12]

In [22]:
l[6:2:-1]


Out[22]:
[4, 8, 5, 4]

In [23]:
l[6::-1]


Out[23]:
[4, 8, 5, 4, 3, 5, 2]

In [24]:
l[::-1]


Out[24]:
[12, 345, 4, 8, 5, 4, 3, 5, 2]

In [25]:
l


Out[25]:
[2, 5, 3, 4, 5, 8, 4, 345, 12]

Definition de listes en comprehension


In [26]:
[x*x for x in l if x % 2 == 0]


Out[26]:
[4, 16, 64, 16, 144]

Premier exemple: Les listes de n bits

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]:
[[0, 0, 0, 0],
 [0, 0, 0, 1],
 [0, 0, 1, 0],
 [0, 0, 1, 1],
 [0, 1, 0, 0],
 [0, 1, 0, 1],
 [0, 1, 1, 0],
 [0, 1, 1, 1],
 [1, 0, 0, 0],
 [1, 0, 0, 1],
 [1, 0, 1, 0],
 [1, 0, 1, 1],
 [1, 1, 0, 0],
 [1, 1, 0, 1],
 [1, 1, 1, 0],
 [1, 1, 1, 1]]

In [29]:
len(lbinseq(10))


Out[29]:
1024

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]:
[[0, 0, 0, 0],
 [0, 0, 0, 1],
 [0, 0, 1, 0],
 [0, 0, 1, 1],
 [0, 1, 0, 0],
 [0, 1, 0, 1],
 [0, 1, 1, 0],
 [0, 1, 1, 1],
 [1, 0, 0, 0],
 [1, 0, 0, 1],
 [1, 0, 1, 0],
 [1, 0, 1, 1],
 [1, 1, 0, 0],
 [1, 1, 0, 1],
 [1, 1, 1, 0],
 [1, 1, 1, 1]]

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]:
[1, 1, 0, 1, 0, 0, 0, 0, 0, 0]

In [34]:
lbinseq(10)[832]


Out[34]:
[1, 1, 0, 1, 0, 0, 0, 0, 0, 0]

In [35]:
unrank(40, 121923091283)


Out[35]:
[0,
 0,
 0,
 1,
 1,
 1,
 0,
 0,
 0,
 1,
 1,
 0,
 0,
 0,
 1,
 1,
 0,
 0,
 1,
 0,
 1,
 1,
 1,
 0,
 1,
 0,
 1,
 1,
 1,
 0,
 1,
 1,
 0,
 1,
 0,
 1,
 0,
 0,
 1,
 1]

Algorithme First Next


In [36]:
def first(n):
    return n * [0]

In [37]:
first(4)


Out[37]:
[0, 0, 0, 0]

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]:
[1, 1, 0, 0]

In [40]:
next([1,1,1,1])


---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-40-80400549ca83> in <module>()
----> 1 next([Integer(1),Integer(1),Integer(1),Integer(1)])

<ipython-input-38-75f1134f0501> in next(l)
      9         return l
     10     else:
---> 11         raise StopIteration

StopIteration: 

In [41]:
def random(n):
    return [randrange(2) for _ in range(n)]

Iteration en Python

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]:
1

In [45]:
it.next(), it.next(), it.next()


Out[45]:
(1, 2, 4)

In [46]:
list(it)


Out[46]:
[2, 5, 3]

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]:
[0, 0, 0]

In [50]:
it.next()


Out[50]:
[0, 0, 1]

In [51]:
list(it)


Out[51]:
[[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Bijection : Exemple des compositions

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]:
[2, 3, 1, 2, 3, 2, 1]

In [54]:
[bit2compo(l) for l in lbinseq(3)]


Out[54]:
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

Une classe pour les objets modelisants l'ensemble des chaines de bits de longueur n avec k 1


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]:
[0, 1, 0, 1, 0]

In [57]:
BitString(5,2).list()


Out[57]:
[[0, 0, 0, 1, 1],
 [0, 0, 1, 0, 1],
 [0, 0, 1, 1, 0],
 [0, 1, 0, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 1, 1, 0, 0],
 [1, 0, 0, 0, 1],
 [1, 0, 0, 1, 0],
 [1, 0, 1, 0, 0],
 [1, 1, 0, 0, 0]]

In [ ]: