Wiederholungen und generierende Funktionen in Algorithmen

Die Kombinatorik spielt in der Informatik eine wichtige Rolle. Sowohl bei der Analyse als auch beim Entwurf von Algorithmen setzen wir häufig kombinatorische Methoden ein. Zum Beispiel kann eine Methode zum Auffinden eines Vertex-Deckungssatzes in einem Diagramm alle möglichen -Untergruppen untersuchen. Während die Binomialfunktionen exponentiell anwachsen, erhalten wir , wenn eine feste Konstante ist, einen polynomialen Zeitalgorithmus durch asymptotische Analyse.$k$$\binom{n}{k}$$k$

Häufig erfordern reale Probleme komplexere kombinatorische Mechanismen, die wir als Wiederholungen definieren können. Ein berühmtes Beispiel ist die (naiv) definierte Fibonacci-Sequenz :

$f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \\ f(n-1) + f(n-2) & \text{otherwise} \end{cases}$

Die Berechnung des Wertes des $n$ ten Terms wächst nun exponentiell unter Verwendung dieser Wiederholung, aber dank dynamischer Programmierung können wir sie in linearer Zeit berechnen. Jetzt eignen sich nicht alle Wiederholungen für DP (Off Hand, die Fakultätsfunktion), aber es ist eine potenziell ausnutzbare Eigenschaft, wenn eine Zählung eher als Wiederholungsfunktion als als Erzeugungsfunktion definiert wird.

Das Generieren von Funktionen ist eine elegante Möglichkeit, eine Zählung für eine bestimmte Struktur zu formalisieren. Das vielleicht berühmteste ist die Binomialerzeugungsfunktion, die wie folgt definiert ist:

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Zum Glück hat dies eine geschlossene Form Lösung. Nicht alle Erzeugungsfunktionen erlauben eine derart kompakte Beschreibung.

Meine Frage lautet nun: Wie oft werden Generierungsfunktionen beim Entwurf von Algorithmen verwendet? Es ist leicht einzusehen, wie sie ausgenutzt werden können, um die Wachstumsrate zu verstehen, die ein Algorithmus durch Analyse benötigt. Aber was können sie uns über ein Problem bei der Erstellung einer Methode zur Lösung eines Problems sagen?

Wenn ein und dieselbe Zählung oft als eine Wiederholung umformuliert wird, eignet sie sich möglicherweise für die dynamische Programmierung, aber auch hier hat die gleiche Erzeugungsfunktion möglicherweise eine geschlossene Form. Es ist also nicht so gleichmäßig geschnitten.

Das Generieren von Funktionen ist nützlich, wenn Sie Zählalgorithmen entwerfen. Das heißt, nicht nur, wenn Sie nach der Anzahl der Objekte mit einer bestimmten Eigenschaft suchen, sondern auch, wenn Sie nach einer Möglichkeit suchen, diese Objekte aufzulisten (und möglicherweise einen Algorithmus zum Zählen der Objekte zu generieren). In Kapitel 7 der Konkreten Mathematik gibt es eine sehr gute Präsentation von Ronald Graham, Donald Knuth und Oren Patashnik . Die folgenden Beispiele stammen aus diesen Büchern (die Fehler und Unklarheiten sind meine).

Angenommen, Sie suchen nach Möglichkeiten, mit einem bestimmten Satz Münzen Änderungen vorzunehmen. Zum Beispiel sind bei üblichen US-Stückelungen¹ die möglichen Münzen . Um ¢ 42 im Wechsel zu erhalten, ist eine Möglichkeit ; Eine andere Möglichkeit ist . Wir schreiben . Im Allgemeinen können wir eine Erzeugungsfunktion für alle Arten der Änderung schreiben: Technisch gesehen ist ein Term im Raum der Potenzreihen über die fünf Variablen[ 25 ] [ 10 ] [ 5 ] [ 1 ] [ 1 ] [ 10 ] [ 10 ] [ 10 ] [ 10 ] [ 1 ] [ 1 ] 42 ⟨ [ 25 ] [ 10 $[1], [5], [10], [25], [100]$$[25][10][5][1][1]$$[10][10][10][10][1][1]$H = Σ h ≥ 0 Σ q ≥ 0 Σ d ≥ 0 Σ n ≥ 0 Σ p ≥ 0 [ 100 ] h [ 25 ] q [ 10 ] d [ 5 ] n [ 1 ] $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$

$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$ [ 100 ] , [ 25 ] , [ 10 ] , [ 5 ] , [ 1 ] ⟨ [ 100 ] h [ 25 ] q [ 10 ] d [ 5 ] n [ 1 ] p ⟩ = 100 h + 25 q + 10 d + 5 n + p v v H $H$$[100], [25], [10], [5], [1]$. Definieren Sie die Bewertung eines Monoms in diesem Raum durch Dann ist die Anzahl der Monome, deren Bewertung ist, die Möglichkeit, Cent in Veränderung zu geben . Wir können inkrementell ausdrücken , indem wir zuerst die Möglichkeiten aufschreiben , um nur eine Veränderung in Cent zu bewirken, dann die Möglichkeiten , um eine Veränderung in Cent und Nickel zu bewirken und so weiter. ( meine keine Münze.) $$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$ $v$$v$$H$$P$I P = I + [ 1 ] + [ 1 ] 2 + [ 1 ] 3 + … = $N$$I$ $$\begin{gather*} P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\ N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\ D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\ Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\ H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\ \end{gather*}$$ Wenn Sie zählen und nicht nur die Möglichkeiten aufzählen möchten, Änderungen herbeizuführen, gibt es eine einfache Möglichkeit, die formale Reihe zu verwenden, die wir erhalten haben. Wende den Homomorphismus Der Koeffizient von in ist die Anzahl der Möglichkeiten, um Cent in Änderung anzugeben. $$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100}$$ $X^v$$S(C)$$v$

