Wie groß ist die Wahrscheinlichkeit, dass das Array gleich bleibt?

74

Diese Frage wurde im Microsoft-Interview gestellt. Sehr neugierig zu wissen, warum diese Leute so seltsame Fragen zur Wahrscheinlichkeit stellen?

Bei einem Rand (N) ein Zufallsgenerator, der eine Zufallszahl von 0 bis N-1 erzeugt.

int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
    int m = rand(N);
    int n = rand(N);
    swap(A[m],A[n]);
}

BEARBEITEN: Beachten Sie, dass der Startwert nicht festgelegt ist.

Wie groß ist die Wahrscheinlichkeit, dass Array A gleich bleibt?
Angenommen, das Array enthält eindeutige Elemente.

Grüner Kobold
quelle
9
Für einen festen Nund einen festen Startwert ist die Wahrscheinlichkeit entweder 0oder 1weil sie überhaupt nicht zufällig ist.
Mysticial
25
Wenn dies tatsächlich ein C-Programm ist (wie die Tags vermuten lassen), ist die Wahrscheinlichkeit 1. Die Array-Elemente werden als Wert übergeben (in C gibt es keine Referenzübergabe), sodass die swapFunktion den Inhalt von möglicherweise nicht ändern kann A. \ edit: Nun, swapkönnte auch ein Makro sein ... hoffen wir nur, dass es nicht so ist :)
Reima
13
@reima: Es könnte ein Makro sein.
Evgeny Kluev
4
Fragen Sie auf math.stackexchange.com nach. Eine Umformulierung: Wie groß ist die Wahrscheinlichkeit, dass die Permutation (a_1 b_1) (a_2 b_2) ... (a_n b_n) = Identität in der symmetrischen Gruppe S_n ist, wenn zufällig a_i, b_i gegeben ist?
SDCVVC
11
Äh ... niemand hat bemerkt, dass A NIE INITIALISIERT ist?
Ken Beckett

Antworten:

29

Nun, ich hatte ein bisschen Spaß mit diesem. Das erste, woran ich dachte, als ich das Problem zum ersten Mal las, war die Gruppentheorie (insbesondere die symmetrische Gruppe S n ). Die for-Schleife baut einfach eine Permutation σ in S n auf, indem sie bei jeder Iteration Transpositionen (dh Swaps) zusammensetzt. Meine Mathematik ist nicht allzu spektakulär und ich bin ein bisschen verrostet. Wenn meine Notation nicht stimmt, nimm sie mit.


Überblick

Sei Adas Ereignis, dass unser Array nach der Permutation unverändert bleibt. Wir sind schließlich gebeten , die Wahrscheinlichkeit von Ereignis zu finden A, Pr(A).

Meine Lösung versucht, das folgende Verfahren zu befolgen:

  1. Berücksichtigen Sie alle möglichen Permutationen (dh Neuordnungen unseres Arrays).
  2. Partitionieren Sie diese Permutationen in disjunkte Mengen basierend auf der Anzahl der darin enthaltenen sogenannten Identitätstranspositionen . Dies hilft, das Problem auf gleichmäßige Permutationen zu reduzieren .
  3. Bestimmen Sie die Wahrscheinlichkeit, die Identitätspermutation zu erhalten, vorausgesetzt, die Permutation ist gerade (und von einer bestimmten Länge).
  4. Summieren Sie diese Wahrscheinlichkeiten, um die Gesamtwahrscheinlichkeit zu erhalten, mit der das Array unverändert bleibt.

1) Mögliche Ergebnisse

Beachten Sie, dass jede Iteration der for-Schleife einen Swap (oder eine Transposition ) erzeugt, der eines von zwei Dingen ergibt (aber niemals beide):

  1. Zwei Elemente werden vertauscht.
  2. Ein Element wird mit sich selbst ausgetauscht. Für unsere Absichten und Zwecke bleibt das Array unverändert.

Wir kennzeichnen den zweiten Fall. Definieren wir eine Identitätsumsetzung wie folgt:

Eine Identitätsumsetzung tritt auf, wenn eine Nummer mit sich selbst ausgetauscht wird. Das heißt, wenn n == m in der obigen for-Schleife ist.

Für jeden Lauf des aufgelisteten Codes erstellen wir NTranspositionen. 0, 1, 2, ... , NIn dieser "Kette" können Identitätsumwandlungen auftreten.


Betrachten Sie zum Beispiel einen N = 3Fall:

Given our input [0, 1, 2].
Swap (0 1) and get [1, 0, 2].
Swap (1 1) and get [1, 0, 2]. ** Here is an identity **
Swap (2 2) and get [1, 0, 2]. ** And another **

Beachten Sie, dass es eine ungerade Anzahl von Nichtidentitätstranspositionen gibt (1) und das Array geändert wird.


2) Partitionierung basierend auf der Anzahl der Identitätstranspositionen

Sei K_idas Ereignis, dass iIdentitätstranspositionen in einer gegebenen Permutation auftreten. Beachten Sie, dass dies eine vollständige Aufteilung aller möglichen Ergebnisse darstellt:

  • Keine Permutation kann zwei verschiedene Größen von Identitätstranspositionen gleichzeitig haben, und
  • Alle möglichen Permutationen müssen zwischen 0und NIdentitätstranspositionen haben.

Somit können wir das Gesetz der Gesamtwahrscheinlichkeit anwenden :

                      

Jetzt können wir endlich die Partition nutzen. Beachten Sie, dass das Array bei einer ungeraden Anzahl von Nichtidentitäts- Transpositionen auf keinen Fall unverändert bleiben kann *. So:

                        

* Aus der Gruppentheorie ist eine Permutation gerade oder ungerade, aber niemals beides. Daher kann eine ungerade Permutation nicht die Identitätspermutation sein (da die Identitätspermutation gerade ist).

3) Bestimmen von Wahrscheinlichkeiten

Wir müssen nun zwei Wahrscheinlichkeiten für N-igerade bestimmen :

  1. Pr (K_i)
  2. Pr (A | K_i)

Die erste Amtszeit

Der erste Term Pr (K_i)repräsentiert die Wahrscheinlichkeit, eine Permutation mit iIdentitätstranspositionen zu erhalten. Dies stellt sich als binomisch heraus, da für jede Iteration der for-Schleife:

  • Das Ergebnis ist unabhängig von den Ergebnissen davor und
  • Die Wahrscheinlichkeit, eine Identitätstransposition zu erzeugen, ist nämlich dieselbe 1/N.

Daher ist für NVersuche die Wahrscheinlichkeit, iIdentitätstranspositionen zu erhalten, wie folgt:

                      

Die zweite Amtszeit

Also , wenn Sie es bis hierher geschafft haben, haben wir das Problem zu finden , reduziert Pr (A | K_i)für N - iselbst. Dies stellt die Wahrscheinlichkeit dar, eine Identitätspermutation zu erhalten, wenn idie Transpositionen Identitäten sind. Ich verwende einen naiven Zählansatz, um die Anzahl der Wege zum Erreichen der Identitätspermutation über die Anzahl möglicher Permutationen zu bestimmen.

