1er-Zählung in den Zahlen bis n

[Dagon]

Hi Leute,
wie es die Überschrift schon sagt versuche ich eine Funktion zu entwickeln, die die Häufigkeit der Ziffer 1 in den Zahlen von 1 bis n berechnet. Ich hatte mir den Ansatz überlegt erstmal alle Zahlen von 1-n in eine Liste zu schreiben:

Code: Alles auswählen

 liste = []
 x = 0
 while x < n:
     x = x+1
     liste.append(x)

Nur habe ich da zwar jetzt alle Zahlen drin, doch mir fehlt einfach die zündende Idee wie ich nun die 1en zählen kann. Natürlich könnte ich theoretisch einfach nach 1,10,11,12 etc. suchen lassen, aber das ist ja nicht Sinn der Sache. Wäre schön wenn mir da wer helfen könnte.

[Rebecca]

Wenn du die Zahlen als Strings in speicherst, kannst du mit

Code: Alles auswählen

if "1" in einString

rausfinden, ob eine 1 enthalten ist.

[Rebecca]

Mit anderen Worten:

Code: Alles auswählen

 if "1" in str(125): print "drin"

[Dagon]

Ok jetzt hab ichs soweit:

Code: Alles auswählen

def eins(n):
 x=0
 a=0
 while x <= n:
     if "1" in str(x):
         a=a+1
     x=x+1
 print a

Aber jetzt besteht noch das Problem, dass bei einer 11 nur eine 1 gezählt wird und nicht beide. Da man n ja beliebeig wählen kann müsste auch 111 ls 3 1er 1111 als 4 1er etc. gezählt werden...

[modelnine]

Als One-Liner:

Code: Alles auswählen

sum(str(i).count("1") for i in range(1,n+1))

Und für die Häufigkeit dann logischerweise:

Code: Alles auswählen

sum(str(i).count("1") for i in range(1,n+1))/float(n)

Da das Ding Generator-Expressions benutzt geht es logischerweise nur unter Python 2.4...

[modelnine]

Das ganze geht noch ein Stückchen schneller (da der "einfache" Algorithmus den ich im letzten Post angegeben habe exponentiell skaliert aufgrund von str(x)) wenn man das Problem leicht abwandelt und sagt dass man die relative Häufigkeit einer (beliebigen) Ziffer in <=n-stelligen Zahlen berechnen will, dann kann man nämlich einfach:

r(z,n) = Summe(i=1,n,9^(n-i)*(n i)*i)/10^n

berechnen (wobei (n i) n über i bedeutet und r(z,n) die relative Häufigkeit der Ziffer ze{0-9} bei n>=1-stelligen Zahlen ist). Was man daraus sieht: alle Ziffern haben die selbe relative Häufigkeit, zumindest wenn man das Problem so wie oben leicht abwandelt.

Das ganze kann man mit Sicherheit noch weiter vereinfachen (der Term da oben sollte eine algebraische, also exakte Lösung haben die ohne Summe auskommt wenn mich nicht alles täuscht), aber da müßte ich nachgucken.

Die Implementierung des ganzen überlass ich mal Dir.

[modelnine]

Hier ein Beispielprogramm um das ganze auszurechnen:

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-

import operator

def fak(n):
    if n in (0,1):
        return 1
    else:
        return reduce(operator.mul,range(1,n+1))

def comb(n,k):
    return fak(n)/(fak(k)*fak(n-k))

def r(n):
    return float(sum(9**(n-i)*comb(n,i)*i for i in range(1,n+1)))/10**n

for i in range(1,21):
    print ("Bei einer zufälligen Dezimalzahl mit <=%s Stellen"
           " im Schnitt %s mal die 1" % (i,r(i)))

Gibt eine lustige Ausgabe:

Code: Alles auswählen

modelnine@phoenix ~ $ python test.py
Bei einer zufälligen Dezimalzahl mit <=1 Stellen im Schnitt 0.1 mal die 1
Bei einer zufälligen Dezimalzahl mit <=2 Stellen im Schnitt 0.2 mal die 1
Bei einer zufälligen Dezimalzahl mit <=3 Stellen im Schnitt 0.3 mal die 1
Bei einer zufälligen Dezimalzahl mit <=4 Stellen im Schnitt 0.4 mal die 1
Bei einer zufälligen Dezimalzahl mit <=5 Stellen im Schnitt 0.5 mal die 1
Bei einer zufälligen Dezimalzahl mit <=6 Stellen im Schnitt 0.6 mal die 1
Bei einer zufälligen Dezimalzahl mit <=7 Stellen im Schnitt 0.7 mal die 1
Bei einer zufälligen Dezimalzahl mit <=8 Stellen im Schnitt 0.8 mal die 1
Bei einer zufälligen Dezimalzahl mit <=9 Stellen im Schnitt 0.9 mal die 1
Bei einer zufälligen Dezimalzahl mit <=10 Stellen im Schnitt 1.0 mal die 1
Bei einer zufälligen Dezimalzahl mit <=11 Stellen im Schnitt 1.1 mal die 1
Bei einer zufälligen Dezimalzahl mit <=12 Stellen im Schnitt 1.2 mal die 1
Bei einer zufälligen Dezimalzahl mit <=13 Stellen im Schnitt 1.3 mal die 1
Bei einer zufälligen Dezimalzahl mit <=14 Stellen im Schnitt 1.4 mal die 1
Bei einer zufälligen Dezimalzahl mit <=15 Stellen im Schnitt 1.5 mal die 1
Bei einer zufälligen Dezimalzahl mit <=16 Stellen im Schnitt 1.6 mal die 1
Bei einer zufälligen Dezimalzahl mit <=17 Stellen im Schnitt 1.7 mal die 1
Bei einer zufälligen Dezimalzahl mit <=18 Stellen im Schnitt 1.8 mal die 1
Bei einer zufälligen Dezimalzahl mit <=19 Stellen im Schnitt 1.9 mal die 1
Bei einer zufälligen Dezimalzahl mit <=20 Stellen im Schnitt 2.0 mal die 1
modelnine@phoenix ~ $

Die Vereinfachung sollte ja klar sein (also n/10), wobei ich da ehrlich gesagt auf jeden Fall noch mal nachschauen muß warum das so ist; das kann ich nicht mit Bestimmtheit sagen.

[Joghurt]

Als One-Liner:

Code: Alles auswählen

sum(str(i).count("1") for i in range(1,n+1))

Warum nicht gleich:

Code: Alles auswählen

"".join(map(str,range(1,n+1))).count("1")

Wird natürlich für große n unpraktisch.

[modelnine]

Wird natürlich für große n unpraktisch.

Jo, besonders weil die Stringlänge O(n*logn) wächst, und Du immer noch den Geschwindigkeitsnachteil hast O(a^n). Deswegen schrieb ich ja dass es sinnvoller ist sich ein bissel mit Kombinatorik zu befassen, da geht's dann nämlich in konstanter Zeit.

[Joghurt]

Wieso O(a^n)? O(n)...

Natürlich würde man das einfach mit Kombinatorik lösen, es ging hier aber ja um einen Einzeiler

[modelnine]

Die Konvertierung einer Zahl in Binärdarstellung in Demizaldarstellung (also str(i)) ist O(a^logn). Deswegen sagte ich ja dass der Algorithmus nicht linear skaliert (wie man zuerst vermuten könnte wenn man einfach nur die Schleife sieht).

[Joghurt]

Stimmt. Nicht nachgedacht.