Ein schwierigeres Beispiel: Angenommen, Sie möchten alle Möglichkeiten zum Kacheln von Rechtecken mit 2 × 1-Dominosteinen untersuchen. Zum Beispiel gibt es zwei Möglichkeiten, ein 2 × 2-Rechteck zu kacheln, entweder mit zwei horizontalen Dominosteinen oder mit zwei vertikalen Dominosteinen. Es ist ziemlich einfach, die Anzahl der Kacheln für ein Rechteck zu bestimmen , aber der Fall wird schnell nicht offensichtlich. Wir können alle möglichen Kacheln eines horizontalen Bandes der Höhe 3 durch Zusammenkleben von Dominosteinen , wodurch sich schnell wiederholende Muster ergeben: $2 \times n$$3 \times n$

$$\begin{cases} U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\ V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\ \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\ \end{cases}$$ wo die lustigen Formen elementare Domino-Arrangements darstellen: ist kein Domino, ist ein vertikaler Domino über dem linken Teil eines horizontalen , ist ein vertikaler der am unteren Rand des Bandes der Höhe 3 ausgerichtet ist, ist ein horizontaler Dominostein, der am oberen Rand des Bandes ausgerichtet ist, plus zwei horizontale Dominosteine ​​darunter und einen Schritt nach rechts. usw. Hier repräsentiert Multiplikation horizontale Verkettung und ist nicht kommutativ, aber es gibt Gleichungen zwischen den Elementarmustern, die Variablen in dieser Potenzreihe bilden. Wie zuvor bei den Münzen können wir jedes Domino durch ersetzen und eine generierende Reihe für die Anzahl der Kacheln von a erhalten$\mathsf{o}$$\mathsf{L}$$\substack{\strut\\\mathsf{I}}$$\substack{\:-\\=}$$X$$3 \times (2n/3)$ Rectangle (dh der Koeffizient von ist die Anzahl der Möglichkeiten, ein Rechteck der Fläche , das Dominosteine enthält und die Breite ). Die Serie kann auch vielseitiger eingesetzt werden. Indem wir beispielsweise vertikale und horizontale Dominosteine ​​unterscheiden, können wir die Fliesen mit einer bestimmten Anzahl vertikaler und horizontaler Dominosteine ​​zählen.$X^{3k}$$6k$$3k$$2k$

Lesen Sie erneut Konkrete Mathematik, um eine weniger überstürzte Präsentation zu erhalten.

¹ _{Ich weiß, dass meine Liste unvollständig ist. Nehmen Sie ein vereinfachtes US an, das für mathematische Beispiele geeignet ist.²}
² _{Nehmen Sie auch kugelförmige Münzen an, wenn es auftaucht.}
³ _{Und besser gesetzt.}

Ich erinnere mich an ein Problem, das ich 2001 während eines Studentenprogrammierwettbewerbs lösen musste. Das Problem war das folgende:

Bei Massen von 1, 7, 13, ... (ich erinnere mich nicht, welche Massen, aber es gab eine endliche, bestimmte Menge von Massen), entwerfen Sie eine Funktion, die bestimmt, ob ein bestimmtes Gewicht auf einer Waage damit gewogen werden kann Menge von Massen.

Ich begann mit verschachtelten Schleifen, traf aber schnell eine Wand. Dann wurde mir klar, dass ich zunächst aufzählen musste, was mit den leichteren Massen getan werden kann, bevor ich mit den schwereren fortfuhr. Ich könnte das Problem mit vielen nicht verschachtelten Schleifen lösen.