Betrachten Sie zuerst die Permutationen (n, m)und (m, n)Äquivalente. Dann sei Mdie Anzahl der möglichen Nichtidentitätspermutationen. Wir werden diese Menge häufig verwenden.

                              

Ziel ist es, die Anzahl der Möglichkeiten zu bestimmen, wie eine Sammlung von Transpositionen kombiniert werden kann, um die Identitätspermutation zu bilden. Ich werde versuchen, die allgemeine Lösung neben einem Beispiel von zu konstruieren N = 4.


Betrachten wir den N = 4Fall bei allen Identitätstranspositionen ( dh i = N = 4 ). Stellen wir Xeine Identitätstransposition dar. Für jeden Xgibt es NMöglichkeiten (sie sind :) n = m = 0, 1, 2, ... , N - 1. Somit gibt es N^i = 4^4Möglichkeiten, die Identitätspermutation zu erreichen. Der Vollständigkeit halber addieren wir den Binomialkoeffizienten C(N, i), um die Reihenfolge der Identitätstranspositionen zu berücksichtigen (hier ist er nur gleich 1). Ich habe versucht, dies unten mit dem physischen Layout der obigen Elemente und der Anzahl der folgenden Möglichkeiten darzustellen:

I  =  _X_   _X_   _X_   _X_
       N  *  N  *  N  *  N  * C(4, 4) => N^N * C(N, N) possibilities

Jetzt, ohne explizit N = 4und zu ersetzen i = 4, können wir den allgemeinen Fall betrachten. Wenn wir das Obige mit dem zuvor gefundenen Nenner kombinieren, finden wir:

                          

Das ist intuitiv. In der Tat sollte Sie jeder andere Wert als 1wahrscheinlich alarmieren. Denken Sie darüber nach: Wir erhalten die Situation, in der alle NTranspositionen als Identitäten bezeichnet werden. Was ist wahrscheinlich, dass das Array in dieser Situation unverändert bleibt? Klar , 1.


N = 4Betrachten wir nun noch einmal zwei Identitätstranspositionen ( dh i = N - 2 = 2 ). Als Konvention werden wir die beiden Identitäten am Ende platzieren (und später bestellen). Wir wissen jetzt, dass wir zwei Transpositionen auswählen müssen, die, wenn sie komponiert werden, zur Identitätspermutation werden. Platzieren wir ein Element an der ersten Stelle und nennen es t1. Wie oben erwähnt, gibt es MMöglichkeiten, vorausgesetzt, es t1handelt sich nicht um eine Identität (es kann nicht so sein, wie wir bereits zwei platziert haben).

I  =  _t1_   ___   _X_   _X_
       M   *  ?  *  N  *  N

Das einzige Element, das möglicherweise noch an der zweiten Stelle verbleiben könnte, ist das Inverse von t1, was tatsächlich der Fall ist t1(und dies ist das einzige Element aufgrund der Eindeutigkeit des Inversen). Wir schließen wieder den Binomialkoeffizienten ein: In diesem Fall haben wir 4 offene Stellen und wir möchten 2 Identitätspermutationen platzieren. Wie viele Möglichkeiten können wir das tun? 4 wählen Sie 2.

I  =  _t1_   _t1_   _X_   _X_ 
       M   *  1   *  N  *  N  * C(4, 2) => C(N, N-2) * M * N^(N-2) possibilities

Betrachtet man noch einmal den allgemeinen Fall, so entspricht dies alles:

                      

Schließlich machen wir den N = 4Fall ohne Identitätstranspositionen ( dh i = N - 4 = 0 ). Da es viele Möglichkeiten gibt, wird es schwierig und wir müssen aufpassen, dass wir nicht doppelt zählen. In ähnlicher Weise beginnen wir, indem wir ein einzelnes Element an die erste Stelle setzen und mögliche Kombinationen ausarbeiten. Nehmen Sie die einfachste zuerst: die gleiche Umsetzung 4 Mal.

I  =  _t1_   _t1_   _t1_   _t1_ 
       M   *  1   *  1   *  1   => M possibilities

Betrachten wir nun zwei einzigartige Elemente t1und t2. Es gibt MMöglichkeiten für t1und nur M-1Möglichkeiten für t2(da t2kann nicht gleich sein t1). Wenn wir alle Vorkehrungen ausschöpfen, bleiben uns die folgenden Muster:

I  =  _t1_   _t1_   _t2_   _t2_ 
       M   *  1   *  M-1 *  1   => M * (M - 1) possibilities   (1)st

   =  _t1_   _t2_   _t1_   _t2_
       M   *  M-1 *  1   *  1   => M * (M - 1) possibilities   (2)nd

   =  _t1_   _t2_   _t2_   _t1_
       M   *  M-1 *  1   *  1   => M * (M - 1) possibilities   (3)rd

Betrachten wir nun drei einzigartige Elemente, t1, t2, t3. Lassen Sie uns t1zuerst und dann platzieren t2. Wie immer haben wir:

I  =  _t1_   _t2_   ___   ___ 
       M   *  ?   *  ?  *  ?  

Wir können noch nicht sagen, wie viele Möglichkeiten t2es noch geben kann, und wir werden gleich sehen, warum.

Wir platzieren uns jetzt t1auf dem dritten Platz. Beachten Sie, t1dass wir dorthin gehen müssen, da wir, wenn wir an der letzten Stelle hingehen würden, nur das (3)rdobige Arrangement neu erstellen würden . Doppelzählung ist schlecht! Dadurch bleibt das dritte eindeutige Element t3an der endgültigen Position.

I  =  _t1_   _t2_   _t1_   _t3_ 
       M   *  ?   *  1  *   ?  

Warum mussten wir uns eine Minute Zeit nehmen, um die Anzahl der t2s genauer zu betrachten ? Die Transpositionen t1und t2 können keine disjunkten Permutationen sein ( dh sie müssen eine (und nur eine, da sie auch nicht gleich sein können) von ihrem noder teilen m). Der Grund dafür ist, dass wir die Reihenfolge der Permutationen vertauschen könnten, wenn sie disjunkt wären. Dies bedeutet, dass wir die (1)stAnordnung doppelt zählen würden .

Sagen Sie t1 = (n, m). t2muss von der Form (n, x)oder (y, m)für einige sein xund yum nicht disjunkt zu sein. Beachten Sie, dass xmöglicherweise nicht noder mund yviele nicht noder sind m. Somit ist die Anzahl der möglichen Permutationen, t2die sein könnten, tatsächlich 2 * (N - 2).

Kommen wir also zu unserem Layout zurück:

I  =  _t1_    _t2_    _t1_   _t3_ 
       M   * 2(N-2) *  1   *  ?  

Jetzt t3muss die Umkehrung der Zusammensetzung von sein t1 t2 t1. Machen wir es manuell:

(n, m)(n, x)(n, m) = (m, x) 

Also t3muss sein (m, x). Hinweis : Dies ist nicht zu disjunkt t1und nicht entweder gleich t1oder t2so gibt es keine Doppelzählung für diesen Fall.

