Methode zum Zählen von N-Digit-Zahlen, die angegebene Ziffernmuster erfüllen [geschlossen] ⇐ Python

[Guest]

Was ist ein skalierbarer Weg, um die Anzahl der n-Digit-Zahlen (in gemischtem Radix) zu zählen, die eine Liste verschiedener Ziffernkriterien erfüllen? Was sind beispielsweise die 4 -stelligen Zahlen, die eines dieser Muster haben, in denen das _ angibt, dass die Ziffer alles sein kann: < /p>

Code: Select all

1_ _ _, _ 2 3 _, 4 _ _ 5, _ 5 _ 1, or 4 3 2 1

generiert nur die 10000 -Zahlen und zählt nur diejenigen, die mit einem Muster übereinstimmen, gibt an, dass die Antwort 1260 beträgt. "Erzeugung" skalents exponentiell und das Zählen nicht. Beispiel Radix -Zahlen mit Ziffern mit Basen von [8, 7, 7, 7, 8, 8, 5, 8, 6, 6] dauert ungefähr 14 Sekunden, ungefähr 1/4 so lang, weil sie prod ([8, 7) , 7, 7, 8, 8, 5, 8, 6, 6])/8 ** 10 ist ungefähr 1/4.

< P> Aber wenn die Frage "wie viele 4 -stellige Zahlen mit 1 beginnen" lautete, ist die Antwort einfach. Es ist 1000 oder 10 ** (n-1) wobei n die Anzahl der Ziffern in einer Basis 10-Nummer ist. Ich bin also wirklich neugierig, wie andere diese Aufgabe aus einer Nichtgeneration, d. H. Nicht-Brutenkraft, Sicht, vornehmen würden, denn wenn die Einschränkungen der Größenordnungen kleiner sind als die Reihenfolge der Möglichkeiten, sollte die Antwort Anweisungen sein von Größe auch einfacher zu finden. Oder aus Sympy importieren Sie dies: Wenn es zu langsam ist, ist es (wahrscheinlich) Ihre Schuld. Das Problem ohne so viel Sorge um die Praktikabilität der Berechnung der Anzahl. Elemente im Produkt spielt keine Rolle, wie hier erläutert, wobei eine zweipartnere Matching -Routine die bevorzugte bevorzugte Möglichkeit ist, die einzigartigen Produkte zu generieren (die natürlich gezählt werden können). Fühlen Sie sich für die Grenzen, die ich gerade bewusst bin. In einem größeren System gibt es beispielsweise 10440 einzigartig (2) oben). Die Anzahl der Zahlen, die durch die Muster zulässig sind, beträgt 49399639. Und ich kann diejenigen in etwa 40 Sekunden zählen, was ungefähr doppelt so lange ist wie einfach alle möglichen Zahlen. (Aber ich weiß nicht, wie man sie generiert und dann so schnell gegen diese vielen Muster überprüft.) < /P>
Dauert die Matrix -Methode (Brutekraft mit Numpy) etwa 0,5 Sekunden. Die Brute-Force-Methode wird jedoch mit zunehmender Systemgrößen aus dem Speicher ausgehen.

Code: Select all

>>> def full(bases,patterns):
...     t0 = time()
...     n = len(bases)
...     a = np.zeros(bases, dtype=bool)
...     for pattern in patterns:
...         indices = [slice(None)] * n
...         for i, indices[i] in pattern:
...             pass
...         a[*indices] = True
...     print(a.sum(), time() - t0)
...
>>> full(bases,patterns)
49399639 0.5025269985198975
>>> bases, len(patterns), patterns[:3]
([8, 7, 7, 7, 8, 8, 5, 8, 6, 6], 10440, [[(0, 4), (6, 3), (7, 0)], [(0, 3), (1, 4), (4, 0)], [(4, 1), (7, 7), (8, 3)]])

(Die ersten wenigen der 10440 -Muster werden angezeigt; [(0, 4), (6, 3), (7, 0)] bedeutet "eine Nummer mit Die erste Ziffer von 4, 7. Ziffer von 3 und 8. Ziffer von 0 "oder" 4 _ _ _ _ _ 3 0 _ _ ". < /p>

• 
  Wenn ich versucht habe, Polynomerzeugungsfunktionen zu verwenden, berechnet der Flaschenhals alle Kombinationen von Mustern, die in einer Einschluss-Exklusionszahl verwendet werden sollen. < /li>
  Präfix -Bäume mit den Mustern waren ebenfalls sehr langsam und sie sind besonders nicht von Interesse, wenn sie alle Zahlen generieren und dann im Baum testen, ob sie funktionieren oder nicht.

Irgendwelche anderen Ideen?