permutation aléatoire avec [i] = i

Question

Habituellement une permutation aléatoire pour un tableau avec des éléments n signifie une distribution uniforme de n! possibilités, et le shuffle Knuth est utilisé pour le faire:

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i 
    exchange a[j] and a[i] 

Mais avec la contrainte que a[i] != i, je n'ai aucune idée comment former une telle permutation uniformément.

Par exemple, avec n = 3, comment former une permutation aléatoirement à partir des possibilités ci-dessous?

{1, 2, 0}, {2, 0, 1}

Answer 1

Permutation sans point fixe est appelé derangement

Comme le nombre de derangemets est O (n!), tout comme le nombre de permutations, générer toutes les permutations et en filtrant ceux qui ne sont pas les dérangements ne nuiraient pas à votre performance.

La recherche rapide m'a renvoyé these slides, qui décrit un autre algorithme.

Answer 2

Vous n'avez pas précisé la taille de vos baies ni votre degré d'efficacité. Une solution possible serait simplement de faire le shuffle de Knuth, puis de tester si votre contrainte est satisfaite et de refaire le shuffle sinon.

Si vous voulez un peu plus d'efficacité, vous pouvez essayer à la place. Parce que i est décroissante, après l'étape exchange a[j] and a[i], a[i] est fixée. Donc, modifier simplement l'algorithme:

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i; repeat until a[j] != i 
    exchange a[j] and a[i]