I  =  _t1_    _t2_    _t1_   _t3_ 
       M   * 2(N-2) *  1  *   1    => M * 2(N - 2) possibilities   

Zum Schluss noch alles zusammen:

        

4) Alles zusammenfügen

Das war's. Arbeiten Sie rückwärts und ersetzen Sie das, was wir gefunden haben, durch die ursprüngliche Summe in Schritt 2. Ich habe die Antwort auf den folgenden N = 4Fall berechnet . Es stimmt sehr genau mit der empirischen Zahl überein, die in einer anderen Antwort gefunden wurde!

         N = 4
         M = 6 _________ _____________ _________
                  | Pr (K_i) | Pr (A | K_i) | Produkt |
         _________ | _________ | _____________ | _________ |
        | | | | |
        | i = 0 | 0,316 | 120/1296 | 0,029 |
        | _________ | _________ | _____________ | _________ |
        | | | | |
        | i = 2 | 0,211 | 6/36 | 0,035 |
        | _________ | _________ | _____________ | _________ |
        | | | | |
        | i = 4 | 0,004 | 1/1 | 0,004 |
        | _________ | _________ | _____________ | _________ |
                            | | |
                            | Summe: | 0,068 |
                            | _____________ | _________ |

Richtigkeit

Es wäre cool, wenn es ein Ergebnis in der Gruppentheorie gäbe, das hier angewendet werden könnte - und vielleicht gibt es das! Es würde sicherlich dazu beitragen, dass all diese mühsamen Zählungen vollständig verschwinden (und das Problem auf etwas viel eleganteres verkürzen). Ich hörte auf zu arbeiten N = 4. Denn N > 5was gegeben ist, gibt nur eine Annäherung (wie gut, ich bin nicht sicher). Es ist ziemlich klar, warum das so ist, wenn Sie darüber nachdenken: Zum Beispiel gibt es bei gegebenen N = 8Transpositionen eindeutig Möglichkeiten, die Identität mit vier einzigartigen Elementen zu schaffen, die oben nicht berücksichtigt wurden. Die Anzahl der Wege wird anscheinend schwieriger zu zählen, wenn die Permutation länger wird (soweit ich das beurteilen kann ...).

Jedenfalls konnte ich so etwas im Rahmen eines Interviews definitiv nicht machen. Wenn ich Glück hätte, würde ich bis zum Nenner kommen. Darüber hinaus scheint es ziemlich böse.

Nutzer
quelle
Ich denke nicht, dass Sie Recht haben, weil es Abhängigkeiten zwischen den Ereignissen gibt - Pr (A und K = 0) + Pr (A und K = 1) + ... + Pr (A und K = N). Und nach Ihrer Analyse nehmen Sie nicht an.
Barak1412
Hmm, danke für den Hinweis. Vielleicht wende ich es falsch an, aber ich habe über das Ergebnis nachgedacht: Sei K_1, K_2, ..., K_N eine Partition unseres Raumes S. Sei A ein Unterraum von S. Dann (manchmal als Gesamtwahrscheinlichkeit bezeichnet, denke ich): P (A) = Summe von Pr (A | K_i) * P (K_i). Ich bin mir ziemlich sicher, dass das Teilen auf diese Weise auch eine Partition erzeugt: Keine Permutation kann in zwei verschiedenen Teilmengen vorliegen (da sie eine einzige Anzahl von Identitäten hat) und alle möglichen Permutationen werden berücksichtigt.
Benutzer
afaict was du hast ist in Ordnung (außer dass der Zähler aus dem Nichts erscheint ...)
Andrew Cooke
Die Antwort ist in dieser Hinsicht sicherlich schwach. Ich habe versucht, einen Einblick in das Beispiel zu geben, aber es ist zugegebenermaßen nicht sehr gut. Es geht meistens nur darum, wo immer möglich effizient zu zählen und zu zählen (indem Muster verwendet werden, die möglicherweise auftreten könnten). Ich habe es für ein paar Fälle überprüft, aber offensichtlich nicht für alle; Dort sollte wahrscheinlich ein Sternchen stehen. Wenn es ein gutes Mittel gäbe, um diese Wahrscheinlichkeit zu berechnen, wäre diese Lösung meiner Meinung nach ziemlich ordentlich. Es ist mir aber definitiv entgangen! :)
Benutzer
1
Das ist die richtige Antwort. Es trifft alle richtigen Schlagworte ("Permutation", "Transposition", "Identität") und die Argumentation ist richtig: 1) Betrachten Sie die Anzahl der tatsächlichen Transpositionen, 2) Berücksichtigen Sie, dass Sie eine gerade Anzahl von Transpositionen benötigen, und 3) Zählen Sie alle die Anzahl der permutierten Paare, aus denen eine Identitätspermutation besteht. Ein Kritikpunkt: Wenn Sie die Dinge präziser geschrieben hätten, wäre es wahrscheinlich offensichtlicher gewesen, dass Sie es richtig machen.
Jérémie
20

Sehr neugierig zu wissen, warum diese Leute so seltsame Fragen zur Wahrscheinlichkeit stellen?

Fragen wie diese werden gestellt, weil sie dem Interviewer ermöglichen, einen Einblick in die des Interviewten zu erhalten

  • Fähigkeit, Code zu lesen (sehr einfacher Code, aber zumindest etwas)
  • Fähigkeit, einen Algorithmus zu analysieren, um den Ausführungspfad zu identifizieren
  • Fähigkeiten bei der Anwendung von Logik, um mögliche Ergebnisse und Randfälle zu finden
  • Argumentations- und Problemlösungsfähigkeiten, während sie das Problem lösen
  • Kommunikations- und Arbeitsfähigkeiten - stellen sie Fragen oder arbeiten sie isoliert auf der Grundlage der vorliegenden Informationen?

... und so weiter. Der Schlüssel zu einer Frage, die diese Attribute des Befragten enthüllt, ist ein täuschend einfacher Code. Dies schüttelt die Betrüger aus, in denen der Nicht-Codierer steckt. der arrogante Sprung zu der falschen Schlussfolgerung; Der faule oder unterdurchschnittliche Informatiker findet eine einfache Lösung und hört auf zu suchen. Wie sie sagen, geht es oft nicht darum, ob Sie die richtige Antwort erhalten, sondern ob Sie mit Ihrem Denkprozess beeindrucken.


Ich werde auch versuchen, die Frage zu beantworten. In einem Interview würde ich mich erklären, anstatt eine einzeilige schriftliche Antwort zu geben - das liegt daran, dass ich logisches Denken demonstrieren kann, selbst wenn meine „Antwort“ falsch ist.

A bleibt gleich - dh Elemente an den gleichen Positionen - wenn

  • m == nin jeder Iteration (so dass jedes Element nur mit sich selbst austauscht); oder
  • Jedes Element, das ausgetauscht wird, wird an seine ursprüngliche Position zurückgesetzt

Der erste Fall ist der 'einfache' Fall, den duedl0r angibt, der Fall, dass das Array nicht geändert wird. Dies könnte die Antwort sein, weil

Wie groß ist die Wahrscheinlichkeit, dass Array A gleich bleibt?