Wäre ich damals nicht jugendlich arrogant und autark gewesen (und hätte ich nicht gewusst und geübt, Funktionen zu generieren), hätte ich das Problem mit dem Generieren von Funktionen möglicherweise als solches definiert:

Definieren Sie als OGF für die Anzahl der Möglichkeiten, wie ein Gewicht unter Berücksichtigung der Menge der Massen gewogen werden kann.$f(x)$$n$

Welches Gewicht auf der rechten Pfanne kann ich bei einer Masse von 1 wiegen?

Drei Möglichkeiten:

• Wenn ich die Masse auf die linke Pfanne lege, kann ich 1 wiegen.
• Wenn ich die Masse auf die richtige Pfanne lege, kann ich -1 wiegen.
• Wenn ich die Masse nicht benutze, kann ich 0 wiegen.

Es gibt also eine Möglichkeit, zu wiegen , eine Möglichkeit, zu wiegen und eine Möglichkeit, zu wiegen . Die Erzeugungsfunktion für diese Masse ist so etwas wie , was entspricht:$-1$$0$$1$$x^{-1} + 1 + x$

$$\frac{1 - x^3}{x(1-x)}$$

Die Erzeugungsfunktion für eine einzelne Masse ist , was ist:$m$$x^{-m} + 1 + x^m$

$$\frac{1 - x^{3m}}{x^m(1-x^m)}$$

Bei einem Multiset von Massen wird als Produkt der Funktionen zur Erzeugung einer einzelnen Masse ausgedrückt:$M$$f$

$$f(x) = \frac{\prod_{m \in M}(1 - x^{3m})}{x^{\sum_{m \in M}m}\prod_{m \in M}(1 - x^{m})}$$

Nun müssen Sie bei einem Paket, das Operationen an Polynomen ausführen kann, nur noch:

• Berechnen Sie beide Produkte.
• Führen Sie die Aufteilung dieser Produkte aus, beginnend mit dem niedrigsten Grad. (was endet)
• Verschiebt das Polynom (euklidische Division durch , behält den Quotienten bei und wirft den Rest ab)$x^k$

Und du bist fertig. Jetzt hat Ihr Polynom die Anzahl der Möglichkeiten, am Index zu wiegen . Der einzige Eingang ist die multiset der Massen .$w \ge 0$$w$$M$

Ich habe den Algorithmus mit mathematisch fundierten Komponenten entworfen. Der Hauptteil des Algorithmus, bei dem es sich um eine Polynomdivision mit dem niedrigsten Grad zuerst handelt, ist linear und kann durch ein Standardpaket implementiert werden. Es ist vielleicht nicht optimal, aber es funktioniert auf jeden Fall besser als das, was ich beim Wettbewerb gemacht habe, und auf eine weniger fehleranfällige Weise.

Wenn Sie sich den Teilungsprozess genau ansehen, sehen Sie schnell, dass der Rest in jedem Zustand des Prozesses als "aktueller verborgener Zustand" und der Quotient als Ergebnis betrachtet werden kann. Der Vorgang wird beendet, wenn der "aktuelle verborgene Zustand" überall Null erreicht.

Sie können Polynome als Arrays oder, wenn sie wirklich sehr dünn sind, als Listen mit geordneten Indexkoeffizienten implementieren, was den Algorithmus nicht ändert.

Bei der Entwicklung eines Algorithmus zur monotonen submodularen Maximierung über eine Matroid mussten wir die Wiederholung lösen Nachdem festgestellt wurde, dass , Wir haben das Problem auf die Berechnung einer universellen Sequenz reduziert . Letzteres wurde mit Hilfe von Generierungsfunktionen erreicht, und von dort erhielten wir eine explizite Formel für , wiederum mit Hilfe von Generierungsfunktionen. Sie können die Lösung in der Veröffentlichung finden, wenn Sie neugierig sind, obwohl wir uns nie die Mühe gemacht haben, diese Ableitung aufzunehmen.

$$\ell \gamma^{(m)}_{\ell+1} = (2\ell-m) \gamma^{(m)}_\ell + (m - \ell + 1) \gamma^{(m)}_{\ell-1}, \quad \gamma^{(m)}_0 = 1, \quad \gamma^{(m)}_{m+1} = e.$$ $\gamma^{(m)}_\ell = m(\gamma^{(m-1)}_\ell - \gamma^{(m-1)}_{\ell-1})$$\gamma^{(0)}$$\gamma^{(m)}$

Vielleicht ist das ausführliche Studium von Quicksort und seinen vielen Varianten das klarste Beispiel. Dort regelten kombinatorische Überlegungen die Prüfung von Alternativen, und die Analyse der Lösungen für recht komplexe Gleichungen zeigt Leistungsvorteile (oder auch nicht) von diesen.