nombres dont les chiffres sont tous différents [PYTHON] - Page 2
Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 31 à 59 sur 59

nombres dont les chiffres sont tous différents [PYTHON]



  1. #31
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]


    ------

    Une méthode simple en python3 :

    Code:
    from itertools import combinations, permutations
    
    figures = range(10)
    count = 0
    
    for n in range(1, 6):
        for c in combinations(figures, n):
            for x in permutations(c):
                if(x[0] != 0):
                    count += 1
    #                for y in x:
    #                    print(y, end="")
    #                print("")
    
    print("count=", count)
    Le code commenté permet de les afficher aussi. Sans l'affichage, cela tourne en 12 ms sur un Xeon E5 3.5 Ghz.

    -----

  2. #32
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Et pour rigoler en ligne de commande :

    Code:
    scala -e 'var count = 0; val l = for(i <- 0 to 9) yield i; for(n <- 1 to 5) { l.combinations(n).map(_.permutations).foreach(x => { x.foreach( y => { if(y.head !=0) count += 1 } )} ) }; println(s"count=$count") '
    C'est le même code que Python au dessus. Cela tourne moins vite malgré l'avantage théorique de Scala mais l'implémentation est inefficiente.

    Formatté proprement, cela donne :

    Code:
    object Unique extends App {
      var count = 0;
      val l = for(i <- 0 to 9) yield i;
      for(n <- 1 to 5)
      {
        l.combinations(n).map(_.permutations).foreach { x =>
          x.foreach {
            y => if(y.head !=0) count += 1
          }
        }
      }
      println(s"count=$count")
    }

  3. #33
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Petite variante de mon code précédent en utilisant des entiers au lieu de chaines de caractères

    0.12ms en mono-coeur sur i7-920@4ghz !!!

    Code:
    unit Unit1;
    
    interface
    
    uses
      Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,
      System.Classes, Vcl.Graphics,
      Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls,
      System.Diagnostics;
    
    const
      NbDeChiffreMax = 5;
    
    type
      TChiffres = Array [0 .. 9] of Integer;
      Tdisponibilite = array [-1 .. 9] of boolean;
    
      TFormMain = class(TForm)
        ButtonCalcule: TButton;
        Memo1: TMemo;
        Panel1: TPanel;
        procedure ButtonCalculeClick(Sender: TObject);
      private
        { Déclarations privées }
        Chiffres: TChiffres;
        Liste: Array [0 .. 50000] of Integer;
        Indice: Integer;
        procedure InitialiseChiffres; inline;
        procedure InitialiseDisponibilite(var Disponibilite: Tdisponibilite); inline;
        Procedure AjouteChiffre(Nombre: Integer; Disponibilite: Tdisponibilite;
          DernierChiffre: Integer; Exposant: Integer);
      public
        { Déclarations publiques }
      end;
    
    var
      FormMain: TFormMain;
    
    implementation
    
    uses Math;
    
    {$R *.dfm}
    
    procedure TFormMain.AjouteChiffre(Nombre: Integer;
      Disponibilite: Tdisponibilite; DernierChiffre: Integer; Exposant: Integer);
    var
      i: Integer;
      NombreCourant: Integer;
    begin
      Disponibilite[DernierChiffre] := False;
      for i := 0 to 9 do
        // Cas particulier du premier Chiffre qui ne doit pas être égal à 0
        if not((DernierChiffre = -1) and (i = 0)) and Disponibilite[i] then
        begin
          NombreCourant := Nombre + Chiffres[i] * Exposant;
          if Exposant <> 1 then
            AjouteChiffre(NombreCourant, Disponibilite, i, Exposant div 10)
          else
          begin
            Liste[Indice] := NombreCourant;
            inc(Indice);
          end;
        end;
    end;
    
    procedure TFormMain.ButtonCalculeClick(Sender: TObject);
    var
      Nombre: Integer;
      Disponibilite: Tdisponibilite;
      Stopwatch: TStopwatch;
      i, repet: Integer;
      Exp: Integer;
    begin
      Stopwatch := TStopwatch.StartNew;
      Indice := 0;
      InitialiseChiffres;
    
      // On démarre à 1 car les nombres de zéro chiffre n'existent pas
      for i := 1 to NbDeChiffreMax do
      begin
        if i = 1 then
          Exp := 1
        else
          Exp := Exp * 10;
        Nombre := 0;
        InitialiseDisponibilite(Disponibilite);
        AjouteChiffre(Nombre, Disponibilite, -1, Exp);
      end;
      ShowMessage(FloatToStr(Stopwatch.ElapsedTicks / 10000));
      Memo1.Lines.BeginUpdate;
      for i := 0 to Indice - 1 do
      begin
        Memo1.Lines.add(IntToStr(Liste[i]));
      end;
      Memo1.Lines.EndUpdate;
    end;
    
    procedure TFormMain.InitialiseChiffres;
    var
      i: Integer;
    begin
      for i := 0 to 9 do
        Chiffres[i] := i;
    end;
    
    procedure TFormMain.InitialiseDisponibilite(var Disponibilite: Tdisponibilite);
    var
      i: Integer;
    begin
      for i := 0 to 9 do
        Disponibilite[i] := True;
    end;
    
    end.

  4. #34
    ansset
    Animateur Mathématiques

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    bjr,
    j'ignorai qu'il fallait écrire un programme pour ça, parce que le dénombrement est facile.
    en comptant les nb à 1 chiffre, à 2 chiffres, etc.
    1 chiffre : 9 ( tous sauf 0 )
    2 chiffres : 9*9=81 ( pas de 0 en premier et 10-1 solutions pour le deuxième ) , etc...
    3 chiffres :9*9*8=648
    4 chiffres : 9*9*8*7=4536
    5 chiffres : 9*9*8*7*6=27216
    total : 32490
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  5. #35
    ansset
    Animateur Mathématiques

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    désolé, je n'avais pas vu le "[PYTHON]" dans le titre.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  6. #36
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par ansset Voir le message
    -
    j'ignorai qu'il fallait écrire un programme pour ça, parce que le dénombrement est facile.
    Les programmes écrits les génèrent, grosse différence.
    Après, je reste perplexe devant leur complexité inutile.

  7. #37
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par pm42 Voir le message
    Les programmes écrits les génèrent, grosse différence.
    Après, je reste perplexe devant leur complexité inutile.
    La performance n'est pas forcément inutile, bien sûr, dans ce cas là, c'était un exercice de style pour moi.
    Mais dans mon boulot, c'est une nécessité.

    J'ai encore complexifiée ma fonction récursive pour atteindre 0.106ms

    Code:
    procedure TFormMain.AjouteChiffre(Nombre: Integer;
      Disponibilite: Tdisponibilite; DernierChiffre: Integer; Exposant: Integer);
    var
      i: Integer;
      Depart: Integer;
    begin
      Disponibilite[DernierChiffre] := False;
      if DernierChiffre = -1 then
        Depart := 1
      else
        Depart := 0;
      if Exposant = 1 then
      begin
        for i := Depart to 9 do
          if Disponibilite[i] then
          begin
            Liste[Indice] := Nombre + Chiffres[i] * Exposant;
            inc(Indice);
          end
      end
      else
      begin
        for i := Depart to 9 do
          if Disponibilite[i] then
            AjouteChiffre(Nombre + Chiffres[i] * Exposant, Disponibilite, i, Exposant div 10)
      end
    end;

  8. #38
    mp3dux

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Garion Voir le message
    Petite variante de mon code précédent en utilisant des entiers au lieu de chaines de caractères

    0.12ms en mono-coeur sur i7-920@4ghz !!!
    Tu es sûr du calcul ? Ça parait faible, toute fois je connais pas delphi...

    Citation Envoyé par pm42 Voir le message
    Les programmes écrits les génèrent, grosse différence.
    Après, je reste perplexe devant leur complexité inutile.
    L'algo des rotations d'emplacements est très intéressante comme tu l'as montré dans ton code.

    En parlant de complexité on peut voir deux choses, disons que utiliser une fonction qui fait trois lignes peut paraître simple, mais derrière si cette fonction est composée de 30 lignes de codes chacune
    la comparaison est faussée, par contre la complexité de l'algo oui, et on peut la voir tout suite.

    En restant dans la même lignée du sujet complexité ton programme tourne aussi bien bien sans la boucle de "combinaison" , et même légèrement plus vite
    Code:
     for c in combinations(figures, n):
    Y'a t-il une raison particulière de l'ajouter ?
    Dernière modification par mp3dux ; 20/12/2017 à 15h13.

  9. #39
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par mp3dux Voir le message
    Tu es sûr du calcul ? Ça parait faible, toute fois je connais pas delphi...
    Oui, oui, 0.106ms de moyenne en ayant répété le calcul 1000 fois pour faire la moyenne.
    Delphi, c'est du code compilé comme du C++ avec le même niveau de performance.

  10. #40
    mp3dux

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par ansset Voir le message
    désolé, je n'avais pas vu le "[PYTHON]" dans le titre.


    Le code de pm42 en PYTHON en retirant l'utilisation de "combinations"
    Code:
    from itertools import  permutations
    list1=[]
    for n in range(1, 6):
        for c in permutations(range(10), n):        
             if(c[0] != 0):          
              list1.append(c)
    Si nous faisions tout ce que nous sommes capables de faire, nous en serions abasourdis. T.E

  11. #41
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par mp3dux Voir le message
    Y'a t-il une raison particulière de l'ajouter ?
    5h du math et un de mes 1ers programmes en Python...
    Sinon, bien vu de ta part.

  12. #42
    JPL
    Responsable des forums

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Cela me rappelle le sketch de Fernand Raynaud : Ici on vend de belles oranges pas chère.

    https://www.youtube.com/watch?v=nKrsqvVK5Ak
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  13. #43
    mp3dux

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Garion Voir le message
    Oui, oui, 0.106ms de moyenne en ayant répété le calcul 1000 fois pour faire la moyenne.
    Delphi, c'est du code compilé comme du C++ avec le même niveau de performance.
    Ok

    Essaie aussi entre 1 et 10 milliards...
    3.42s en python
    Code:
    from itertools import  permutations
    list1=[]
    for n in range(1, 11):
        for c in permutations(range(10), n):        
             if(c[0] != 0):          
              list1.append(c)
    Si nous faisions tout ce que nous sommes capables de faire, nous en serions abasourdis. T.E

  14. #44
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par mp3dux Voir le message
    Essaie aussi entre 1 et 10 milliards...
    3.42s en python
    Une technique marrante mais longue consiste à faire du "loop unrolling" (https://en.wikipedia.org/wiki/Loop_unrolling) ce qui est normalement au niveau du compilateur.
    Dans ce cas, on est en dessous de la seconde en Scala et je pense qu'on irait plus vite en C encore mais j'ai la flemme.

    Code:
    object UniqueFast extends App {
    
      val start = System.nanoTime()
      var count=0
      count += loop1(x1 => 1)
      count += loop1(loop2(_, (x1, x2) => 1))
      count += loop1(loop2(_, loop3(_, _, (x1, x2, x3) => 1)))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, (x1, x2, x3, x4) => 1))))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, loop5(_, _, _, _,  (x1, x2, x3, x4, x5) => 1)))))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, loop5(_, _, _, _,  loop6(_, _, _, _, _,  (x1, x2, x3, x4, x5, x6) => 1))))))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, loop5(_, _, _, _,  loop6(_, _, _, _, _,  (loop7(_, _, _, _, _, _,  (x1, x2, x3, x4, x5, x6, x7) => 1))))))))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, loop5(_, _, _, _,  loop6(_, _, _, _, _,  (loop7(_, _, _, _, _, _,  loop8(_, _, _, _, _, _, _,  (x1, x2, x3, x4, x5, x6, x7, x8) => 1)))))))))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, loop5(_, _, _, _,  loop6(_, _, _, _, _,  (loop7(_, _, _, _, _, _,  loop8(_, _, _, _, _, _, _,  loop9(_, _, _, _, _, _, _, _,  (x1, x2, x3, x4, x5, x6, x7, x8, x9) => 1))))))))))
      count += loop1(loop2(_, loop3(_, _, loop4(_, _, _, loop5(_, _, _, _,  loop6(_, _, _, _, _,  (loop7(_, _, _, _, _, _,  loop8(_, _, _, _, _, _, _,  loop9(_, _, _, _, _, _, _, _,  loop10(_, _, _, _, _, _, _, _, _)))))))))))
      val time = (System.nanoTime()-start)/1000000.0
      println(count)
      println(s"time=$time")
    
      def loop1(next: (Int) => Int): Int = {
        var i=1
        var count = 0
        while(i<10) {
          count += next(i)
          i+=1
        }
        count
      }
    
      def loop2(p1: Int, next: (Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1) count += next(p1, i)
          i+=1
        }
        count
      }
    
      def loop3(p1: Int, p2: Int, next: (Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2) count += next(p1, p2, i)
          i+=1
        }
        count
      }
    
      def loop4(p1: Int, p2: Int, p3: Int, next: (Int, Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3) count += next(p1, p2, p3, i)
          i+=1
        }
        count
      }
    
      def loop5(p1: Int, p2: Int, p3: Int, p4: Int, next: (Int, Int, Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3 && i!=p4) count += next(p1, p2, p3, p4, i)
          i+=1
        }
        count
      }
    
      def loop6(p1: Int, p2: Int, p3: Int, p4: Int, p5: Int, next: (Int, Int, Int, Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3 && i!=p4 && i!=p5) count += next(p1, p2, p3, p4, p5, i)
          i+=1
        }
        count
      }
    
      def loop7(p1: Int, p2: Int, p3: Int, p4: Int, p5: Int, p6: Int, next: (Int, Int, Int, Int, Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3 && i!=p4 && i!=p5 && i!=p6) count += next(p1, p2, p3, p4, p5, p6, i)
          i+=1
        }
        count
      }
    
      def loop8(p1: Int, p2: Int, p3: Int, p4: Int, p5: Int, p6: Int, p7: Int, next: (Int, Int, Int, Int, Int, Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3 && i!=p4 && i!=p5 && i!=p6 && i!=p7) count += next(p1, p2, p3, p4, p5, p6, p7, i)
          i+=1
        }
        count
      }
    
      def loop9(p1: Int, p2: Int, p3: Int, p4: Int, p5: Int, p6: Int, p7: Int, p8: Int, next: (Int, Int, Int, Int, Int, Int, Int, Int, Int) => Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3 && i!=p4 && i!=p5 && i!=p6 && i!=p7 && i!=p8) count += next(p1, p2, p3, p4, p5, p6, p7, p8, i)
          i+=1
        }
        count
      }
    
      def loop10(p1: Int, p2: Int, p3: Int, p4: Int, p5: Int, p6: Int, p7: Int, p8: Int, p9: Int): Int = {
        var i=0
        var count = 0
        while(i<10) {
          if(i!=p1 && i!=p2 && i!=p3 && i!=p4 && i!=p5 && i!=p6 && i!=p7 && i!=p8 && i!=p9) count += 1
          i+=1
        }
        count
      }
    }

  15. #45
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    On doit pouvoir faire plus concis, générique et rapide avec des bitfields pour indiquer les valeurs déjà prises ceci dit. Si j'ai 5 min, j'essaie.

  16. #46
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Oui, vu que je n'arrive pas à dormir, ça marche bien avec des bitfields. 1ms pour les 1 à 100 000 et 150 ms pour les 10 milliards :

    Code:
    object UniqueBitfield extends App {
    
      val start = System.nanoTime()
      var count=0
      var i = 1
      while(i<11) {
        count += loop1(i)
        i += 1
      }
      val time = (System.nanoTime()-start)/1000000.0
      println(count)
      println(s"time=$time")
    
    
      def loop1(n: Int): Int = {
        var i = 1
        var count = 0
        while(i<10) {
          count += loop0(n-1, 1 << i)
          i += 1
        }
        count
      }
    
      def loop0(n: Int, used: Int): Int = {
        if(n == 0 ) 1
        else {
          var i = 0
          var current = 1
          var count = 0
          while (i < 10) {
            if((used & current) == 0) count += loop0(n - 1, used | current)
            current = current << 1
            i += 1
          }
          count
        }
      }
    }

  17. #47
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    En C, ca va un peu plus vite : 80 ms pour les 10 milliards :

    Code:
    #include <stdio.h>
    
    int loop0(int n, short used)
    {
      if(n == 0) {
        return 1;
      }
      else {
        int count = 0;
        short current = 1;
        for(int i = 0; i<10; i++) {
          if((used & current) == 0) {
    	count += loop0(n - 1, current | used);
          }
          current <<= 1;
        }
        return count;
      }
    }
    
    int loop1(int n)
    {
      int count = 0;
      for(int i = 1; i<10; i++) {
        count += loop0(n-1, 1 << i);
      }
      return count;
    }
    
    int main(int argc, char **argv)
    {
      int count = 0;
      for(int i = 1; i<11; i++) {
        count += loop1(i);
      }
      printf("%d\n", count);
    }

  18. #48
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Garion Voir le message
    J'ai encore complexifiée ma fonction récursive pour atteindre 0.106ms
    Tu peux réessayer en affichant Stopwatch..ElapsedMilliseconds ? Parce que je n'obtiens pas les mêmes chiffres que toi. Je suis à 2 ms avec ton code.

  19. #49
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    En python, c'est beaucoup plus lent et pas vraiment plus rapide que le code simple avec les permutations : 1 min environ pour les 10 milliards.

    Code:
    def loop1(n):
        count = 0
        for i in range(1, 10):
            count += loop0(n-1, 1 << i)
        return count
    
    def loop0(n, used):
        if(n == 0):
            return 1
        else:
            current = 1
            count = 0
            for i in range(10):
                if((used & current) == 0):
                    count += loop0(n - 1, used | current)
                current = current << 1
            return count
    
    count=0
    for i in range(1, 11):
        count += loop1(i)
    print(count)

  20. #50
    invite73192618

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Une autre version, non optimale pour le temps, mais avec une tentative d'élégance pythonesque dans le code (pas forcément réussie... tout commentaire et amélioration bienvenue).


    Code:
    def nbperm(n, verbose=False):
        listefinale=[]
        for i in range(n):
            listefinale=listefinale+nbde(i+1)
        if verbose: print listefinale
        else: print len(listefinale)        
    
    def nbde(n=1, liste=[str(x+1) for x in range(9)]):
        if n>1: return nbde(n-1, successeur(liste))
        return liste      
    
    def successeur(liste):
        return[liste[x] + str(y) for x in range(len(liste)) for y in range(10) if liste[x].find(str(y)) == -1]
        
    nbperm(5, True)
    for i in range(5): nbperm(i+1)
    Dernière modification par Jiav ; 21/12/2017 à 16h38.

  21. #51
    invite73192618

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    En poussant l'idée un peu plus loin:

    Code:
    def nbperm(n, verbose=False):
        if verbose: print mk_res(n)
        else: print len(mk_res(n))        
    
    def mk_res(n, letexte=[]):
        if n>1: return mk_res(n-1, mk_liste(n) + letexte)
        else: return mk_liste(n) + letexte 
    
    def mk_liste(n=1, liste=[str(x+1) for x in range(9)]):
        if n>1: return mk_liste(n-1, mk_next(liste))
        else: return liste      
    
    def mk_next(liste):
        return[liste[x] + str(y) for x in range(len(liste)) for y in range(10) if liste[x].find(str(y)) == -1]
        
    nbperm(3, True)
    for i in range(5): nbperm(i+1)
    Lisibilité meilleure, non?
    Dernière modification par Jiav ; 21/12/2017 à 17h50.

  22. #52
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Jiav Voir le message
    Lisibilité meilleure, non?
    Je ne suis pas assez "fluent" en python pour vraiment juger. Mais c'est propre en effet.
    Sinon, un collègue à qui j'ai posé la colle a fait la version permutations en Scala beaucoup plus élégant que moi :

    Code:
    def gen(n: Int) = (1 to n).flatMap("0123456789".combinations(_)).flatMap(_.permutations).filter(!_.startsWith("0"))

  23. #53
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par pm42 Voir le message
    Tu peux réessayer en affichant Stopwatch..ElapsedMilliseconds ? Parce que je n'obtiens pas les mêmes chiffres que toi. Je suis à 2 ms avec ton code.
    C'est fait, il me donne 0, je suis avec Delphi 10.1 Berlin compilé en mode release (configuration par défaut du mode release), et exécuté hors debugger. Mon PC même s'il a 9 ans, est pas trop mal vu qu'il est overclocké à 4Ghz.

  24. #54
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par pm42 Voir le message
    En C, ca va un peu plus vite : 80 ms pour les 10 milliards :
    Je suis battu, 125ms pour arriver jusqu'à 10milliards.
    Je viens de tenter une compilation en 64 bits qui utilise mieux les instruction SSE, et je tombe à 120ms.
    Les compilateurs C sont mieux optimisé pour les processeurs récents, ils tirent mieux parti du cache et des instructions des processeurs modernes.
    Je vais convertir ton code C en Delphi pour voir si c'est l'algo ou le compilateur qui fait la différence.

  25. #55
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Garion Voir le message
    C'est fait, il me donne 0, je suis avec Delphi 10.1 Berlin compilé en mode release (configuration par défaut du mode release), et exécuté hors debugger. Mon PC même s'il a 9 ans, est pas trop mal vu qu'il est overclocké à 4Ghz.
    Ok. Je suis en Delphi 10.2 et à 3.5 Ghz. Ceci dit, 125 ms pour arriver à 10 milliards, c'est déjà pas mal du tout.

  26. #56
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Hum, j'ai un problème avec ton code C (mais je suis proche de l'ignare en C)
    D'une part, il ne fait qu'énumérer les possibilités sans les générer. D'autre part, le count donné ne correspond pas à ce qu'obtiens en Delphi.
    J'ai une incertitude avec la ligne
    count += loop0(n-1, 1 << i);
    Soit il faut que j'approfondisse (mais je n'ai pas le temps ce soir) car j'ai une mauvaise compréhension du code C, soit il y a un truc louche.
    Mais j'avoue que je n'ai pas essayé de comprendre l'algo, juste essayé de le convertir.
    Je verrai quand j'aurai le temps.

  27. #57
    pm42

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Si je génère, je vais être un peu plus lent mais ce n'est pas dur non plus. C'est juste un poil chiant et là, j'ai la flemme parce que je vais aller dormir
    Et s'il y a une erreur, c'est possible : j'ai codé ça pendant des pointes d'insomnies dues à une rhino.
    Déjà qu'en temps normal, je ne suis pas infaillible mais là...

    Mais le principe est de faire une 1ère boucle pour le 1er chiffre qui va de 1 à 9 (loop1) et qui ensuite appelle une autre boucle loop0 qui elle fait le chiffre suivant de 0 à 9.
    loop0 continue comme ça.
    Et pour ne jamais utiliser 2 fois le même chiffre, j'utilise un bitfield de 16 bits où je mets à 1 le bit correspondant à ceux déjà pris. Donc si j'ai utilisé 0 et 2, je passe 0000000000000101.

    C'est encore optimisable mais après 3 variantes de l'algo dans 3 langages, je vais passer à autre chose.
    Dernière modification par pm42 ; 21/12/2017 à 23h33.

  28. #58
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Edit... Erreur (confondu décalage à gauche et décalage à droite).
    Je comprend mieux maintenant.
    Dernière modification par Garion ; 21/12/2017 à 23h38.

  29. #59
    Garion

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Et grosso modo, la différence de stratégie, c'est vaut-il mieux tout générer tout et tester un par un avec ton algo optimisé (ta stratégie) ou ne générer que les nombres valides (ma stratégie).
    Ne sachant pas, je vais tester les deux stratégies car ça m'intrigue sur ce cas.
    (putain, je passe une bonne partie de mon temps sur des profiler pour optimiser la performance du code dans mon boulot, j'ai même du écrit du code natif en assembleur SSE3 pour optimiser les choses, je fais de la simulation énergétique des bâtiments).
    Dernière modification par Garion ; 21/12/2017 à 23h52.

Page 2 sur 2 PremièrePremière 2

Discussions similaires

  1. [Energie] Lecture optique de chiffres/nombres
    Par Bientzou dans le forum Électronique
    Réponses: 9
    Dernier message: 11/06/2018, 11h14
  2. Chiffres différents par digits, 74SL47
    Par XDamienX007 dans le forum Électronique
    Réponses: 5
    Dernier message: 16/02/2015, 22h33
  3. Tous les nombres entiers sont égaux.
    Par Sund dans le forum Science ludique : la science en s'amusant
    Réponses: 9
    Dernier message: 26/06/2014, 22h08
  4. nombres en 4 chiffres
    Par inviteafd28d80 dans le forum Science ludique : la science en s'amusant
    Réponses: 3
    Dernier message: 13/03/2010, 23h32
  5. Chiffres et nombres
    Par inviteb06d4484 dans le forum TPE / TIPE et autres travaux
    Réponses: 11
    Dernier message: 30/10/2008, 11h52