Wenn sich das Array bei ändert i = 1und dann wieder zurückgesetzt wird i = 2, befindet es sich im ursprünglichen Zustand, aber es ist nicht "gleich geblieben" - es wurde geändert und dann wieder geändert. Das könnte eine kluge Technik sein.

Wenn ich dann die Möglichkeit in Betracht ziehe, Elemente auszutauschen und zurückzutauschen, denke ich, dass die Berechnung in einem Interview über meinem Kopf liegt. Die offensichtliche Überlegung ist, dass dies keine Änderung sein muss - Wechsel zurück ändern, es könnte genauso gut einen Austausch zwischen drei Elementen geben, 1 und 2, dann 2 und 3, 1 und 3 und schließlich 2 und 3. Und Wenn Sie fortfahren, kann es zu Swaps zwischen 4, 5 oder mehr Elementen kommen, die so "kreisförmig" sind.

In der Tat, nicht die Fälle , in Anbetracht , wo das Array unverändert ist, kann es einfacher sein , die Fälle zu prüfen , wo es wird geändert. Überlegen Sie, ob dieses Problem auf eine bekannte Struktur wie das Pascalsche Dreieck abgebildet werden kann .


Das ist ein schweres Problem. Ich stimme zu, dass es zu schwer ist, in einem Interview zu lösen, aber das bedeutet nicht, dass es zu schwer ist, in einem Interview zu fragen. Der arme Kandidat wird keine Antwort haben, der durchschnittliche Kandidat wird die offensichtliche Antwort erraten und der gute Kandidat wird erklären, warum das Problem zu schwer zu beantworten ist.

Ich halte dies für eine offene Frage, die dem Interviewer einen Einblick in den Kandidaten gibt. Aus diesem Grund ist es eine gute Frage, die Sie während eines Interviews stellen sollten , auch wenn sie während eines Interviews zu schwer zu lösen sind . Eine Frage zu stellen ist mehr als nur zu prüfen, ob die Antwort richtig oder falsch ist.

Kirk Broadhurst
quelle
Was ist mit längeren Zyklen? können sie nicht existieren? oder sind sie mit zunehmender Zykluslänge zunehmend unwahrscheinlich? man würde hoffen, dass einer der beiden Fälle wahr ist, und es wäre gut, eine quantitative Schätzung darüber abzugeben, wie wichtig sie sind.
Andrew Cooke
2
Leider geht es nicht so ... wenn Sie 1 und 2, dann 2 und 3 und dann 1 und 3 tauschen, wird es nicht der erste Zustand sein ... der letztere muss erneut getauscht werden ...
Erdem E.
3
richtig, aber das ist kein Beweis dafür, dass keine Sequenz mit mehr als 2 Swaps möglich ist. In Ihrer Argumentation machen vier Swaps zum Beispiel alles in Ordnung.
Andrew Cooke
@andrewcooke längere Zyklen können existieren, würden aber davon ausgehen, dass sie im Verhältnis zu ihrer Länge wahrscheinlich exponentiell abnehmen. Vermutlich wird es eine Art Limit geben.
Kirk Broadhurst
Oh, sorry Sieger, dachte du sprichst mit mir!
Andrew Cooke
10

Unten ist C-Code, um die Anzahl der Werte des 2N-Tupels von Indizes zu zählen, die Rand erzeugen und die Wahrscheinlichkeit berechnen kann. Beginnend mit N = 0 werden Zählungen von 1, 1, 8, 135, 4480, 189125 und 12450816 mit Wahrscheinlichkeiten von 1, 1, .5, .185185, .0683594, .0193664 und .00571983 angezeigt. Die Zählungen erscheinen nicht in der Encyclopedia of Integer Sequences , daher hat entweder mein Programm einen Fehler oder dies ist ein sehr dunkles Problem. In diesem Fall soll das Problem nicht von einem Bewerber gelöst werden, sondern einige seiner Denkprozesse und der Umgang mit Frustration aufdecken. Ich würde es nicht als gutes Interviewproblem ansehen.

#include <inttypes.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>


#define swap(a, b)  do { int t = (a); (a) = (b); (b) = t; } while (0)


