Une méthode simple en python3 :
Le code commenté permet de les afficher aussi. Sans l'affichage, cela tourne en 12 ms sur un Xeon E5 3.5 Ghz.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)
Et pour rigoler en ligne de commande :
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.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") '
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") }
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.
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
désolé, je n'avais pas vu le "[PYTHON]" dans le titre.
Les programmes écrits les génèrent, grosse différence.Envoyé par ansset
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;
Tu es sûr du calcul ? Ça parait faible, toute fois je connais pas delphi...
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
Y'a t-il une raison particulière de l'ajouter ?Code:for c in combinations(figures, n):
Dernière modification par mp3dux ; 20/12/2017 à 15h13.
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.
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
5h du math et un de mes 1ers programmes en Python...
Sinon, bien vu de ta part.
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
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
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 } }
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.
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 } } }
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); }
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.J'ai encore complexifiée ma fonction récursive pour atteindre 0.106ms
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)
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)
En poussant l'idée un peu plus loin:
Lisibilité meilleure, non?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)
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"))
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.
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.
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.
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.
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.
Edit... Erreur (confondu décalage à gauche et décalage à droite).
Je comprend mieux maintenant.
Dernière modification par Garion ; 21/12/2017 à 23h38.
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.
