Quelle est la probabilité que le tableau reste le même ?

Question

Cette question a été posée lors d'un entretien avec Microsoft. Je suis très curieux de savoir pourquoi ces personnes posent des questions aussi étranges sur les probabilités ?

Étant donné un rand(N), un générateur aléatoire qui génère des nombres aléatoires de 0 à N-1.

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]);
}

EDITAR: Notez que la graine n'est pas fixe.

quelle est la probabilité que le tableau A reste le même ?
Supposons que le tableau contient des éléments uniques.

Answer 1

Je modéliserais le problème comme un multigraphe où les noeuds sont des éléments du tableau et où l'échange consiste à ajouter une connexion non dirigée ( !) entre eux. Ensuite, il faut chercher les boucles d'une manière ou d'une autre (tous les noeuds font partie d'une boucle => original).

J'ai vraiment besoin de me remettre au travail ! :(

Answer 2

Bien, d'un point de vue mathématique :

pour que les éléments du tableau soient échangés au même endroit à chaque fois, alors la fonction Rand(N) doit générer le même nombre deux fois pour int m, et int n. donc la probabilité que la fonction Rand(N) génère le même nombre deux fois est 1/N. et nous avons Rand(N) appelée N fois à l'intérieur de la boucle for, donc nous avons une probabilité de 1/(N^2)

Answer 3

Implémentation naïve en C#. L'idée est de créer toutes les permutations possibles du tableau initial et de les énumérer. Ensuite, nous construisons une matrice des changements d'état possibles. En multipliant la matrice par elle-même N fois, on obtient la matrice montrant combien de chemins existent qui mènent de la permutation #i à la permutation #j en N étapes. L'élément [0,0] montrera combien de chemins mèneront au même état initial. La somme des éléments de la ligne 0 indique le nombre total de chemins différents. En divisant le premier par le second, on obtient la probabilité.

En fait, le nombre total de permutations est 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;
        }
    }
}

Answer 4

La probabilité que m==n à chaque itération, alors faites-le N fois. P(m==n) = 1/N. Donc je pense que P=1/(n^2) pour ce cas. Mais alors vous devez considérer les valeurs qui sont échangées en retour. Donc je pense que la réponse est (l'éditeur de texte m'a eu) 1/N^N.

Answer 5

Question : quelle est la probabilité que le tableau A reste le même ? Condition : On suppose que le tableau contient des éléments uniques.

J'ai essayé la solution en Java.

Un échange aléatoire se produit sur un tableau d'int primitif. Dans les méthodes java, les paramètres sont toujours passés par valeur, donc ce qui se passe dans la méthode swap n'a pas d'importance puisque les éléments a[m] et a[n] du tableau (d'après le code ci-dessous swap(a[m], a[n]) ) sont passés et non pas un tableau complet.

La réponse est que le tableau restera le même. Malgré la condition mentionnée ci-dessus. Voir l'exemple de code java ci-dessous :

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();
    }
}

Exemple de sortie :

Tableau de remplissage : Tableau d'impression : 3 1 1 4 9 7 9 5 9 5 Tableau d'échange : Tableau d'impression : 3 1 1 4 9 7 9 5 9 5