static uint64_t count(int n)
{
    // Initialize count of how many times the original order is the result.
    uint64_t c = 0;

    // Allocate space for selectors and initialize them to zero.
    int *r = calloc(2*n, sizeof *r);

    // Allocate space for array to be swapped.
    int *A = malloc(n * sizeof *A);

    if (!A || !r)
    {
        fprintf(stderr, "Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    // Iterate through all values of selectors.
    while (1)
    {
        // Initialize A to show original order.
        for (int i = 0; i < n; ++i)
            A[i] = i;

        // Test current selector values by executing the swap sequence.
        for (int i = 0; i < 2*n; i += 2)
        {
            int m = r[i+0];
            int n = r[i+1];
            swap(A[m], A[n]);
        }

        // If array is in original order, increment counter.
        ++c;    // Assume all elements are in place.
        for (int i = 0; i < n; ++i)
            if (A[i] != i)
            {
                // If any element is out of place, cancel assumption and exit.
                --c;
                break;
            }

        // Increment the selectors, odometer style.
        int i;
        for (i = 0; i < 2*n; ++i)
            // Stop when a selector increases without wrapping.
            if (++r[i] < n)
                break;
            else
                // Wrap this selector to zero and continue.
                r[i] = 0;

        // Exit the routine when the last selector wraps.
        if (2*n <= i)
        {
            free(A);
            free(r);
            return c;
        }
    }
}


int main(void)
{
    for (int n = 0; n < 7; ++n)
    {
        uint64_t c = count(n);
        printf("N = %d:  %" PRId64 " times, %g probabilty.\n",
            n, c, c/pow(n, 2*n));
    }

    return 0;
}
Eric Postpischil
quelle
1
Ein unabhängiges Python-Programm liefert die gleichen Ergebnisse bis zu N = 6, sodass Ihre Implementierung korrekt ist. Jede Zählung kann durch N ^ 3 geteilt werden, aber das erscheint auch nicht in OEIS.
Ecatmur
10

Das Verhalten des Algorithmus kann als Markov-Kette über der symmetrischen Gruppe S N modelliert werden .

Grundlagen

Die N Elemente des Arrays Akönnen in N angeordnet werden ! verschiedene Permutationen. Nummerieren wir diese Permutationen von 1 bis N !, ZB durch lexikografische Reihenfolge. Also der Zustand des ArraysA zu jedem Zeitpunkt im Algorithmus vollständig durch die Permutationsnummer charakterisiert werden.

Zum Beispiel für N = 3 eine mögliche Nummerierung aller 3! = 6 Permutationen können sein:

  1. ABC
  2. acb
  3. bac
  4. bca
  5. Taxi
  6. cba

Zustandsübergangswahrscheinlichkeiten

In jedem Schritt des Algorithmus Ableibt der Zustand entweder gleich oder geht von einer dieser Permutationen zu einer anderen über. Wir sind jetzt an den Wahrscheinlichkeiten dieser Zustandsänderungen interessiert. Nennen wir Pr ( ij ) die Wahrscheinlichkeit, dass sich der Zustand in einer einzelnen Schleifeniteration von Permutation i zu Permutation j ändert .

Wenn wir m und n gleichmäßig und unabhängig vom Bereich [0, N -1] auswählen , gibt es N. mögliche Ergebnisse, von denen jedes gleich wahrscheinlich ist.

Identität

Für N dieser Ergebnisse gilt m = n , so dass sich die Permutation nicht ändert. Deshalb,

Pr (i → i).

Transpositionen

Die verbleibenden - N Fälle sind Transpositionen, dh zwei Elemente tauschen ihre Positionen aus und daher ändert sich die Permutation. Angenommen, eine dieser Transpositionen tauscht die Elemente an den Positionen x und y aus . Es gibt zwei Fälle, in denen diese Transposition durch den Algorithmus erzeugt werden kann: entweder m = x , n = y oder m = y , n = x . Somit beträgt die Wahrscheinlichkeit für jede Transposition 2 / .

Wie hängt das mit unseren Permutationen zusammen? Nennen wir zwei Permutationen i und j Nachbarn, wenn und nur wenn es eine Transposition gibt, die i in j umwandelt (und umgekehrt). Wir können dann schließen:

Pr (i → j)

Übergangsmatrix

Wir können die Wahrscheinlichkeiten Pr ( ij ) in einer Übergangsmatrix P ∈ [0,1] N ! × N ! . Wir definieren

p ij = Pr ( ij ),

wobei p ij ist der Eintrag in der i -ten Zeile und j -ten Spalte von P . Beachten Sie, dass

Pr ( ij ) = Pr ( ji ),

was bedeutet, dass P symmetrisch ist.

Der entscheidende Punkt ist nun die Beobachtung dessen, was passiert, wenn wir P mit sich selbst multiplizieren . Nehmen jedes Element p (2) ij von P ²:

p (2) ij

Das Produkt Pr ( ik ) · Pr ( kj ) ist die Wahrscheinlichkeit, dass wir ab der Permutation i in einem Schritt in die Permutation k und nach einem weiteren nachfolgenden Schritt in die Permutation j übergehen. Die Summierung aller dazwischen liegenden Permutationen k ergibt daher die Gesamtwahrscheinlichkeit des Übergangs von i nach j in 2 Schritten .

Dieses Argument kann auf höhere Potenzen von P ausgedehnt werden . Eine besondere Konsequenz ist folgendes:

p ( N ) ii ist die Wahrscheinlichkeit, nach N Schritten zur Permutation i zurückzukehren , vorausgesetzt, wir haben bei der Permutation i begonnen .

Beispiel

Lassen Sie uns dies mit N = 3 durchspielen . Wir haben bereits eine Nummerierung für die Permutationen. Die entsprechende Übergangsmatrix lautet wie folgt:

P.

Das Multiplizieren von P mit sich selbst ergibt:

P²

Eine weitere Multiplikation ergibt:

P³

Jedes Element der Hauptdiagonale gibt uns die gewünschte Wahrscheinlichkeit, das ist 15 / 81 oder 5 / 27 .

Diskussion

Während dieser Ansatz mathematisch fundiert ist und auf jeden Wert von N angewendet werden kann , ist er in dieser Form nicht sehr praktisch. Die Übergangsmatrix P hat N ! ²-Einträge, die sehr schnell riesig werden. Selbst für N = 10 überschreitet die Größe der Matrix bereits 13 Billionen Einträge. Eine naive Implementierung dieses Algorithmus erscheint daher nicht realisierbar.

Im Vergleich zu anderen Vorschlägen ist dieser Ansatz jedoch sehr strukturiert und erfordert keine komplexen Ableitungen, außer herauszufinden, welche Permutationen Nachbarn sind. Ich hoffe, dass diese Struktur genutzt werden kann, um eine viel einfachere Berechnung zu finden.

Zum Beispiel könnte man die Tatsache ausnutzen, dass alle diagonalen Elemente einer Potenz von P gleich sind. Angenommen, wir können die Spur von P N leicht berechnen , dann ist die Lösung einfach tr ( P N ) / N ! Die Spur von P N ist gleich der Summe der N- ten Potenzen seiner Eigenwerte. Wenn wir also einen effizienten Algorithmus zur Berechnung der Eigenwerte von P hätten , wären wir gesetzt. Ich habe dies jedoch nicht weiter untersucht, als die Eigenwerte bis zu N = 5 zu berechnen .

Reima
quelle
Wenn Sie durchschauen, erscheint dies als die einzige fundierte / richtige Antwort zum gesamten Thema. Haben Sie Glück gehabt, das Ergebnis zu verallgemeinern? Ich werde heute Abend einen Blick darauf werfen.
Gleno
@Gleno Ich habe mich nicht mehr mit dem befasst, was ich bereits geschrieben habe. Ich würde gerne von Ihren Erkenntnissen hören!
Reima
1
Nun, ich hatte noch keine Zeit, an dem Problem zu arbeiten. Ich habe Ihre Ergebnisse überprüft (gleiche Matrix für n = 3, gleiche Wahrscheinlichkeiten usw. abgeleitet) und Eigenwerte und Wahrscheinlichkeiten bis zu N = 7 berechnet. Es gibt eindeutig ein Muster, aber es ist mir beim Betrachten der Eigenwertsequenzen nicht aufgefallen . Ich habe auch versucht zu schummeln, indem ich die diagonalen Elemente der Matrizen mit der n-ten Potenz betrachtete und überprüfte, ob diese einer bekannten Sequenz folgten - aber leider nicht. Ein bisschen traurig, dass Ihr Ansatz, der zu diesem Zeitpunkt Wahrscheinlichkeiten für bis zu N = 7 ergeben hat, auf der Seite so niedrig ist.
Gleno
4

Es ist leicht, die Grenzen 1 / n n <= p <= 1 / n zu beobachten.

Hier ist eine unvollständige Idee, eine invers-exponentielle Obergrenze zu zeigen.

Sie zeichnen 2n mal Zahlen aus {1,2, .., n}. Wenn eines davon eindeutig ist (tritt genau einmal auf), wird das Array definitiv geändert, da das Element verschwunden ist und nicht mehr an seinen ursprünglichen Platz zurückkehren kann.

Die Wahrscheinlichkeit, dass eine feste Zahl eindeutig ist, beträgt 2n * 1 / n * (1-1 / n) ^ (2n-1) = 2 * (1-1 / n) ^ (2n-1), was asympotisch 2 / e ist 2 , begrenzt von 0. [2n, weil Sie wählen, bei welchem ​​Versuch Sie es bekommen, 1 / n, dass Sie es bei diesem Versuch bekommen haben, (1-1 / n) ^ (2n-1), dass Sie es nicht bekommen haben andere Versuche]

Wenn die Ereignisse unabhängig wären, würden Sie die Chance bekommen, dass alle Zahlen nicht eindeutig sind (2 / e 2 ) ^ n, was p <= O ((2 / e 2 ) ^ n) bedeuten würde . Leider sind sie nicht unabhängig. Ich bin der Meinung, dass die Grenze mit einer differenzierteren Analyse gezeigt werden kann. Das Schlüsselwort lautet "Balls and Bins Problem".

sdcvvc
quelle
3

Eine vereinfachende Lösung ist

p> = 1 / N N.

Da ein möglicher Weg das Array gleich bleibt, ist wenn m = nfür jede Iteration. Und mgleich nmit der Möglichkeit 1 / N.

Es ist sicherlich höher als das. Die Frage ist, um wie viel ..

Zweiter Gedanke: Man könnte auch argumentieren, dass jede Permutation die gleiche Wahrscheinlichkeit hat, wenn Sie ein Array zufällig mischen. Da es n!Permutationen gibt, ist die Wahrscheinlichkeit, nur eine zu bekommen (die, die wir am Anfang haben), groß

p = 1 / N!

Das ist ein bisschen besser als das vorherige Ergebnis.

Wie diskutiert, ist der Algorithmus voreingenommen. Dies bedeutet, dass nicht jede Permutation die gleiche Wahrscheinlichkeit hat. Ist 1 / N!also nicht ganz genau. Sie müssen herausfinden, wie die Verteilung der Permutationen ist.

duedl0r
quelle
1
Das Array wird zufällig gemischt, die Frage ist, ob es gleichmäßig gemischt wird. Die beiden Konzepte haben nichts miteinander zu tun.
Dietrich Epp
1
@DietrichEpp: Ja, dann müssen Sie zeigen, ob dieser Algorithmus voreingenommen ist oder nicht. Wenn es nicht voreingenommen ist, ist es gleichmäßig verteilt.
duedl0r
5
Ah, ich habe mich gerade an einen super einfachen Beweis erinnert, dass der Algorithmus voreingenommen ist. Der Algorithmus kann auf N ^ N verschiedene Arten gleichmäßig ausführen, aber die Anzahl der Permutationen N! ist mit ziemlicher Sicherheit kein Teiler von N ^ N, daher ist der Algorithmus für N> = 3 voreingenommen.
Dietrich Epp
@ DietrichEpp Für einen Beweis, der n!sich nicht immer teilt n^n, betrachten Sie einfach den Fall, in dem neine Primzahl größer als 2 ist.
Dennis Meng
1
@ duedl0r: Es ist ein mathematischer Beweis. Sie überprüfen ihn, indem Sie die logischen Schritte untersuchen und sicherstellen, dass sie korrekt ausgeführt werden. Es ist nicht erforderlich, das Programm tatsächlich auszuführen, wenn Sie bereits wissen, wie die Antwort lautet. Wie gesagt, es ist kein konstruktiver Beweis, daher gibt der Beweis keine Auskunft darüber, wie stark die Voreingenommenheit ist. Er beweist nur, dass es Voreingenommenheit geben MUSS, da es sonst einen logischen Widerspruch geben würde. Wenn Sie sagen, dass es "abbricht", ist das wirklich nur eine Vermutung, aber Sie können gerne versuchen zu beweisen, dass es sich aufhebt.
Dietrich Epp
3

Zu Ihrer Information, ich bin mir nicht sicher, ob die obige Grenze (1 / n ^ 2) gilt:

N=5 -> 0.019648 < 1/25
N=6 -> 0.005716 < 1/36

Stichprobencode:

import random

def sample(times,n):
    count = 0;
    for i in range(times):
        count += p(n)
    return count*1.0/times;

def p(n):
    perm = range(n);
    for i in range(n):
        a = random.randrange(n)
        b = random.randrange(n)

        perm[a],perm[b]=perm[b],perm[a];


    return perm==range(n)

print sample(500000,5)
dfb
quelle
Beachten Sie, dass Sie tauschen können, indem Sie perm [a], perm [b] = perm [b], perm [a]
robert king
3

Jeder geht davon aus A[i] == i, was nicht ausdrücklich angegeben wurde. Ich werde diese Annahme auch machen, aber beachte, dass die Wahrscheinlichkeit vom Inhalt abhängt. Zum Beispiel wenn A[i]=0, dann ist die Wahrscheinlichkeit = 1 für alle N.

Hier erfahren Sie, wie es geht. Sei P(n,i)die Wahrscheinlichkeit, dass sich das resultierende Array um genau i Transpositionen vom ursprünglichen Array unterscheidet.

Wir wollen es wissen P(n,0). Es ist wahr, dass:

P(n,0) = 
1/n * P(n-1,0) + 1/n^2 * P(n-1,1) = 
1/n * P(n-1,0) + 1/n^2 * (1-1/(n-1)) * P(n-2,0)

Erläuterung: Wir können das ursprüngliche Array auf zwei Arten erhalten, indem wir entweder eine "neutrale" Transposition in einem Array durchführen, das bereits gut ist, oder indem wir die einzige "schlechte" Transposition zurücksetzen. Um ein Array mit nur einer "schlechten" Transposition zu erhalten, können wir ein Array mit 0 schlechten Transpositionen nehmen und eine Transposition durchführen, die nicht neutral ist.

EDIT: -2 ​​statt -1 in P (n-1,0)

Leonhard Euler
quelle
1
1) Die Frage lautet "Angenommen, das Array enthält eindeutige Elemente." Sie können also ohne Verlust der Allgemeinheit davon ausgehen A[i] == i. 2) Ich glaube nicht, dass es P(n,i)im Allgemeinen einen einfachen Weg gibt . Es ist leicht für P(n,0), aber für größere iist unklar, wie viele Transpositionen "gut" und wie viele "schlecht" sind.
SDCVVC
@sdcvvc: Sie sagen, dass es leicht zu finden ist, P(n,0)aber genau darum geht es in der Frage. Wenn Sie mit dieser Argumentation nicht einverstanden sind, geben Sie ein Beispiel an, wo sie fehlschlägt oder warum sie falsch ist.
Leonhard Euler
Das glaube ich nicht P(n-1,1) = (1-1/(n-1)) * P(n-2,0). Wenn Sie sich in der Mitte befinden, können Sie einen weiteren schlechten Schritt hinzufügen, den Sie später rückgängig machen werden. Betrachten Sie zum Beispiel (1234) => (2134) => (2143) => (1243) => (1234). Die Zahl n-1 im Nenner ist ebenfalls verdächtig, da die Zufallsfunktion eine Wiederholung ermöglicht.
SDCVVC
1

