Partage
  • Partager sur Facebook
  • Partager sur Twitter

Exercice et algorithm

    20 juin 2021 à 22:38:32

    from itertools import product
    
    def f1(it, n):
        return list(map(''.join, product(it, repeat=n)))
    
    def f2(it, n):
        ls = ['']
        for _ in range(n):
            ls = [a + b for a in ls for b in it]
        return ls
    
    
    from string import ascii_lowercase
    from time import perf_counter
    
    args = (ascii_lowercase, 8)
    
    for funct in (f1, f2):
        time = perf_counter()
        _ = funct(*args)
        time = perf_counter() - time
        print(funct.__name__, time)
    • Partager sur Facebook
    • Partager sur Twitter
      21 juin 2021 à 3:28:24

      @LaPremière:
      J'ai testé ton code avec seulement 8 lettres. Sinon, je m'en prenais pour plus de 6 heures ...
      La première fonction est plus rapide.
      • Partager sur Facebook
      • Partager sur Twitter

      Le Tout est souvent plus grand que la somme de ses parties.

        21 juin 2021 à 17:56:36

        Bonjour, un autre exercice : faire un Triangle de Pascal 

        example:

        pascal(5)

        qui affiche :

               1
              1 1
             1 2 1
            1 3 3 1
           1 4 6 4 1

        2 NIVEAU: dire la ligne correspondante( qui est trés facile si on n' a réussi le premier niveau):

        pascal_index(6)


        example:

        1 5 10 10 5 1

        PS: pour ceux qui ne connaissent pas : https://fr.wikipedia.org/wiki/Triangle_de_Pascal

        On peut utiliser la récursivité

        et on n'essaye de ne pas faire ca en une ligne (COIN D' OEIL À JOSMILEY :p)

        Bonne chance à tous



        -
        Edité par Le programmeur solitaire 21 juin 2021 à 18:00:44

        • Partager sur Facebook
        • Partager sur Twitter

        le code FAIT le bonheur (pour moi en tous cas)

          21 juin 2021 à 18:50:37

          Voici ma version de base, je pense qu'on peut faire mieux (fais un copier-coller pour retrouver l'indentation)
          -
          def pascal(n):
              if n<=0: return [1]
              L=pascal(n-1)
              LL=[1]
              for i in range(1,n):
                  LL.append(L[i-1]+L[i])
              LL.append(1)
              return LL
          for i in range(6):
              print(pascal(i))
          • Partager sur Facebook
          • Partager sur Twitter

          Le Tout est souvent plus grand que la somme de ses parties.

            21 juin 2021 à 19:20:19

            pour le fun ... sans formatage du texte.

            foo = lambda n:(i and(c:=[1]+list(map(sum,zip(c,c[1:])))+[1])or(c:=[1])for i in range(n))
            
            for i in foo(10):
                print(*i)
            


            version développée ...

            def foo(n):
                yield (c:=[1])
                for i in range(1,n):
                    c = [1]+list(map(sum,zip(c,c[1:])))+[1]
                    yield c
            
            for i in foo(10):
                print(*i)



            -
            Edité par josmiley 21 juin 2021 à 19:24:34

            • Partager sur Facebook
            • Partager sur Twitter

            Python c'est bon, mangez-en. 

              21 juin 2021 à 19:27:34

              t@josmiley: tu triches ...
              Légère amélioration:
              Faudrait voir ce qu'on peut faire avec reduce()
              -
              def pascal(n):
                  if n<=0: return [1]
                  L=pascal(n-1)
                  return [1] + [L[i-1]+L[i] for i in range(1, n)] + [1]
              for i in range(6):
                  print(pascal(i))
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                21 juin 2021 à 19:38:16

                Ma participation

                def pascal_triangle(n):
                    for i in range(n):
                        pascal_line_(1,1,i,0)
                
                def pascal_line_(acc_num, acc_den, original_n, iterations):
                    if original_n == iterations:
                        print()
                    elif iterations == 0:
                        print(1, end=" ")
                        pascal_line_(acc_num, acc_den, original_n, iterations+1)
                    else:
                        acc_num = acc_num*(original_n-iterations)
                        acc_den = acc_den*(iterations)
                        print(int(acc_num/acc_den), end=" ")
                        pascal_line_(acc_num, acc_den, original_n, iterations+1)
                
                pascal_triangle(15)



                • Partager sur Facebook
                • Partager sur Twitter
                  21 juin 2021 à 20:47:27

                  import sys
                  
                  def pascal(limit):
                      num = 1
                      for i in range(limit):
                          s = ""
                          for j in range(i+1):
                              if j == 0 or i == j:
                                  num = 1
                              else:
                                  num = (num * (i-j+1)) // j
                              s += " " + str(num)
                          print(s.center(limit*4))
                  
                  pascal(15)
                                                1                             
                                               1 1                            
                                              1 2 1                           
                                             1 3 3 1                          
                                            1 4 6 4 1                         
                                          1 5 10 10 5 1                       
                                        1 6 15 20 15 6 1                      
                                       1 7 21 35 35 21 7 1                    
                                     1 8 28 56 70 56 28 8 1                   
                                   1 9 36 84 126 126 84 36 9 1                
                               1 10 45 120 210 252 210 120 45 10 1            
                             1 11 55 165 330 462 462 330 165 55 11 1          
                           1 12 66 220 495 792 924 792 495 220 66 12 1        
                       1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1    
                   1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 


                  • Partager sur Facebook
                  • Partager sur Twitter

                  Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
                  La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)

                    21 juin 2021 à 20:49:13

                    Je récidive:
                    -
                    def pascal(n):
                        if n<=0: return [1]
                        L=pascal(n-1)
                        return [i+j for i,j in zip([0]+L, L+[0])]
                    for i in range(6):
                        print(pascal(i))
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                      21 juin 2021 à 22:22:19

                      Le programmeur solitaire a écrit:

                      Bonjour, un autre exercice : faire un Triangle de Pascal 



                      La question est hyper méga classique :). Je ne vais pas me recopier donc voir :

                      Voici une solution qui n'a pas été proposée et qui ne marche que sous Python 3.9 :

                      # Python 3.9 uniquement
                      from math import comb 
                      
                      def pascal(n):
                          return [comb(n,k) for k in range(n+1)]
                      
                      print(*pascal(10))
                      
                      1 10 45 120 210 252 210 120 45 10 1

                      fred1599 a écrit:

                                                    1                             
                                                   1 1                            
                                                  1 2 1                           
                                                 1 3 3 1                          
                                                1 4 6 4 1                         
                                              1 5 10 10 5 1                       
                                            1 6 15 20 15 6 1                      
                                           1 7 21 35 35 21 7 1                    
                                         1 8 28 56 70 56 28 8 1                   
                                       1 9 36 84 126 126 84 36 9 1                
                                   1 10 45 120 210 252 210 120 45 10 1            
                                 1 11 55 165 330 462 462 330 165 55 11 1          
                               1 12 66 220 495 792 924 792 495 220 66 12 1        
                           1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1    
                       1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 




                      Joli !



                      • Partager sur Facebook
                      • Partager sur Twitter
                        22 juin 2021 à 1:51:06

                        Si je suppose qu'un des objectifs de l'exercice est de "dessiner" le triangle de Pascal de façon esthétique,
                        j'aurai besoin du nombre de chiffres du plus grand nombre.
                        Ce nombre se trouve au milieu de la liste correspondant à la plus grande puissance.
                        De plus, si je dois construire toutes les lignes, la méthode récursive m'impose de recalculer les sous-résultats.
                        J'ai décidé de procéder autrement.
                        -
                        power = 10   # Puissance maximum
                        ligne = [1]   # Première ligne.
                        triangle = [ligne]   # Triangle de Pascal (j'ai failli écrire Des Bermudes ...)
                        for _ in range(power):
                            ligne = [i+j for i, j in zip([0]+ligne, ligne+[0])]   # Pas forcément la plus efficace.
                            triangle.append(ligne)
                        width = len(str(triangle[-1][len(triangle[-1])//2]))   # Nombre de caractères par nombre.
                        spaces = ' '*width
                        fmt = lambda n, w: (' '*w+str(n))[-w:]
                        for p in range(power+1):
                            print(spaces*(power-p), end='')
                            print(*(fmt(number, width) for number in triangle[p]), sep=spaces)
                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          22 juin 2021 à 8:01:08

                          PierrotLeFou a écrit:

                          Si je suppose qu'un des objectifs de l'exercice est de "dessiner" le triangle de Pascal de façon esthétique,
                          j'aurai besoin du nombre de chiffres du plus grand nombre.
                          Ce nombre se trouve au milieu de la liste correspondant à la plus grande puissance.
                          De plus, si je dois construire toutes les lignes, la méthode récursive m'impose de recalculer les sous-résultats.
                          J'ai décidé de procéder autrement.
                          -
                          power = 10   # Puissance maximum
                          ligne = [1]   # Première ligne.
                          triangle = [ligne]   # Triangle de Pascal (j'ai failli écrire Des Bermudes ...)
                          for _ in range(power):
                              ligne = [i+j for i, j in zip([0]+ligne, ligne+[0])]   # Pas forcément la plus efficace.
                              triangle.append(ligne)
                          width = len(str(triangle[-1][len(triangle[-1])//2]))   # Nombre de caractères par nombre.
                          spaces = ' '*width
                          fmt = lambda n, w: (' '*w+str(n))[-w:]
                          for p in range(power+1):
                              print(spaces*(power-p), end='')
                              print(*(fmt(number, width) for number in triangle[p]), sep=spaces)

                          Le formatage est la seule partie de l'exercice qui ne soit pas évidente. Tu obtiens un très joli résultat, j'affiche ce que ça donne pour p=14 :

                                                                                                                   1
                                                                                                              1         1
                                                                                                         1         2         1
                                                                                                    1         3         3         1
                                                                                               1         4         6         4         1
                                                                                          1         5        10        10         5         1
                                                                                     1         6        15        20        15         6         1
                                                                                1         7        21        35        35        21         7         1
                                                                           1         8        28        56        70        56        28         8         1
                                                                      1         9        36        84       126       126        84        36         9         1
                                                                 1        10        45       120       210       252       210       120        45        10         1
                                                            1        11        55       165       330       462       462       330       165        55        11         1
                                                       1        12        66       220       495       792       924       792       495       220        66        12         1
                                                  1        13        78       286       715      1287      1716      1716      1287       715       286        78        13         1
                                             1        14        91       364      1001      2002      3003      3432      3003      2002      1001       364        91        14         1
                                        1        15       105       455      1365      3003      5005      6435      6435      5005      3003      1365       455       105        15         1
                                   1        16       120       560      1820      4368      8008     11440     12870     11440      8008      4368      1820       560       120        16         1
                              1        17       136       680      2380      6188     12376     19448     24310     24310     19448     12376      6188      2380       680       136        17         1


                          Je ne sais pas s'il est faisable de faire en sorte que chaque nombre soit exactement au milieu des deux nombres dont il est la somme et que l'écartement soit minimal. Dans ton code ci-dessus 19448 est plus proche (de 1 caractère) de 11440 que de 8008 et cela se produit à plusieurs endroits. 

                          • Partager sur Facebook
                          • Partager sur Twitter
                            22 juin 2021 à 15:17:53

                            Il y a deux problèmes de centrage.
                            D'abord, si le nombre le plus grand a un nombre impair de chiffres, je ne peux pas centrer les nombres ayant un nombre pair de chiffres.
                            On a le même problème si le plus grand nombre a un nombre pair de chiffres avec les nombres ayant un nombre impair de chiffres.
                            Je peux essayer de centrer un peu tout de même, Ce ne sera pas parfait.
                            J'ai revérifié sur ma console et les nombres sont bien à leur place mais pas centrés dans leur zone.

                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le Tout est souvent plus grand que la somme de ses parties.

                              23 juin 2021 à 15:34:03

                              tJ'ai réécrit ma fonction fmt() qi essaie de centrer autant que possible:
                              fmt=lambda n, w: (s:=str(n), l:=len(s), ' '*((w-l+1)//2)+s+' '*((w-l)//2))[-1]
                              • Partager sur Facebook
                              • Partager sur Twitter

                              Le Tout est souvent plus grand que la somme de ses parties.

                                23 juin 2021 à 17:29:46

                                PierrotLeFou a écrit:

                                tJ'ai réécrit ma fonction fmt() qi essaie de centrer autant que possible:
                                fmt=lambda n, w: (s:=str(n), l:=len(s), ' '*((w-l+1)//2)+s+' '*((w-l)//2))[-1]


                                OK, ça marche Pierrot !
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  26 juin 2021 à 10:29:47


                                  Toujours à propos de cette question.

                                  fred1599 a écrit:

                                  À mon sens, c'est typiquement dans ce type d'exercice que PyPy et Cython peuvent sortir leur épingle du jeu.

                                  Je pense pas qu'en pure python on puisse faire beaucoup mieux que le code que tu proposes.

                                  Pour PyPy, j'ai essayé, sur cet exemple l'exécution et l'occupation mémoire sont TRÈS mauvaises.

                                  Pour Cython, c'est une punition ! Typiquement, il va falloir travailler avec un gros tableau de caractères, et donc créer un tableau de pointeurs vers les lignes "virtuelles" car si on veut un code efficace, il faut faire des copies massives (l'algo s'y prête) via memcpy, autant dire que Cython ne va que compliquer les choses, autant le faire direct en C.

                                  Je précise l'algo  pour trouver par exemple tous les 81 mots de 4 lettres sur l'alphabet a, b, c :

                                  • On construit un tableau 4 x 81 de caractères 
                                  • On remplit la ligne 0 avec a, b et c.
                                  • On duplique sur la même ligne pour obtenir la suite de caractères abcabcabc
                                  • ligne 1 : on écrit à partir du début la suite de caractères aaabbbccc
                                  • On recommence : on duplique 3 fois le bloc 2x9 et on lui colle en dessous une séquence a...ab...c...c
                                  • etc
                                  • on transpose le tableau pour récupérer les lignes

                                  Donc on se dit qu'on peut largement vectoriser cela avec Numpy. Le problème est que Numpy n'est pas meilleur que python pour travailler sur des chaînes, donc on préfère travailler avec le code ascii des caractères (des uint8) puis reconvertir d'où le code :

                                  from string import ascii_lowercase
                                  import numpy as np
                                  
                                  from time import perf_counter
                                  
                                  
                                  def copy_block(L, alpha, nline, w, n):
                                      # le bloc à répéter
                                      M=L[:nline, :w]
                                      # la copie
                                      C=np.repeat(M,n, axis=0)
                                      # affectation
                                      L[:nline,:w*n]=C.reshape(nline,w*n)
                                      # rajout de ligne
                                      A=np.array([ord(c) for c in alpha])
                                      B=np.zeros(w, dtype=np.uint8).reshape(w,1)
                                      L[nline,:w*n]=(A+B).transpose().flatten()
                                  
                                  def product(alpha, p):
                                      n=len(alpha)
                                      L=np.zeros(shape=(p, n**p), dtype=np.uint8)
                                      L[0][:n]=[ord(c) for c in alpha]
                                      nline=1
                                      w=n
                                      for nline in range(1,p):
                                          copy_block(L, alpha, nline, w, n)
                                          w*=n
                                      L=np.array([chr(x) for x in range(128)])[L.transpose()]
                                      join="".join
                                      M=list(map(join, L))
                                      return M
                                  
                                  begin_perf = perf_counter()
                                  
                                  n=3
                                  p=4
                                  alpha=ascii_lowercase[:n]
                                  
                                  
                                  #  ---- Début de code à exécuter ----
                                  
                                  M=product(alpha, p)
                                  
                                  #  ---- Fin de code à exécuter ----
                                  
                                  delta = perf_counter() - begin_perf
                                  
                                  print(f"Temps d'exécution : {delta:.2f}s")
                                  M
                                  Temps d'exécution : 0.00s
                                  ['aaaa',
                                   'baaa',
                                   'caaa',
                                   'abaa',
                                   'bbaa',
                                   'cbaa',
                                   'acaa',
                                   'bcaa',
                                   'ccaa',
                                   'aaba',
                                   'baba',
                                   'caba',
                                   'abba',
                                   'bbba',
                                   'cbba',
                                   'acba',
                                   'bcba',
                                   'ccba',
                                   'aaca',
                                   'baca',
                                   'caca',
                                   'abca',
                                   'bbca',
                                   'cbca',
                                   'acca',
                                   'bcca',
                                   'ccca',
                                   'aaab',
                                   'baab',
                                   'caab',
                                   'abab',
                                   'bbab',
                                   'cbab',
                                   'acab',
                                   'bcab',
                                   'ccab',
                                   'aabb',
                                   'babb',
                                   'cabb',
                                   'abbb',
                                   'bbbb',
                                   'cbbb',
                                   'acbb',
                                   'bcbb',
                                   'ccbb',
                                   'aacb',
                                   'bacb',
                                   'cacb',
                                   'abcb',
                                   'bbcb',
                                   'cbcb',
                                   'accb',
                                   'bccb',
                                   'cccb',
                                   'aaac',
                                   'baac',
                                   'caac',
                                   'abac',
                                   'bbac',
                                   'cbac',
                                   'acac',
                                   'bcac',
                                   'ccac',
                                   'aabc',
                                   'babc',
                                   'cabc',
                                   'abbc',
                                   'bbbc',
                                   'cbbc',
                                   'acbc',
                                   'bcbc',
                                   'ccbc',
                                   'aacc',
                                   'bacc',
                                   'cacc',
                                   'abcc',
                                   'bbcc',
                                   'cbcc',
                                   'accc',
                                   'bccc',
                                   'cccc']

                                  Hélas, il y a un problème d'efficacité, qui vient de Python. Dans le code ci-dessus (ligne 28), L est un tableau Numpy de caractères dont les lignes sont exactement les caractères des chaînes que nous cherchons. L'obtention de L est assez efficace, pour p=8 et n= 9, ça s'obtient en  1,8s dont les 2/3 (quand même) à reconvertir les code ascii en caractères, à comparer aux 6,35s du code proposé plus haut. La partie TRÈS couteuse du code vient de la ligne 30 qui définit M et qui fusionne avec join les caractères de chaque ligne pour obtenir chaque mot : rien que pour n=8 et p=8, ça prend 35s et une conso mémoire qui croit doucement mais surement, inimaginable à faire pour n=9.



                                  -
                                  Edité par PascalOrtiz 26 juin 2021 à 10:38:46

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    27 juin 2021 à 8:19:24

                                    PascalOrtiz a écrit:

                                    Pour Cython, c'est une punition ! Typiquement, il va falloir travailler avec un gros tableau de caractères, et donc créer un tableau de pointeurs vers les lignes "virtuelles" car si on veut un code efficace, il faut faire des copies massives (l'algo s'y prête) via memcpy, autant dire que Cython ne va que compliquer les choses, autant le faire direct en C.

                                    Oui c'est bien pour ça que je ne l'ai pas écrit :p

                                    Je suis même pas sûr que ça soit si rapide, car si on souhaite y retrouver la forme de la réponse, soit une liste de chaînes de caractères, il faudra utiliser la méthode decode pour transformer de bytes en str sur l'ensemble des tableaux de caractères calculés et cette méthode est très lente, sans compter la création d'un nouvelle liste où on y ajoute les éléments résultants de decode (boucle supplémentaire).

                                    Bref effectivement, la seule solution est de faire du full cython, et du coup tu as raison, en fait du C pour l'ensemble de l'exercice.

                                    • Partager sur Facebook
                                    • Partager sur Twitter

                                    Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
                                    La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)

                                      27 juin 2021 à 18:49:20

                                      L'optimisation réside dans le choix de la structure retournée. Il n'est pas utile de générer et stocker toutes les combinaisons possibles. Une liste qui génère l’élément à la demande serai plus intéressante.

                                      from collections import abc
                                      
                                      
                                      class Combinations(abc.Sequence):
                                          
                                          def __init__(self, digits, width):
                                              self.digits = tuple(digits)
                                              self.base = len(self.digits)
                                              if self.base < 2:
                                                  raise ValueError
                                              if not isinstance(width, int):
                                                  raise TypeError
                                              if width < 1:
                                                  raise ValueError
                                              self.length = self.base ** width
                                              self.width = width
                                      
                                          def __len__(self):
                                              return self.length
                                      
                                          def __getitem__(self, index):
                                              if not isinstance(index, int):
                                                  raise TypeError
                                              if index >= self.length:
                                                  raise IndexError
                                              results, index = [], index % self.length
                                              for _ in range(self.width):
                                                  results.append(self.digits[index % self.base])
                                                  index //= self.base
                                              return results
                                      
                                      
                                      if __name__ == "__main__":
                                          from string import ascii_lowercase
                                      
                                          class Posi(Combinations):
                                              def __init__(self, width):        
                                                  super().__init__(ascii_lowercase, width)
                                              def __getitem__(self, index):
                                                  return ''.join(super().__getitem__(index))
                                      
                                          seq = Posi(52)
                                          print(seq[1_000_000_000], seq[-1_000_000_000], sep='\n')

                                      -
                                      Edité par .H.D.1. 27 juin 2021 à 18:52:18

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        27 juin 2021 à 20:32:18

                                        .H.D.1. a écrit:

                                        L'optimisation réside dans le choix de la structure retournée. Il n'est pas utile de générer et stocker toutes les combinaisons possibles. Une liste qui génère l’élément à la demande serai plus intéressante.


                                        Merci de cette contribution et du code intéressant. Ici, la question était de retourner une liste. Le code que tu nous proposes est basé (c'est le cas de le dire) sur le fait qu'un élément de rang r  donné du produit cartésien est parfaitement connu par l'écriture de r dans la base de numération définie par les chiffres donnés.

                                        Au passage, je suis étonné de deux choses :

                                        • habituellement, la génération se fait dans l'ordre lexicographique croissant
                                        • il n'est pas possible de choisir ses chiffres.

                                        Je modifie légèrement :

                                        ctions import abc
                                         
                                         
                                        class Combinations(abc.Sequence):
                                            def __init__(self, digits, width):
                                                self.digits = tuple(digits)
                                                self.base = len(self.digits)
                                                if self.base < 2:
                                                    raise ValueError
                                                if not isinstance(width, int):
                                                    raise TypeError
                                                if width < 1:
                                                    raise ValueError
                                                self.length = self.base ** width
                                                self.width = width
                                         
                                            def __len__(self):
                                                return self.length
                                         
                                            def __getitem__(self, index):
                                                if not isinstance(index, int):
                                                    raise TypeError
                                                if index >= self.length:
                                                    raise IndexError
                                                results, index = [], index % self.length
                                                for _ in range(self.width):
                                                    results.append(self.digits[index % self.base])
                                                    index //= self.base
                                                return results
                                        
                                        
                                        from string import ascii_lowercase, digits
                                        
                                        class Posi(Combinations):
                                            def __init__(self, width, alpha):       
                                                super().__init__(alpha, width)
                                            def __getitem__(self, index):
                                                return ''.join(super().__getitem__(index))
                                        
                                        seq = Posi(2, digits)
                                        for i in range(42):
                                            print(seq[i])
                                        00
                                        10
                                        20
                                        30
                                        40
                                        50
                                        60
                                        70
                                        80
                                        90
                                        01
                                        11
                                        21
                                        31
                                        41
                                        51
                                        61
                                        71
                                        81
                                        91
                                        02
                                        12
                                        22
                                        32
                                        42
                                        52
                                        62
                                        72
                                        82
                                        92
                                        03
                                        13
                                        23
                                        33
                                        43
                                        53
                                        63
                                        73
                                        83
                                        93
                                        04
                                        14

                                        [Curieusement, les slices ne semblent pas fonctionner, seq[:42] lève une exception].

                                        L'intérêt de ton code est de fournir à la volée n'importe quel élément d'«indice» donné (sans itérer donc). La contrepartie est que l'itération est extrêmement coûteuse même pour des valeurs raisonnables (une liste de quelques millions), c'est normal, on fait une conversion dans la base à chaque étape. Exemple :

                                        from collections import abc
                                         
                                         
                                        class Combinations(abc.Sequence):
                                             
                                            def __init__(self, digits, width):
                                                self.digits = tuple(digits)
                                                self.base = len(self.digits)
                                                if self.base < 2:
                                                    raise ValueError
                                                if not isinstance(width, int):
                                                    raise TypeError
                                                if width < 1:
                                                    raise ValueError
                                                self.length = self.base ** width
                                                self.width = width
                                         
                                            def __len__(self):
                                                return self.length
                                         
                                            def __getitem__(self, index):
                                                if not isinstance(index, int):
                                                    raise TypeError
                                                if index >= self.length:
                                                    raise IndexError
                                                results, index = [], index % self.length
                                                for _ in range(self.width):
                                                    results.append(self.digits[index % self.base])
                                                    index //= self.base
                                                return results
                                         
                                         
                                        
                                        from string import ascii_lowercase
                                        from time import perf_counter
                                        
                                        class Posi(Combinations):
                                            def __init__(self, width):       
                                                super().__init__(ALPHA, width)
                                            def __getitem__(self, index):
                                                return ''.join(super().__getitem__(index))
                                        
                                        n=8
                                        p=8
                                        ALPHA=ascii_lowercase[:n]
                                        seq=Posi(p)
                                        
                                        
                                        begin_perf = perf_counter()
                                        
                                        L=list(seq)
                                        
                                        delta = perf_counter() - begin_perf
                                        
                                        print(len(seq), n**p)
                                        
                                        print(f"Temps d'exécution : {delta:.2f}s")
                                        
                                        
                                        16777216 16777216
                                        Temps d'exécution : 34.79s
                                        

                                        Bien sûr, j'ai bien compris que tu ne souhaitais pas itérer mais parfois c'est utile si le nombre d'items reste raisonnable. En revanche, pas de problème de mémoire (même si elle croit doucement pendant toute l'exécution). 

                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          27 juin 2021 à 22:09:00

                                          Pour itérer les combinaisons il faudrait utiliser itertools.product (sans passer par une liste ou autre conteneur).

                                          Pour conserver les combinaisons générées il faudrait éviter de créer des millions d'objets distincts. Chaque objet référencé dans une liste pèse plusieurs octets en plus du poids déjà très élevé des objets eux-mêmes (à partir de 25 octets par objets vide ou numérique).
                                          Par exemple dans une chaîne de caractères, les perfs en temps et en espace sont déjà très bonnes :

                                          s = ''.join(map(''.join, product(digits, repeat=width)))


                                          Sinon je propose une refonte de la classe Combinations pour le support du slicing :

                                          #!/usr/bin/env python3
                                          
                                          from collections import abc
                                          from string import digits
                                          
                                          
                                          class Combinations(abc.Sequence):
                                              
                                              def __init__(self, width, digits=digits):
                                                  self.digits = tuple(digits)
                                                  self.base = len(self.digits)
                                                  if self.base < 2:
                                                      raise ValueError
                                                  if not isinstance(width, int):
                                                      raise TypeError
                                                  if width < 1:
                                                      raise ValueError
                                                  self._data = range(self.base ** width)
                                                  self.width = width
                                          
                                              def __len__(self):
                                                  return len(self._data)
                                          
                                              def __getitem__(self, index):
                                                  if isinstance(index, slice):
                                                      subseq = self.__class__(self.width, self.digits)
                                                      subseq._data = self._data.__getitem__(index)
                                                      return subseq
                                                  item, index = [], self._data[index]
                                                  for _ in range(self.width):
                                                      item.append(self.digits[index % self.base])
                                                      index //= self.base
                                                  return item[::-1]
                                          
                                          
                                          if __name__ == "__main__":
                                              from string import hexdigits
                                          
                                              class Posi(Combinations):
                                                  def __getitem__(self, index):
                                                      if isinstance(index, slice):
                                                          return super().__getitem__(index)
                                                      return ''.join(super().__getitem__(index))
                                          
                                              seq = Posi(16, hexdigits)
                                              sub = seq[::-1]
                                              print(seq[25464985213], seq[-465482215655], sub[465482215654], sep='\n')

                                          -
                                          Edité par .H.D.1. 27 juin 2021 à 22:09:53

                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            28 juin 2021 à 1:04:50

                                            .H.D.1. a écrit:

                                            Pour itérer les combinaisons il faudrait utiliser itertools.product (sans passer par une liste ou autre conteneur).

                                            Oui mais nous avons vu dans un message précédent que les performances mémoire d'itertools étaient, en l'espèce, très mauvaises par exemple pour n=9 et p=8 et je n'en vois pas la raison puisque product est un itérateur, il ne stocke rien.

                                            .H.D.1. a écrit:

                                            Sinon je propose une refonte de la classe Combinations pour le support du slicing :


                                            Merci pour le code. Je crois que j'ai une erreur pour le slice :

                                            #!/usr/bin/env python3
                                             
                                            from collections import abc
                                            from string import digits
                                             
                                             
                                            class Combinations(abc.Sequence):
                                                 
                                                def __init__(self, width, digits=digits):
                                                    self.digits = tuple(digits)
                                                    self.base = len(self.digits)
                                                    if self.base < 2:
                                                        raise ValueError
                                                    if not isinstance(width, int):
                                                        raise TypeError
                                                    if width < 1:
                                                        raise ValueError
                                                    self._data = range(self.base ** width)
                                                    self.width = width
                                             
                                                def __len__(self):
                                                    return len(self._data)
                                             
                                                def __getitem__(self, index):
                                                    if isinstance(index, slice):
                                                        subseq = self.__class__(self.width, self.digits)
                                                        subseq._data = self._data.__getitem__(index)
                                                        return subseq
                                                    item, index = [], self._data[index]
                                                    for _ in range(self.width):
                                                        item.append(self.digits[index % self.base])
                                                        index //= self.base
                                                    return item[::-1]
                                             
                                             
                                            if __name__ == "__main__":
                                                from string import hexdigits, digits
                                             
                                                class Posi(Combinations):
                                                    def __getitem__(self, index):
                                                        if isinstance(index, slice):
                                                            return super().__getitem__(index)
                                                        return ''.join(super().__getitem__(index))
                                             
                                                seq = Posi(5, digits)
                                                print(seq[:42])
                                            <__main__.Posi object at 0x7f73a688d668>
                                            

                                            J'ai essayé de faire un itérateur sans utiliser itertools en simulant l'ordre lexicographique :

                                            from string import digits
                                            from time import perf_counter
                                              
                                                
                                            class Product:
                                                def __init__(self, digits, width):
                                                    self.width=width
                                                    self.digits=digits
                                                    self.L=[0]*width
                                                    self.L[-1]=-1
                                                    self.base=len(digits)
                                                    
                                                def __iter__(self):
                                                    return self
                                            
                                                def __next__(self):
                                                    L=self.L
                                                    base=self.base
                                                    d=self.digits
                                                    k=-1
                                                    try:
                                                        while L[k]+1==base:
                                                            L[k]=0
                                                            k-=1
                                                        L[k]+=1
                                                        return "".join(d[k] for k in L)
                                                    except IndexError:
                                                        raise StopIteration
                                            
                                            
                                            n=8
                                            p=8
                                            
                                            begin_perf = perf_counter()
                                            
                                            L=list(Product(digits[:n], p))
                                            
                                            delta = perf_counter() - begin_perf
                                            
                                            print(f"Temps d'exécution : {delta:.2f}s")
                                            
                                            print(len(L), n**p)
                                            Temps d'exécution : 18.10s
                                            16777216 16777216
                                            

                                            Bien sûr, c'est beaucoup plus lent qu'itertools, la boucle while ralentit tout mais c'est quand même plus rapide que de convertir dans la base. La conso mémoire est très importante (1 Go), à peu près comme ton code et pourtant rien n'est stocké (de visible).






                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              28 juin 2021 à 2:29:38

                                              PascalOrtiz a écrit:

                                              .H.D.1. a écrit:

                                              Pour itérer les combinaisons il faudrait utiliser itertools.product (sans passer par une liste ou autre conteneur).

                                              Oui mais nous avons vu dans un message précédent que les performances mémoire d'itertools étaient, en l'espèce, très mauvaises par exemple pour n=9 et p=8 et je n'en vois pas la raison puisque product est un itérateur, il ne stocke rien.

                                              Ce n'est pas le fait de product mais de la liste. Chaque chaîne de la liste résultante pèse plusieurs dizaines d'octets, raison pour laquelle, si besoin de stocker les combinaisons, il est préférable de les concaténer dans une seule chaîne.

                                              .H.D.1. a écrit:

                                              Sinon je propose une refonte de la classe Combinations pour le support du slicing :


                                              Merci pour le code. Je crois que j'ai une erreur pour le slice :

                                              # ...
                                                  seq = Posi(5, digits)
                                                  print(seq[:42])
                                              <__main__.Posi object at 0x7f73a688d668>
                                              

                                              Le résultat d'un slice est un nouvel objet du type dont il est le slice. C'est le comportement normal d'un slicing.

                                              Bien sûr, c'est beaucoup plus lent qu'itertools, la boucle while ralentit tout mais c'est quand même plus rapide que de convertir dans la base. La conso mémoire est très importante (1 Go), à peu près comme ton code et pourtant rien n'est stocké (de visible).

                                              Quel est le code qui occupe 1Go et dans quelle condition ?

                                               
                                              #!/usr/bin/env python3
                                              
                                              from itertools import product
                                              from memory_profiler import profile
                                              
                                              
                                              @profile
                                              def funct(s, n):
                                                  return ''.join(map(''.join, product(s, repeat=n)))
                                              
                                              
                                              s = funct("0123456789", 7)
                                              print(s[:7], s[7:14], '...', s[-14:-7], s[-7:])
                                              
                                              (profiler) ~$ time mprof run untitled.py 
                                              mprof: Sampling memory every 0.1s
                                              running new process
                                              running as a Python program...
                                              Filename: untitled.py
                                              
                                              Line #    Mem usage    Increment  Occurences   Line Contents
                                              ============================================================
                                                   7     17.3 MiB     17.3 MiB           1   @profile
                                                   8                                         def funct(s, n):
                                                   9     84.5 MiB     67.2 MiB           1       return ''.join(map(''.join, product(s, repeat=n)))
                                              
                                              
                                              0000000 0000001 ... 9999998 9999999
                                              
                                              real	0m1,341s
                                              user	0m1,095s
                                              sys	0m0,157s
                                              (profiler) ~$ cat mprofile_xxx.dat 
                                              CMDLINE /home/hd1/.venvs/profiler/bin/python3 untitled.py
                                              MEM 1.398438 1624842158.8203
                                              MEM 47.968750 1624842158.9206
                                              MEM 120.906250 1624842159.0209
                                              MEM 194.046875 1624842159.1211
                                              MEM 268.796875 1624842159.2214
                                              MEM 341.894531 1624842159.3217
                                              MEM 416.261719 1624842159.4220
                                              MEM 489.347656 1624842159.5223
                                              MEM 565.070312 1624842159.6226
                                              MEM 637.058594 1624842159.7229
                                              MEM 631.699219 1624842159.8233
                                              MEM 84.476562 1624842159.9235
                                              

                                              Soit une chaîne de 67 Mo contenant 70 000 000 caractères, soit 10 000 000 combinaisons de 7 chiffres, et un pique à 637 Mo qui s'explique par l'accumulation des chaînes intermédiaires que le GC n'a pas eu besoin de nettoyer avant la fin de la concaténation.

                                              -
                                              Edité par .H.D.1. 28 juin 2021 à 3:44:13

                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                28 juin 2021 à 10:05:22

                                                .H.D.1. a écrit:

                                                PascalOrtiz a écrit:

                                                .H.D.1. a écrit:

                                                Pour itérer les combinaisons il faudrait utiliser itertools.product (sans passer par une liste ou autre conteneur).

                                                Oui mais nous avons vu dans un message précédent que les performances mémoire d'itertools étaient, en l'espèce, très mauvaises par exemple pour n=9 et p=8 et je n'en vois pas la raison puisque product est un itérateur, il ne stocke rien.

                                                Ce n'est pas le fait de product mais de la liste. Chaque chaîne de la liste résultante pèse plusieurs dizaines d'octets, raison pour laquelle, si besoin de stocker les combinaisons, il est préférable de les concaténer dans une seule chaîne.


                                                Ah oui ! c'est vrai que j'ai mesuré la construction de la liste. Si on teste seulement l'itération sur les 43 millions de chaînes :

                                                from time import perf_counter
                                                from itertools import product
                                                from string import ascii_lowercase
                                                 
                                                p=8
                                                n=9
                                                alpha=ascii_lowercase[:n]
                                                 
                                                begin_perf = perf_counter()
                                                 
                                                cpt=0
                                                for x in product(alpha, repeat=p):
                                                    "".join(x)
                                                    cpt+=1
                                                
                                                delta = perf_counter() - begin_perf
                                                print(cpt, n**p)
                                                print(f"Temps d'exécution : {delta:.2f}s")
                                                43046721 43046721                                                                                                                                                          
                                                Temps d'exécution : 9.65s
                                                

                                                l'empreinte mémoire est effectivement très faible, je lis un maximum de 3,9 Mio.

                                                .H.D.1. a écrit:


                                                Merci pour le code. Je crois que j'ai une erreur pour le slice :

                                                # ...
                                                    seq = Posi(5, digits)
                                                    print(seq[:42])
                                                <__main__.Posi object at 0x7f73a688d668>
                                                

                                                Le résultat d'un slice est un nouvel objet du type dont il est le slice. C'est le comportement normal d'un slicing.


                                                Oui, d'accord, il aurait fallu que j'écrive

                                                for s in seq[:42]:
                                                        print(s)

                                                .H.D.1. a écrit:

                                                Quel est le code qui occupe 1Go et dans quelle condition ?

                                                Même erreur que plus haut, j'ai mesuré list(it) au lieu de seulement itérer sur it, désolé.

                                                Donc effectivement, l'itération avec itertools est efficace en mémoire, je vais le mentionner dans le message initial !



                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  29 juin 2021 à 15:39:10

                                                  Si vous cherchez des exercices du même genre (dont le triangle de Pascal), il y a aussi Hackinscience : https://www.hackinscience.org/exercises/

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    30 juin 2021 à 2:26:27

                                                    @entwanne:
                                                    As-tu quelque chose à suggérer? Le début m'a semblé banal.
                                                    I.E. Le nombre de secondes dans une année.
                                                    Le gros du problème est la durée de l'année ... 365? 365.25? 365j 5h 48m 21s ...
                                                    Avec ça je vais passer à la postérité ...
                                                    secondes = lambda s: s
                                                    minutes = lambda m: m*secondes(60)
                                                    heures = lambda h: h*minutes(60)
                                                    jours = lambda j: j*heures(24)
                                                    annee = lambda a: jours(365) + heures(5) + minutes(48) + secondes(21)
                                                    print(secondes(13))
                                                    print(minutes(20))
                                                    print(jours(1))
                                                    print(annee(1))
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter

                                                    Le Tout est souvent plus grand que la somme de ses parties.

                                                      30 juin 2021 à 7:55:06

                                                      Les exercices sont classés en différentes catégories, le comptage des secondes figure dans la catégorie « Les bases de Python ». Mais sinon les plus difficiles sont généralement ceux qui ont été résolus le moins de fois.

                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        2 juillet 2021 à 19:07:41

                                                        ma solution pour le triangle de pascal qui est d'ailleurs horrible comparé a vos solutions:

                                                        pascal = lambda n, l=[1]: [[1]] + [(l:=([1] + [l[n-1] + l[n]  for  n in range(len(l)) if  (len(l) != 1 or len(l) != 2) and not n == 0] + [1])) for i in range(n-1)]
                                                        
                                                        print(pascal(10))
                                                        

                                                        qui affiche:

                                                        [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

                                                        et désolé sans formatage de text: et oui je vous avais prévenu que mon code était horrible:honte:


                                                        • Partager sur Facebook
                                                        • Partager sur Twitter

                                                        le code FAIT le bonheur (pour moi en tous cas)

                                                          26 novembre 2021 à 8:20:05

                                                          bonjour les zeros, nouveau exercices : les Noeuds.

                                                          le but de cet exercice et de manipuler les noeuds et les fonctions d'affichages

                                                          voici ce code avec la classe Noeud(à vous de coder la classe Noeud):

                                                          n1 = Noeud("A")
                                                          n2 = Noeud("B")
                                                          n3 = Noeud("C")
                                                          n4 = Noeud("D")
                                                          n5 = Noeud("E")
                                                          n6 = Noeud("F")
                                                          n7 = Noeud("G")
                                                          n8 = Noeud("H")
                                                          n9 = Noeud("I")
                                                          n10 = Noeud("J")
                                                          n11 = Noeud("M")
                                                          n12 = Noeud("L")
                                                          n13 = Noeud("K")
                                                          n14 = Noeud("W")
                                                          n15 = Noeud("X")
                                                          n16 = Noeud("P")
                                                          n17 = Noeud("Z")
                                                          n18 = Noeud("Y")
                                                          
                                                          n6.add_noeud(n13)
                                                          n7.add_noeud(n14)
                                                          n7.add_noeud(n15)
                                                          n8.add_noeud(n16)
                                                          n2.add_noeud(n6)
                                                          n2.add_noeud(n7)
                                                          n3.add_noeud(n8)
                                                          n3.add_noeud(n9)
                                                          n4.add_noeud(n10)
                                                          n5.add_noeud(n12)
                                                          n5.add_noeud(n11)
                                                          n1.add_noeud(n2)
                                                          n1.add_noeud(n3)
                                                          n1.add_noeud(n4)
                                                          n1.add_noeud(n5)
                                                          n10.add_noeud(n17)
                                                          n17.add_noeud(n18)
                                                          n1.print_tree()

                                                          le resultat:

                                                          A
                                                          |
                                                          B-----C---D-E
                                                          |     |   | |
                                                          F-G   H-I J L-M
                                                          | |   |   |
                                                          K W-X P   Z
                                                                    |
                                                                    Y


                                                          le but est d'afficher l'arborescence d'un seul noeud avec ses enfants dans une fonction de la classe Noeud qui s'appellera print_tree comme dans l'example

                                                          -
                                                          Edité par Le programmeur solitaire 26 novembre 2021 à 8:23:14

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter

                                                          le code FAIT le bonheur (pour moi en tous cas)

                                                            26 novembre 2021 à 15:31:28

                                                            -

                                                            -
                                                            Edité par PierrotLeFou 26 novembre 2021 à 15:55:12

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter

                                                            Le Tout est souvent plus grand que la somme de ses parties.

                                                              26 novembre 2021 à 17:30:54

                                                              je ne comprend pas ?

                                                              PierrotLeFou a écrit:

                                                              -

                                                              -
                                                              Edité par PierrotLeFou il y a environ 1 heure



                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              le code FAIT le bonheur (pour moi en tous cas)

                                                              Exercice et algorithm

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                              • Editeur
                                                              • Markdown