J'ai réé un algorithme permettant de compter sur n'importe quel base (avec n'importe quels caractères).
Cependant je n'en suis pas entièrement satisfait, je le trouve mal optimiser.
J’attends donc simplement vos retours sur celui-ci, des propositions d'amélioration etc...
Comportement:
Le code:
def compter(pas: int, char: list) -> list:
"""
Fonction récursive qui compte à partir
d'un nombre de pas demander et d'une chaine de caractère
"""
#le résultat sera stoker dans cette liste
result = list()
#condition d'arrêt de la fonction récursive
if pas < len(char):
for i in range(pas+1):
result.append(str(char[i]))
else:
# la récursivité commence ici:
#donc si le nombre de pas à effectuer est supérieur aux nombres de caractères,
#On ajoute récursivement les nombres
result.append(compter(pas-1, char))
result.append(str(compter(pas//len(char), char)[-1]) + str(char[pas%len(char)]))
# Pour avoir une liste propre
# sans ça, ça donnerait ça:
# >>> compter(2, [0,1])
# [['0', '1'], '10']
result = result[0] + [result[1]]
return result
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)
La base n'est pas donnée de façon symbolique dans ton exemple. Si je veux une base 16, qu'est-ce que j'écris? [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] ou "0123456789ABCDEF"
Voici une petite esquisse, on peut mettre dans des variables les len(...) On fait comme à la petite école, on compte sur nos doigts avec une "retenue" # La vraie longueur serait log(pas) / log(len(base)) + 1 resultat = [0 for _ in range(pas)] while pas: carry = 1 digit = len(resultat) - 1 while carry: resultat[digit] += carry carry = resultat[digit] // len(base) resultat[digit] %= len(base) digit -= 1 # Je suppose que base est en caractères. liste.append(''.join(base[resultat[i]] for i in range(digit, len(resultat)))) pas -= 1
edit: Indices: J'affiche après l'incrémentation alors que je devrais le faire avant. Le nombre de digits affichés n'est pas correct, il faut garder la plus petite valeur de digit et s'en servir pour la conversion.
- Edité par PierrotLeFou 19 décembre 2021 à 3:06:33
Le Tout est souvent plus grand que la somme de ses parties.
def compter(pas: int, char: list) -> list:
"""
Fonction récursive qui compte à partir
d'un nombre de pas demander et d'une chaine de caractère
"""
#le résultat sera stoker dans cette liste
result = list()
#condition d'arrêt de la fonction récursive
if pas < len(char):
for i in range(pas+1):
result.append(str(char[i]))
else:
# la récursivité commence ici:
#donc si le nombre de pas à effectuer est supérieur aux nombres de caractères,
#On ajoute récursivement les nombres
result.append(compter(pas-1, char))
result.append(str(compter(pas//len(char), char)[-1]) + str(char[pas%len(char)]))
# Pour avoir une liste propre
# sans ça, ça donnerait ça:
# >>> compter(2, [0,1])
# [['0', '1'], '10']
result = result[0] + [result[1]]
return result
A cause des limitations de la récursivité en Python, tu ne pourras pas compter au-delà de 1000 sinon, c'était pas mal tenté.
Ton problème est fondamentalement d'écrire les n premiers entiers dans une base donnée. Il suffit donc d'écrire un programme de conversion dans une base (ce dont Python ne dispose pas nativement), et de procéder exactement comme l'a expliqué mps.
On peut aussi voir la question d'un point de vue «combinatoire». Il s'agit de trouver le suivant dans l'ordre lexicographique sur un alphabet donné. Par exemple, en base 3
le suivant de [1, 2, 0, 1, 2, 2, 2] est [1, 2, 0, 2, 0, 0, 0]
le suivant de [2, 2, 2, 2, 2, 2, 2] est [1, 0, 0, 0, 0, 0, 0, 0]
Il suffit donc de coder une fonction suivant (ce qui revient à gérer l'addition de 1 à un nombre d'où la retenue qu'utilise pierrot) et pour chaque liste obtenue, d'écrire le nombre correspondant :
def suivant(L, N):
n=len(L)
k=n-1
while k>=0 and L[k]==N-1:
k-=1
if k<0:
return [1]+n*[0]
L[k]+=1
L[k+1:]=(n-k-1)*[0]
return L
def compter(n, alpha):
L=[0]
for i in range(n):
print(''.join(alpha[i] for i in L))
L=suivant(L, len(alpha))
compter(10, alpha=["1", "A", "4", "Z"])
J'ai utilisé des slices mais on peut s'en passer. Ce code affiche les 10 premiers nombres (j'ai repris un de tes exemples)
1
A
4
Z
A1
AA
A4
AZ
41
4A
On doit aussi pouvoir parvenir au même résultat en utilisant la fonction product du module itertools.
- Edité par PascalOrtiz 19 décembre 2021 à 14:16:19
C'est pas de la triche avec itertools? Ca me retourne le cerveau à chaque fois cet exercice car je sais que les solutions peuvent être simples et je galère à en retrouver une :
def test(a=5, b='abc'):
ids = [0]
c = len(b)
for x in range(a+1):
for i, z in enumerate(ids):
if z == c:
try:
ids[i] = 0
ids[i+1] += 1
except:
ids.append(1)
print(''.join(b[index] for index in ids[::-1]), ids)
ids[0] += 1
Pas trouvé plus simple...
>>> test(8,["1", "A", "4", "Z"])
1 [0]
A [1]
4 [2]
Z [3]
A1 [0, 1]
AA [1, 1]
A4 [2, 1]
AZ [3, 1]
41 [0, 2]
Je ne crois pas qu'on puisse s'en sortir sans que la base soit en symbolique (caractêres); - def convert(n, base): b = len(base) s = "" while n: s = base[n%b] + s n //= b return s or base[0] def compte(pas, base): liste = [] for c in range(pas): liste.append(convert(c, base)) return liste print(compte(4, "01")) print(compte(6, "0123456789")) print(compte(13, "abcd")) - ['0', '1', '10', '11'] ['0', '1', '2', '3', '4', '5'] ['a', 'b', 'c', 'd', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc', 'cd', 'da']
Le Tout est souvent plus grand que la somme de ses parties.
Sans doute pour le lycéen (?) qui a l'exo à faire mais product fait presque ce qui est demandé donc c'est naturel de l'utiliser.
ErispoeLeNarvalo a écrit:
def test(a=5, b='abc'):
ids = [0]
c = len(b)
for x in range(a+1):
for i, z in enumerate(ids):
if z == c:
try:
ids[i] = 0
ids[i+1] += 1
except:
ids.append(1)
print(''.join(b[index] for index in ids[::-1]), ids)
ids[0] += 1
Pas trouvé plus simple...
Ton code est simple et efficace, tu passes le test de 20 millions :
def test(a=5, b='abc'):
ids = [0]
c = len(b)
L=[]
for x in range(a+1):
for i, z in enumerate(ids):
if z == c:
try:
ids[i] = 0
ids[i+1] += 1
except:
ids.append(1)
L.append(''.join(b[index] for index in ids[::-1]))
ids[0] += 1
return L
L=(test(20*10**6, "0123456789"))
print(L[-1])
Tu passes le test en 30s sur ma machine et surtout, avec une conso mémoire très raisonnable.
Il faut que tu rajoutes +1 à n ! Regarde le comportement en exemple.
En effet, il commence à compter à zéro.
ЯК a écrit:
Je ne suis pas sûr de l'intérêt de la fonction, mais pour le fun je propose avec product :
import itertools
import math
def my_product(length, digits):
digits = list(map(str, digits))
results, firsts = digits[:length], digits[1:]
for magnitude in range(1, math.ceil(math.log(length, len(digits)))):
for sequence in itertools.product(firsts, *[digits] * magnitude):
results.append(''.join(sequence))
return results[:length]
print(my_product(10, ["Foo", "Bar", "Baz"]))
Si n n'est pas trop grand, le programme est rapide. Mais dès qu'on dépasse la dizaine de millions, la conso mémoire s'affole et freeze le PC. Exemple :
import itertools
import math
def my_product(length, digits):
digits = list(map(str, digits))
results, firsts = digits[:length], digits[1:]
for magnitude in range(1, math.ceil(math.log(length, len(digits)))):
for sequence in itertools.product(firsts, *[digits] * magnitude):
results.append(''.join(sequence))
return results[:length]
L=my_product(20*10**7+1, list("0123456789"))
print(L[-1])
Si on mettait un compteur pour arrêter quand n est atteint, peut-être que ça irait jusqu'au bout.
Voici un autre code, basé sur la même idée :
from math import log
from itertools import product
def compter(n, alpha):
B=len(alpha)
r=1+int(log(n)//log(B))
# Génère les B**r premiers entiers à partir de 0
p=product(alpha, repeat=r+1)
a=0
b=B
L=[]
cpt=0
for k in range(r):
for i in range(a, b):
z="".join(next(p)[-(k+1):])
L.append(z)
cpt+=1
if cpt>n:
return L
a=b
b=10*a
return L
L=compter(20*10**6, list("0123456789"))
print(L[-1])
Bien qu'utilisant itertools, il faut un peu retravailler le code pour obtenir ce que l'on veut. Mais c'est relativement rapide (8s sur ma machine).
En fait, on peut faire mieux sans itertools :
from math import log
def compter(n, alpha):
if n == 0:
return [alpha[0]]
B = len(alpha)
r = 1 + int(log(n) // log(B))
L = list(alpha[1:])
R = list(alpha)
cpt = B
if n < B:
return R[:n + 1]
for i in range(r):
temp = []
for c in L:
for i in alpha:
temp.append(c + i)
cpt += 1
if cpt > n:
R.extend(temp)
return R
L = temp
R.extend(temp)
return R
R = compter(20 * 10**6, "0123456789")
print(len(R), R[-1])
qui s'exécute en moins de 4s (EDIT : code corrigé suite test de ErispoeLeNarvalo).
PierrotLeFou a écrit:
Je ne crois pas qu'on puisse s'en sortir sans que la base soit en symbolique (caractêres); - def convert(n, base): b = len(base) s = "" while n: s = base[n%b] + s n //= b return s or base[0] def compte(pas, base): liste = [] for c in range(pas): liste.append(convert(c, base)) return liste print(compte(4, "01")) print(compte(6, "0123456789")) print(compte(13, "abcd")) - ['0', '1', '10', '11'] ['0', '1', '2', '3', '4', '5'] ['a', 'b', 'c', 'd', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc', 'cd', 'da']
Ton code est plus efficace que je ne pensais (les divisions sont coûteuses) :
def convert(n, base):
b = len(base)
s = ""
while n:
s = base[n%b] + s
n //= b
return s or base[0]
def compte(pas, base):
liste = []
for c in range(pas):
liste.append(convert(c, base))
return liste
L=(compte(20*10**6, "0123456789"))
print(len(L), L[-1])
Ça met 18s sur ma machine.
EDIT
Et avec la fonction que j'avais donné au début, c'est pas si mal, contrairement à ce que je pensais :
def suivant(L, N):
n=len(L)
k=n-1
while k>=0 and L[k]==N-1:
k-=1
if k<0:
return [1]+n*[0]
L[k]+=1
L[k+1:]=(n-k-1)*[0]
return L
def compter(n, alpha):
R=[]
L=[0]
for i in range(n+1):
R.append(''.join(alpha[i] for i in L))
L=suivant(L, len(alpha))
return R
L=(compter(20*10**6, "0123456789"))
print(len(L), L[-1])
Exécution en moins de 25 s.
- Edité par PascalOrtiz 19 décembre 2021 à 22:06:57
Si n n'est pas trop grand, le programme est rapide. Mais dès qu'on dépasse la dizaine de millions, la conso mémoire s'affole et freeze le PC.
Que serait Python sans thrashing. Bon c'est vrai que ma proposition abuse un peu en essayant de produire 99999999 éléments quand seulement 20M sont nécessaires. xD
Mais ce problème de thrashing finira toujours par arriver alors que le déclenchement d'une erreur serait salvateur. C'est pour ça que je désactive toujours le swap.
Voilà qui est sûrement mieux :
import itertools
import math
def my_product(length, digits):
digits = list(map(str, digits))
results, firsts = digits[:length], digits[1:]
length, magnitude = length - len(results), 0
while length:
magnitude += 1
for sequence in itertools.product(firsts, *[digits] * magnitude):
if length:
results.append(''.join(sequence))
length -= 1
else: break
return results
ls = my_product(20000000, range(10))
print(len(ls), ls[-1])
Oui je savais que ça ne marchait pas (corner case), je corrigerai.
PierrotLeFou a écrit:
Et ceci?
def compte(pas, base):
num = [0]
lg = 1
b = len(base)
liste = []
while pas:
liste.append(''.join(base[c] for c in num))
carry = 1
i = lg-1
while carry:
num[i] += carry
carry = 0
if num[i] >= b:
num[i]=0
if i>0:
carry = 1
i -= 1
else:
num.insert(0, 1)
lg += 1
carry = 0
pas -= 1
return liste
L=(compte(20*10**6, "0123456789"))
print(len(L), L[-1])
S'exécute en 19 s. Je ne pense pas ça joue trop ici (car les listes dont courtes et que l'insertion est rare) mais le num.insert(0, 1) est algorithmiquement hérétique.
J'ai essayé de reprendre ton code en le simplifiant et en supprimant ce qui me paraissait lent mais, curieusement, ton code reste plus rapide :
def compter(n, alpha):
R=[]
L=[0]
m=len(alpha)-1
append=R.append
join=''.join
for i in range(n+1):
append(join(alpha[i] for i in L))
for k in range(len(L)-1, -1, -1):
if L[k]==m:
L[k]=0
else:
break
else:
L.append(0)
L[k]+=1
return R
n=20*10**6
L=(compter(n, "0123456789"))
print(len(L), L[-1])
def compte(pas, base):
num = [0]
lg = 1
b = len(base)
liste = []
while pas:
liste.append(''.join(base[c] for c in num))
carry = 1
i = lg-1
while carry:
num[i] += carry
carry = 0
if num[i] >= b:
num[i]=0
if i>0:
carry = 1
i -= 1
else:
num.insert(0, 1)
lg += 1
carry = 0
pas -= 1
return liste
Travailler directement avec les caractères est plus rapide que passer par des indices :
def suivant(mot, alpha, alpha0):
n=len(mot)
k=n-1
while k>=0 and mot[k]==alpha[-1]:
k-=1
if k<0:
return alpha[1]+alpha0*(n)
i=alpha.index(mot[k])
c=alpha[i+1]
return mot[:k]+c+alpha0*(n-k-1)
n=20*10**6
mot="0"
R=[mot]
for _ in range(n):
mot=suivant(mot, "0123456789", "0")
R.append(mot)
print(len(R), R[-1])
@PascalOrtiz: Et ton code fonctionne avec un ensemble de symboles non conventionel telle que "acfk" Est-ce que le fait que alpha0 soit passé en paramètre est plus rapide que l'évaluer au début de la fonction?
Mes tests ne montrent pas de différence significative.
edit: Ça fonctionne encore plus vite si on en fait un itérateur. - from time import perf_counter def suivant(count, base): base0 = base[0] mot =base0 n=1 while count > 0: count -= 1 yield mot k = n - 1 while k>=0 and mot[k]==base[-1]: k-=1 if k<0: mot = base[1]+base0*(n) n += 1 else: i=base.index(mot[k]) c=base[i+1] mot = mot[:k]+c+base0*(n-k-1) # count = 20*10**6 R=[] begin=perf_counter() for mot in suivant(count, "0123456789"): R.append(mot) print(round(perf_counter()-begin, 3),"secondes") #print(R) #print(len(R), R[-1])
- Edité par PierrotLeFou 20 décembre 2021 à 4:54:34
Le Tout est souvent plus grand que la somme de ses parties.
@PascalOrtiz: Et ton code fonctionne avec un ensemble de symboles non conventionel telle que "acfk" Est-ce que le fait que alpha0 soit passé en paramètre est plus rapide que l'évaluer au début de la fonction?
Mes tests ne montrent pas de différence significative.
Tu as raison, ce 3e paramètre n'est pas utile.
PierrotLeFou a écrit:
edit:
Ça fonctionne encore plus vite si on en fait un itérateur.
Pas testé intensément mais l'avantage semble limité (entre 1% et 2%)
Tout d’abord, Merci pour toutes vos réponses (je m'attendais pas à en recevoir autant).
Les solutions avec itertools ne sont pas exactement ce que je souhaite, mais c'est une solutions qui marche.
La solution avec la fonction suivante n'est pas non-plus exactement ce que je cherche.
Sinon, j'ai adoré toutes vos solutions.
Je propose donc une autre solution, j’aimerai également avoir votre avis et vos conseils sur celui ci:
def compter_nr(pas: int, char: list) -> list:
char = list(map(str, char))
result = ([i for i in char] * (pas//len(char))) + char[:pas%len(char)]
for i in range(len(char)-1,len(result)):
#appliquer la modif du nb d'avant sur l'actuel
if len(result[i-1]) > len(result[i]):
result[i] = result[i-1][:len(result[i-1])-len(result[i])] + result[i]
if char[-1] in result[i]:
i_last_char = None
for b in range(len(result[i])):
if result[i][-(b+1)] != char[-1] :
break
else:
i_last_char = len(result[i])-(b+1)
if i_last_char != None and i != len(result)-1:
if i_last_char:
result[i+1] = result[i][:i_last_char-1] + char[char.index(result[i][i_last_char-1])+1] + char[0]*len(result[i][i_last_char:])
else:
result[i+1] = char[1] + char[0]*len(result[i])
return result
PS: J'ai du mal à comprendre vos code, a cause de mes connaissances limitées notamment en math (je connais les logarithmes uniquement de nom), et en python(je ne maitrise pas itertools ni les itérateurs). Malgré ça j’essaye de me renseigner pour mieux comprendre vos codes.
PS: J'ai du mal à comprendre vos code, a cause de mes connaissances limitées notamment en math (je connais les logarithmes uniquement de nom), et en python(je ne maitrise pas itertools ni les itérateurs). Malgré ça j’essaye de me renseigner pour mieux comprendre vos codes.
Je tire un peu la couverture à moi mais je pense que mon code est le plus simple à comprendre, n'étant pas bon en python ni en math j'ai codé comme si je faisais la manip à la main.
La liste qui apparait dans le code suivant correspond à l'ordre des index qu'il faut prendre en commençant par la fin de la liste, ex : 'ba' -> b est à l'index 1 et a l'index 0 de 'abc', donc on a : ba [0, 1]
>>> test(15,'abc')
a [0]
b [1]
c [2]
ba [0, 1]
bb [1, 1]
bc [2, 1]
ca [0, 2]
cb [1, 2]
cc [2, 2]
baa [0, 0, 1]
bab [1, 0, 1]
bac [2, 0, 1]
bba [0, 1, 1]
bbb [1, 1, 1]
bbc [2, 1, 1]
bca [0, 2, 1]
Effectivement ton code est plus simple, j'ai souvent du mal à pensée simple et je complique souvent trop les choses.
J'ai un tout petit peut modifié ton code à ma sauce (j'ai pratiquement rien changé):
def test(a=20, b='0123456789'):
ids = [0]
c = len(b)
result = list()
for _ in range(a+1):
for i in range(len(ids)):
if ids[i] == c:
try:
ids[i] = 0
ids[i+1] += 1
except IndexError:
ids.append(1)
result.append(''.join(b[index] for index in ids[::-1]))
ids[0] += 1
return result
Je pense que le bon compromis, performance pas trop mauvaise et code facile à comprendre, c'est la solution qui construit la liste en convertissant chaque nombre en sa représentation.
def useless(length, digits):
digits = list(map(str, digits))
base, results = len(digits), []
for number in range(length):
tmp = []
while number:
tmp.append(digits[number % base])
number //= base
results.append(''.join(reversed(tmp)))
return results
Je propose donc une autre solution, j’aimerai également avoir votre avis et vos conseils sur celui ci:
def compter_nr(pas: int, char: list) -> list:
char = list(map(str, char))
result = ([i for i in char] * (pas//len(char))) + char[:pas%len(char)]
for i in range(len(char)-1,len(result)):
#appliquer la modif du nb d'avant sur l'actuel
if len(result[i-1]) > len(result[i]):
result[i] = result[i-1][:len(result[i-1])-len(result[i])] + result[i]
if char[-1] in result[i]:
i_last_char = None
for b in range(len(result[i])):
if result[i][-(b+1)] != char[-1] :
break
else:
i_last_char = len(result[i])-(b+1)
if i_last_char != None and i != len(result)-1:
if i_last_char:
result[i+1] = result[i][:i_last_char-1] + char[char.index(result[i][i_last_char-1])+1] + char[0]*len(result[i][i_last_char:])
else:
result[i+1] = char[1] + char[0]*len(result[i])
return result
Code que je trouve compliqué mais qui montre que tu n'as pas des connaissances en Python aussi limitées que tu le laisses entendre . Le code semble fonctionner. Maintenant, si tu expliquais l'algorithme ...
ebdm13 a écrit:
PS: J'ai du mal à comprendre vos code, a cause de mes connaissances limitées notamment en math (je connais les logarithmes uniquement de nom), et en python(je ne maitrise pas itertools ni les itérateurs).
itertools n'est pas important ici, tu peux ignorer. Les itérateurs, il n'y a rien besoin de savoir dans les codes qui t'ont été proposés. Pour les maths, il faut juste savoir comment le logarithme permet de trouver le nombre de chiffres d'un entier dans une base donnée, c'est juste une formule (mais ça peut se faire facilement sans logarithme avec une simple boucle while, exo classique).
ErispoeLeNarvalo a écrit:
Je tire un peu la couverture à moi mais je pense que mon code est le plus simple à comprendre, n'étant pas bon en python ni en math j'ai codé comme si je faisais la manip à la main.
Comme je t'avais dit ton code est très simple et court, bravo ! Je n'avais pas porté assez d'attention à ton code, en particulier à cause des noms de variables (pour moi peu parlants comme test, idx, x, etc), de l'utilisation d'exceptions (qui me semblaient inutiles ici).
Je viens d'y passer un petit moment pour essayer de comprendre comment ça marche. En fait ton code fait de manière plutôt simple ce que Pierrot et moi parlions dans ce message : tu calcules le suivant du nombre courant en ajoutant 1 manuellement (avec gestion de la retenue) sauf que tu te donnes la possibilité d'écrire la base comme chiffre. Par exemple, si en base 10, j'écris 2029 sous la forme [9, 2, 0, 2], pour rajouter 1 tu écris [10, 2, 0, 2] et tu propages la retenue.
Si je reprends ton code :
def test(a=5, b='abc'):
ids = [0]
c = len(b)
for x in range(a+1):
for i, z in enumerate(ids):
if z == c:
try:
ids[i] = 0
ids[i+1] += 1
except:
ids.append(1)
print(''.join(b[index] for index in ids[::-1]), ids)
ids[0] += 1
je peux facilement en extraire une fonction suivant (j'ai mis juste des noms qui me paraissent plus parlants) :
def suivant(digits, base):
digits[0] += 1
for i, d in enumerate(digits):
if d == base:
digits[i] = 0
try:
digits[i+1] += 1
except:
digits.append(1)
def test(n, alpha='0123456789'):
R=[alpha[0]]
digits = [0]
base = len(alpha)
for _ in range(n):
suivant(digits, base)
R.append(''.join(alpha[index] for index in digits[::-1]))
return R
R=test(112)
print(R)
Le code est super simple et marche très bien mais il n'est pas optimal car la plupart du temps tu testes pour rien si le chiffre courant est la base : par exemple, quand tu ajoutes +1 à 2021, comme 1+1=2 , tu ne vas pas regarder à chaque chiffre pour savoir s'il vaut 10. De même, si tu rajoutes 1 à 2029, à partir du 2e chiffre (à savoir 3), tu n'as pas besoin de regarder derrière s'il y a une retenue à propager. Voilà pourquoi Pierre et moi avons utilisé une boucle while (ou un for/break).
J'avais écrit dans le message déjà cité un code équivalent, que je récris en faisant apparaître une fonction suivant :
def suivant(L, m):
for k in range(len(L)-1, -1, -1):
if L[k]==m:
L[k]=0
else:
break
else:
L.append(0)
L[k]+=1
def compter(n, alpha):
R=[]
L=[0]
m=len(alpha)-1
for i in range(n+1):
R.append(''.join(alpha[i] for i in L))
suivant(L, m)
return R
n=42
L=(compter(n, "0123456789"))
print(len(L), L[-1])
Il y a une différence entre nos deux codes, c'est que tu inverses les chiffres à la fin de l'opération et moi dès le départ. Et aussi qu'au lieu de lever une exception comme tu as fais (bonne idée à propos), je surveille si la retenue dépasse le début du nombre.
ЯК a écrit:
Je pense que le bon compromis, performance pas trop mauvaise et code facile à comprendre, c'est la solution qui construit la liste en convertissant chaque nombre en sa représentation.
def useless(length, digits):
digits = list(map(str, digits))
base, results = len(digits), []
for number in range(length):
tmp = []
while number:
tmp.append(digits[number % base])
number //= base
results.append(''.join(reversed(tmp)))
return results
Oui, c'est la solution assez naturelle (et encore, je ne suis pas sûr que quelqu'un d'inexpérimenté la voit si facilement) et évoquée par mps et en outre assez courte. Du point de vue performance (24 s), ça reste assez moyen (la génération ne tient pas compte des résultats précédents et la division est une opération processeur coûteuse).
- Edité par PascalOrtiz 20 décembre 2021 à 22:50:56
J'ai ajouter des explications à mon code, dites-moi si ce n'est pas assez clair ou si vous avez des suggestion d'amélioration.
Mercie !
def compter_nr(pas: int, char: list) -> list:
"""
Principe:
La base de cette algorithme, est le principe selon lequelle
si l'on prend une liste avec des nombres qui ce suivent,
ex: 0,1,2,3,4,5,6,7,8,9,10,11,12
on remarque que si on prend le dernier caractère de chaque élément et
qu'on en fait une liste, cela donne l'enchainement des caractères définis dans la base x fois.
ex: avec une base="0123456789"
0,1,2,3,4,5,6,7,8,9,10,11,12 -> 0,1,2,3,4,5,6,7,8,9,0,1,2
Puis, pour que cette liste représente bien ces nombres, ex: 0(le 2ème) -> 10
On va regarder si dans l'élément sélectionner de la liste, il y a le dernier caractère de la base: ici 9.
Si c'est le cas, alors il faut tout simplement remplacer le caractère de l'élément suivant avant le 9 par le caractère qui le suit
dans la base. Seulement, si l'on prend 9 par exemple, il n'y a aucun caractère devant lui dans l'élément.
Donc, si tous les caractères de cet élément sont le même que celui du dernier de la base, il faut donc ajouter
le 2ème caractère de la base avant les autres caractères de l'élément et remplacer ses autres caractères par le premier
caractère de la base. Ainsi, 0 -> 10.
Mais si vous avez bien suivi, l'élément d'après, ici: 1,ne sera donc pas changé.
Il faut donc ajouter le radical ajouter de l'élément précédent sur celui-ci.
"""
char = list(map(str, char))
# On défini result sur la liste des derniers caractères: 0,1,2,3,4,5,6,7,8,9,0,1 etc... (en base d?imal)
result = ([i for i in char] * (pas//len(char))) + char[:pas%len(char)]
for i in range(len(char)-1,len(result)):
#appliquer la modif du nb d'avant sur l'actuel
if len(result[i-1]) > len(result[i]):
result[i] = result[i-1][:len(result[i-1])-len(result[i])] + result[i]
if char[-1] in result[i]:
i_last_char = None
# boucle qui permet de définir l'indice du caractère pour lequel il faudra changer
# le caractère suivant de cette élément
# ex: 909; indice = 2, puisqu'il faut arriver à 910
for b in range(len(result[i])):
if result[i][-(b+1)] != char[-1] :
break
else:
i_last_char = len(result[i])-(b+1)
if i_last_char != None and i != len(result)-1:
# pour changer l'élément si il n'y a déjà un caractère devant
# ex: 1099 -> 1100
if i_last_char:
result[i+1] = result[i][:i_last_char-1] + char[char.index(result[i][i_last_char-1])+1] + char[0]*len(result[i][i_last_char:])
# pour changer l'élément si il n'y a pas un caractère devant
# ex: 999->1000
else:
result[i+1] = char[1] + char[0]*len(result[i])
return result
Je comprend tes explications car je suis familier avec le problème, mais je ne sais pas ce que comprendrait quelqu'un qui ne l'a jamais abordé. Comment expliquer que lorsqu'on atteint le dernier symbole de la base pour une position donnée et qu'on veut passer au suivant, il faut revenir au premier. Et ensuite, passer à la position précédent dans cette suite? Et s'il n'y a pas de précédente? En fait, virtuellement, on peut supposer que les positions précédentes sont égales au "zéro" de cette base (le premier symbole) En décimal, 9 = 00000009, et 0 + 1 donne 1. On fait passer le 9 à 0 et à cause de cela, on passe au second symbole et on le fait passer de 0 à 1 C'est ce que j'appelle un "compteur circulaire" ("ring counter" en anglais) On pourrait imaginer une série de roulettes marquées avec les symboles. On commence par faiere avancer celle de droite d'un symbole. Quand on a fait le tour, on entraine la roulette suivante d'une position. Si celle-ci a également fait le tour, on passe à la troisième, etc.
Le Tout est souvent plus grand que la somme de ses parties.
Je comprend tes explications car je suis familier avec le problème, mais je ne sais pas ce que comprendrait quelqu'un qui ne l'a jamais abordé. Comment expliquer que lorsqu'on atteint le dernier symbole de la base pour une position donnée et qu'on veut passer au suivant, il faut revenir au premier. Et ensuite, passer à la position précédent dans cette suite? Et s'il n'y a pas de précédente? En fait, virtuellement, on peut supposer que les positions précédentes sont égales au "zéro" de cette base (le premier symbole) En décimal, 9 = 00000009, et 0 + 1 donne 1. On fait passer le 9 à 0 et à cause de cela, on passe au second symbole et on le fait passer de 0 à 1 C'est ce que j'appelle un "compteur circulaire" ("ring counter" en anglais) On pourrait imaginer une série de roulettes marquées avec les symboles. On commence par faiere avancer celle de droite d'un symbole. Quand on a fait le tour, on entraine la roulette suivante d'une position. Si celle-ci a également fait le tour, on passe à la troisième, etc.
Je ne savais pas que ce système avait un nom, mais j'imaginais exactement ça. Merci pour ces explications plus précises.
× 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.
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)
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.