Es ist keine vollständige Lösung, aber es ist zumindest etwas.

Nehmen Sie einen bestimmten Satz von Swaps, die keine Wirkung haben. Wir wissen, dass es der Fall gewesen sein muss, dass seine Swaps eine Reihe von Loops unterschiedlicher Größe bildeten, wobei insgesamt nSwaps verwendet wurden. (Zu diesem Zweck kann ein Swap ohne Wirkung als Schleife der Größe 1 betrachtet werden.)

Vielleicht können wir

1) Teilen Sie sie anhand der Größe der Schleifen in Gruppen auf
2) Berechnen Sie die Anzahl der Möglichkeiten, um jede Gruppe zu erhalten.

(Das Hauptproblem ist, dass es eine Menge verschiedener Gruppen gibt, aber ich bin mir nicht sicher, wie Sie dies tatsächlich berechnen würden, wenn Sie die verschiedenen Gruppierungen nicht berücksichtigen.)

Dennis Meng
quelle
1

Interessante Frage.

Ich denke, die Antwort ist 1 / N, aber ich habe keinen Beweis. Wenn ich einen Beweis finde, werde ich meine Antwort bearbeiten.

Was ich bis jetzt habe:

Wenn m == n, wird das Array nicht geändert. Die Wahrscheinlichkeit, m == n zu erhalten, beträgt 1 / N, da es N ^ 2 Optionen gibt und nur N für jede 0 <= i <= N-1 geeignet ist ((i, i)).

Somit erhalten wir N / N ^ 2 = 1 / N.

Bezeichne Pk die Wahrscheinlichkeit, dass nach k Iterationen von Swaps das Array der Größe N gleich bleibt.

P1 = 1 / N. (Wie wir unten gesehen haben)

P2 = (1 / N) P1 + (N-1 / N) (2 / N ^ 2) = 1 / N ^ 2 + 2 (N-1) / N ^ 3.

Explanation for P2:
We want to calculate the probability that after 2 iterations, the array with 
N elements won't change. We have 2 options : 
- in the 2 iteration we got m == n (Probability of 1/N)
- in the 2 iteration we got m != n (Probability of N-1/N)

If m == n, we need that the array will remain after the 1 iteration = P1.
If m != n, we need that in the 1 iteration to choose the same n and m 
(order is not important). So we get 2/N^2.
Because those events are independent we get - P2 = (1/N)*P1 + (N-1/N)*(2/N^2).

Pk = (1 / N) * Pk-1 + (N-1 / N) * X. (der erste für m == n, der zweite für m! = n)

Ich muss mehr darüber nachdenken, was X gleich ist. (X ist nur ein Ersatz für die reale Formel, keine Konstante oder irgendetwas anderes)

Example for N = 2.
All possible swaps:

(1 1 | 1 1),(1 1 | 1 2),(1 1 | 2 1),(1 1 | 2 2),(1 2 | 1 1),(1 2 | 1 2)
(1 2 | 2 1),(1 2 | 2 2),(2 1 | 1 1),(2 1 | 1 2),(2 1 | 2 1),(2 1 | 2 2)
(2 2 | 1 1),(2 2 | 1 2),(2 2 | 2 1),(2 1 | 1 1).

Total = 16. Exactly 8 of them remain the array the same.
Thus, for N = 2, the answer is 1/2.

EDIT: Ich möchte einen anderen Ansatz vorstellen:

Wir können Swaps in drei Gruppen einteilen: konstruktive Swaps, destruktive Swaps und harmlose Swaps.

Konstruktiver Swap ist ein Swap, bei dem mindestens ein Element an die richtige Stelle verschoben wird.

Destruktiver Swap ist ein Swap, bei dem sich mindestens ein Element von seiner korrekten Position bewegt.

Harmloser Swap ist ein Swap, der nicht zu den anderen Gruppen gehört.

Es ist leicht zu erkennen, dass dies eine Partition aller möglichen Swaps ist. (Schnittpunkt = leere Menge).

Nun die Behauptung, die ich beweisen möchte:

    The array will remain the same if and only if 
the number of Destructive swap == Constructive swap in the iterations.

Wenn jemand ein Gegenbeispiel hat, schreiben Sie es bitte als Kommentar auf.

Wenn diese Behauptung richtig ist, können wir alle Kombinationen nehmen und summieren - 0 harmlose Swaps, 1 harmlose Swaps, .., N harmlose Swaps.

Und für jeden möglichen k harmlosen Tausch prüfen wir, ob Nk gerade ist, wenn nein, überspringen wir. Wenn ja, nehmen wir (Nk) / 2 als destruktiv und (Nk) als konstruktiv. Und schauen Sie einfach alle Möglichkeiten.

barak1412
quelle
1
Ihre Argumentation ist falsch, da wir N-mal tauschen, dh die Wahrscheinlichkeit wäre 1 / N ^ 2. Das ist aber auch falsch aufgrund einer Kombination von Faktoren, von denen einige zumindest bereits in anderen Antworten erklärt wurden.
Konrad Rudolph
@KonradRudolph wo hast du gesehen, dass ich geschrieben habe, die Wahrscheinlichkeit ist 1 / N ^ 2? Ich bin sicher, dass das, was ich geschrieben habe, richtig ist.
Barak1412
Können Sie erklären, warum? (welcher Teil ist falsch) Ich bin mir ziemlich sicher, dass es nicht so ist.
Barak1412
Erklärt mein erster Kommentar nicht, was los ist? Die Wahrscheinlichkeit von n = m beträgt 1 / N für einen Swap. Wenn Sie dies N-mal tun, muss es jedes Mal gleich sein, was 1 / N * 1 / N = 1 / N ^ 2 ergibt. Grundsätzlich ist die Berechnung von P2 in Ihrer Antwort falsch. Nur intuitiv sollte es offensichtlich sein, dass die Chance, das ursprüngliche Array zu erhalten, viel, viel kleiner als 1 in N sein sollte.
Konrad Rudolph
Warten Sie, die Argumentation in meinem obigen Kommentar ist falsch. Sie können die Wahrscheinlichkeiten nicht multiplizieren, da sie bedingt sind, aber Ihre Formel für P2 ist immer noch falsch und die Intuition gilt immer noch.
Konrad Rudolph
1

Ich würde das Problem als Multigraph modellieren, bei dem Knoten Elemente des Arrays sind und Swaps eine ungerichtete (!) Verbindung zwischen ihnen hinzufügen. Dann suchen Sie irgendwie nach Schleifen (alle Knoten sind Teil einer Schleife => Original)

Ich muss wirklich wieder arbeiten! :(

user1443778
quelle
1

Nun, aus mathematischer Sicht:

Damit die Array-Elemente jedes Mal an derselben Stelle ausgetauscht werden, muss die Rand (N) -Funktion zweimal dieselbe Zahl für int m und int n generieren. Die Wahrscheinlichkeit, dass die Rand (N) -Funktion zweimal dieselbe Zahl erzeugt, beträgt also 1 / N. und wir haben Rand (N) N-mal innerhalb der for-Schleife aufgerufen, also haben wir eine Wahrscheinlichkeit von 1 / (N ^ 2)

Mokhtar Ashour
quelle
1

Naive Implementierung in C #. Die Idee ist, alle möglichen Permutationen des anfänglichen Arrays zu erstellen und sie aufzulisten. Dann bauen wir eine Matrix möglicher Zustandsänderungen auf. Wenn Sie die Matrix N-mal mit sich selbst multiplizieren, erhalten Sie die Matrix, die zeigt, wie viele Wege existieren, die in N Schritten von der Permutation #i zur Permutation #j führen. Elemet [0,0] zeigt, wie viele Wege zum gleichen Ausgangszustand führen. Die Summe der Elemente der Zeile 0 zeigt die Gesamtzahl der verschiedenen Möglichkeiten. Durch Teilen von ersteren zu letzteren erhalten wir die Wahrscheinlichkeit.

Tatsächlich beträgt die Gesamtzahl der Permutationen N ^ (2N).

Output:
For N=1 probability is 1 (1 / 1)
For N=2 probability is 0.5 (8 / 16)
For N=3 probability is 0.1851851851851851851851851852 (135 / 729)
For N=4 probability is 0.068359375 (4480 / 65536)
For N=5 probability is 0.0193664 (189125 / 9765625)
For N=6 probability is 0.0057198259072973293366526105 (12450816 / 2176782336)

class Program
{
    static void Main(string[] args)
    {
        for (int i = 1; i < 7; i++)
        {
            MainClass mc = new MainClass(i);
            mc.Run();
        }
    }
}

class MainClass
{
    int N;
    int M;

    List<int> comb;
    List<int> lastItemIdx;
    public List<List<int>> combinations;
    int[,] matrix;

    public MainClass(int n)
    {
        N = n;

        comb = new List<int>();
        lastItemIdx = new List<int>();
        for (int i = 0; i < n; i++)
        {
            comb.Add(-1);
            lastItemIdx.Add(-1);
        }

        combinations = new List<List<int>>();
    }

    public void Run()
    {
        GenerateAllCombinations();
        GenerateMatrix();
        int[,] m2 = matrix;
        for (int i = 0; i < N - 1; i++)
        {
            m2 = Multiply(m2, matrix);
        }

        decimal same = m2[0, 0];
        decimal total = 0;
        for (int i = 0; i < M; i++)
        {
            total += m2[0, i];
        }

        Console.WriteLine("For N={0} probability is {1} ({2} / {3})", N, same / total, same, total);
    }

    private int[,] Multiply(int[,] m2, int[,] m1)
    {
        int[,] ret = new int[M, M];
        for (int ii = 0; ii < M; ii++)
        {
            for (int jj = 0; jj < M; jj++)
            {
                int sum = 0;

                for (int k = 0; k < M; k++)
                {
                    sum += m2[ii, k] * m1[k, jj];
                }

                ret[ii, jj] = sum;
            }
        }

        return ret;
    }

    private void GenerateMatrix()
    {
        M = combinations.Count;
        matrix = new int[M, M];

        for (int i = 0; i < M; i++)
        {
            matrix[i, i] = N;
            for (int j = i + 1; j < M; j++)
            {
                if (2 == Difference(i, j))
                {
                    matrix[i, j] = 2;
                    matrix[j, i] = 2;
                }
                else
                {
                    matrix[i, j] = 0;
                }
            }
        }
    }

    private int Difference(int x, int y)
    {
        int ret = 0;
        for (int i = 0; i < N; i++)
        {
            if (combinations[x][i] != combinations[y][i])
            {
                ret++;
            }

            if (ret > 2)
            {
                return int.MaxValue;
            }
        }

        return ret;
    }

    private void GenerateAllCombinations()
    {
        int placeAt = 0;
        bool doRun = true;
        while (doRun)
        {
            doRun = false;
            bool created = false;

            for (int i = placeAt; i < N; i++)
            {
                for (int j = lastItemIdx[i] + 1; j < N; j++)
                {
                    lastItemIdx[i] = j; // remember the test

                    if (comb.Contains(j))
                    {
                        continue; // tail items should be nulled && their lastItemIdx set to -1
                    }

                    // success
                    placeAt = i;
                    comb[i] = j;
                    created = true;
                    break;
                }

                if (comb[i] == -1)
                {
                    created = false;
                    break;
                }
            }

            if (created)
            {
                combinations.Add(new List<int>(comb));
            }

            // rollback 
            bool canGenerate = false;
            for (int k = placeAt + 1; k < N; k++)
            {
                lastItemIdx[k] = -1;
            }

            for (int k = placeAt; k >= 0; k--)
            {
                placeAt = k;
                comb[k] = -1;

                if (lastItemIdx[k] == N - 1)
                {
                    lastItemIdx[k] = -1;
                    continue;
                }

                canGenerate = true;
                break;
            }

            doRun = canGenerate;
        }
    }
}
Artemix
quelle
0

Die Wahrscheinlichkeit, dass m == n bei jeder Iteration ist, dann mache das N-mal. P (m == n) = 1 / N. Ich denke also, dass P = 1 / (n ^ 2) für diesen Fall ist. Aber dann müssen Sie berücksichtigen, dass die Werte zurückgetauscht werden. Ich denke also, die Antwort ist (Texteditor hat mich) 1 / N ^ N.

Jason
quelle
1
Es ist definitiv höher als (1/N)^N. Die Sache ist, dass an sich die Wahrscheinlichkeit ist, dass sich das Array nie wirklich ändert. Wir haben immer noch nicht die Wahrscheinlichkeit gezählt, dass sich Dinge bewegen und einfach in den ursprünglichen Zustand zurückkehren.
Dennis Meng
0

Frage: Wie groß ist die Wahrscheinlichkeit, dass Array A gleich bleibt? Bedingung: Angenommen, das Array enthält eindeutige Elemente.

Versuchte die Lösung in Java.

Das zufällige Austauschen erfolgt auf dem primitiven int-Array. In der Java-Methode werden Parameter immer als Wert übergeben, sodass das, was in der Swap-Methode geschieht, keine Rolle spielt, da [m] und a [n] Elemente des Arrays (von unten Code Swap (a [m], a [n])) sind nicht vollständiges Array übergeben.

Die Antwort lautet: Array bleibt gleich. Trotz des oben genannten Zustands. Siehe unten Java-Codebeispiel:

import java.util.Random;

public class ArrayTrick {

    int a[] = new int[10];
    Random random = new Random();

    public void swap(int i, int j) {
        int temp = i;
        i = j;
        j = temp;
    }

    public void fillArray() {
        System.out.println("Filling array: ");
        for (int index = 0; index < a.length; index++) {
            a[index] = random.nextInt(a.length);
        }
    }

    public void swapArray() {
        System.out.println("Swapping array: ");
        for (int index = 0; index < a.length; index++) {
            int m = random.nextInt(a.length);
            int n = random.nextInt(a.length);
            swap(a[m], a[n]);
        }
    }

    public void printArray() {
        System.out.println("Printing array: ");
        for (int index = 0; index < a.length; index++) {
            System.out.print(" " + a[index]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayTrick at = new ArrayTrick();

        at.fillArray();
        at.printArray();
        at.swapArray();
        at.printArray();
    }
}

Beispielausgabe:

Füllarray: Druckarray: 3 1 1 4 9 7 9 5 9 5 Austauscharray: Druckarray: 3 1 1 4 9 7 9 5 9 5

rashid
quelle
1
Swap (i, j) kann unmöglich etwas beeinflussen, da die ganzen Zahlen als Wert übergeben werden
Judge Mental
Das ist es was ich meinte. Die Methode swap () hat keine Auswirkungen.
Rashid
Nur wegen Ihrer Wahl der Sprache und Implementierung vonswap
OrangeDog