Étant donné un entier positif, $n$ génère tous les dérangements de $n$ objets.

Détails

• Un dérangement est une permutation sans point fixe. (Cela signifie que dans chaque numéro de dérangement, $i$ ne peux pas être dans la $i$ ème entrée).
• La sortie doit consister en des dérangements des nombres $(1,2,\ldots,n)$ (ou alternativement $(0,1,2,\ldots,n-1)$ ).
• Vous pouvez également toujours imprimer les dérangements de $(n,n-1,\ldots,1)$ (ou $(n-1,n-2,\ldots,1,0)$ respectivement) mais vous devez le spécifier.
• La sortie doit être déterministe, c'est-à-dire que chaque fois que le programme est appelé avec un certain $n$ comme entrée, la sortie doit être la même (ce qui inclut que l'ordre des dérangements doit rester le même), et la sortie complète doit être effectuée dans un temps fini à chaque fois (il ne suffit pas de le faire avec la probabilité 1).
• Vous pouvez supposer que $n \geqslant 2$
• Pour certains $n$ donnés, vous pouvez soit générer tous les dérangements, soit prendre un autre entier $k$ qui sert d'index et imprimer le $k$ -ième dérangement (dans l'ordre que vous avez choisi).

Exemples

Notez que l'ordre des dérangements ne doit pas nécessairement être le même que celui indiqué ici:

n=2: (2,1)
n=3: (2,3,1),(3,1,2)
n=4: (2,1,4,3),(2,3,4,1),(2,4,1,3), (3,1,4,2),(3,4,1,2),(3,4,2,1), (4,1,2,3),(4,3,1,2),(4,3,2,1)

OEIS A000166 compte le nombre de dérangements.

Gelée , 6 octets

Œ!=ÐṂR

Un lien monadique acceptant un entier positif qui donne une liste de listes d'entiers.

Essayez-le en ligne!

Comment?

Œ!=ÐṂR - Link: integer, n
Œ!     - all permutations of (implicit range of [1..n])
     R - range of [1..n]
   ÐṂ  - filter keep those which are minimal by:
  =    -   equals? (vectorises)
       -   ... i.e. keep only those permutations that evaluate as [0,0,0,...,0]

Brachylog , 9 octets

⟦kpiᶠ≠ᵐhᵐ

Essayez-le en ligne!

Il s'agit d'un générateur qui génère un dérangement de [0, …, n-1]donné n.

Si nous l'enveloppons dans un ᶠ - findallmétaprédicat, nous obtenons toutes les générations possibles de dérangements par le générateur.

Explication

⟦           The range [0, …, Input]
 k          Remove the last element
  p         Take a permutation of the range [0, …, Input - 1]
   iᶠ       Take all pair of Element-index: [[Elem0, 0],…,[ElemN-1, N-1]]
     ≠ᵐ     Each pair must contain different values
       hᵐ   The output is the head of each pair

JavaScript (V8) , 85 octets

Une fonction récursive imprimant tous les dérangements basés sur 0.

f=(n,p=[],i,k=n)=>k--?f(n,p,i,k,k^i&&!p.includes(k)&&f(n,[...p,k],-~i)):i^n||print(p)

Essayez-le en ligne!

Commenté

f = (                   // f is a recursive function taking:
  n,                    //   n   = input
  p = [],               //   p[] = current permutation
  i,                    //   i   = current position in the permutation
  k = n                 //   k   = next value to try
) =>                    //         (a decrementing counter initialized to n)
  k-- ?                 // decrement k; if it was not equal to 0:
    f(                  //   do a recursive call:
      n, p, i, k,       //     leave all parameters unchanged
      k ^ i &&          //     if k is not equal to the position
      !p.includes(k) && //     and k does not yet appear in p[]:
        f(              //       do another recursive call:
          n,            //         leave n unchanged
          [...p, k],    //         append k to p
          -~i           //         increment i
                        //         implicitly restart with k = n
        )               //       end of inner recursive call
    )                   //   end of outer recursive call
  :                     // else:
    i ^ n ||            //   if the derangement is complete:
      print(p)          //     print it

Ruby , 55 octets

->n{[*0...n].permutation.select{|x|x.all?{|i|i!=x[i]}}}

Essayez-le en ligne!

Génère tous les dérangements basés sur 0

05AB1E , 9 octets

Lœʒāø€Ë_P

Essayez-le en ligne!

Explication

L           # push [1 ... input]
 œ          # get all permutations of that list
  ʒ         # filter, keep only lists that satisfy
   āø       # elements zipped with their 1-based index
     €Ë_P   # are all not equal

Wolfram Language (Mathematica) , 55 octets

Select[Permutations[s=Range@#],FreeQ[Ordering@#-s,0]&]&

Essayez-le en ligne!

Japt , 8 octets

Basé sur 0

o á fÈe¦

Essayez-le (le pied de page incrémente tous les éléments pour une comparaison plus facile avec les cas de test)

o á fÈe¦     :Implicit input of integer
o            :Range [0,input)
  á          :Permutations
    f        :Filter
     È       :By passing each through this function
      e      :  Every element of the permutation
       ¦     :  Does not equal its 0-based index

Python 2 , 102 octets

lambda n:[p for p in permutations(range(n))if all(i-j for i,j in enumerate(p))]
from itertools import*

Essayez-le en ligne!

Indexation basée sur 0, liste de tuples.

itertoolsSolution non basée:

Python 2 , 107 octets

n=input()
for i in range(n**n):
 t=[];c=1
 for j in range(n):c*=j!=i%n not in t;t+=[i%n];i/=n
 if c:print t

Essayez-le en ligne!

Indexation 0, lignes de listes, programme complet.

Remarque: Cette solution, même si elle n'importe pas la itertoolsbibliothèque, n'est pas beaucoup plus longue que l'autre qui l'importe, car la majeure partie du volume ici est en train de construire les permutations. Le contrôle de dérangement est en réalité d'environ 7 octets supplémentaires! La raison en est que le contrôle est effectué à la volée dans le cadre de la construction de chaque permutation. Ce n'est pas vrai pour l'autre solution, où vous devez vérifier si chaque permutation renvoyée par la itertools.permutationsfonction est en fait un dérangement, et, bien sûr, le mappage lui-même prend beaucoup d'octets.

MATL , 11 octets

:tY@tb-!AY)

Cela génère tous les dérangements dans l'ordre lexicographique.

Essayez-le en ligne!

Explication avec exemple

Tenez compte des commentaires 3.

:     % Implicit input n. Range [1 2 ... n]
      % STACK: [1 2 3]
t     % Duplicate
      % STACK: [1 2 3], [1 2 3]
Y@    % All permutations, in lexicographical order, as rows of a matrix
      % STACK: [1 2 3], [1 2 3; 1 3 2; ··· ; 3 2 1]
t     % Duplicate
      % STACK: [1 2 3], [1 2 3; 1 3 2; ··· ; 3 2 1], [1 2 3; 1 3 2; ··· ; 3 2 1]
b     % Bubble up: moves third-topmost element in stack to the top
      % STACK: [1 2 3; 1 3 2; ··· ; 3 2 1], [1 2 3; 1 3 2; ··· ; 3 1 2; 3 2 1], [1 2 3]
-     % Subtract, element-wise with broadcast
      % STACK: [1 2 3; 1 3 2; ··· ; 3 2 1], [0 0 0; 0 1 -1; ··· ; 2 -1 -1; 2 0 -2]
!A    % True for rows containining only nonzero elements
      % STACK: [1 2 3; 1 3 2; ··· ; 3 1 2; 3 2 1], [false false ··· true false]
Y)    % Use logical mask as a row index. Implicit display
      % STACK: [2 3 1; 3 1 2]

Perl 5 -MList::Util=none -n , 100 89 octets

$"=',';@b=1..$_;map{%k=$q=0;say if none{++$q==$_||$k{$_}++}/\d+/g}glob join$",("{@b}")x@b

Essayez-le en ligne!

Haskell , 58 octets

f n|r<-[1..n]=[l|l<-mapM(\i->filter(/=i)r)r,all(`elem`l)r]

Essayez-le en ligne!

60 octets

f n|r<-[1..n]=foldr(\i m->[x:l|l<-m,x<-r,all(/=x)$i:l])[[]]r

Essayez-le en ligne!

Gaia , 10 octets

┅f⟨:ċ=†ỵ⟩⁇

Essayez-le en ligne!

┅		| push [1 2 ... n]
 f		| push permutations
  ⟨	⟩⁇	| filter where result of following is truthy
   :ċ		| dup, push [1 2 ... n]
     =†ỵ	| there is no fixed point

J , 26 octets

i.(]#~0~:*/@(-|:))i.@!A.i.

Essayez-le en ligne!

i. (] #~ 0 ~: */@(- |:)) i.@! A. i.
i. (                   )            NB. 0..input
   (                   ) i.@! A. i. NB. x A. y returns the
                                    NB. x-th perm of y
                                    NB. i.@! returns 
                                    NB. 0..input!. Combined
                                    NB. it produces all perms
                                    NB. of y
    ] #~ 0 ~: */@(- |:)             NB. those 2 are passed as
                                    NB. left and right args
                                    NB. to this
    ] #~                            NB. filter the right arg ]
                                    NB. (all perms) by:
         0 ~:                       NB. where 0 is not equal to...
              */@                   NB. the product of the 
                                    NB. rows of...
                 (- |:)             NB. the left arg minus
                                    NB. the transpose of
                                    NB. the right arg, which
                                    NB. will only contain 0
                                    NB. for perms that have
                                    NB. a fixed point

R , 81 80 octets

function(n)unique(Filter(function(x)all(1:n%in%x&1:n-x),combn(rep(1:n,n),n,,F)))

Essayez-le en ligne!

list$n^2\choose n$n[1..n]n1:n%in%x1:n-x .

R + gtools , 62 octets

function(n,y=gtools::permutations(n,n))y[!colSums(t(y)==1:n),]

Essayez-le en ligne!

Beaucoup plus efficace, renvoie un matrixoù chaque ligne est un dérangement.

Python 3.8 (version préliminaire) , 96 octets

lambda n:(p for i in range(n**n)if len({*(p:=[j for k in range(n)for j in{i//n**k%n}-{k}])})==n)

Essayez-le en ligne!

C ++ (gcc) , 207 196 octets

-5 octets par plafond -6 octets par Roman Odaisky

#include<regex>
#define v std::vector
auto p(int n){v<v<int>>r;v<int>m(n);int i=n;for(;m[i]=--i;);w:for(;std::next_permutation(&m[0],&m[n]);r.push_back(m))for(i=n;i--;)if(m[i]==i)goto w;return r;}

Essayez-le en ligne!

C ++ (gcc) , 133 octets

Je pense que cela s'est suffisamment développé par rapport à l'autre communication pour mériter une réponse distincte. Enfin une utilisation pour la index[array]syntaxe inside-out!

#include<regex>
[](int n,auto&r){int i=n;for(;i[*r]=--i;);for(;std::next_permutation(*r,*r+n);)for(i=n;i--?(r[1][i]=i[*r])-i:!++r;);}

Essayez-le en ligne!

Haskell, 76 octets

n&x=[x++[i]|i<-[1..n],notElem i x,i/=length x+1]
d n=iterate(>>=(n&))[[]]!!n

Python 2 , 82 octets

f=lambda n,i=0:i/n*[[]]or[[x]+l for l in f(n,i+1)for x in range(n)if~-(x in[i]+l)]

Essayez-le en ligne!

88 octets comme programme:

M=[],
r=range(input())
for i in r:M=[l+[x]for l in M for x in r if~-(x in[i]+l)]
print M

Essayez-le en ligne!

93 octets en utilisant itertools:

from itertools import*
r=range(input())
print[p for p in permutations(r)if all(map(cmp,p,r))]

Essayez-le en ligne!

Perl 6 , 49 37 octets

Edit: Après quelques allers-retours avec Phil H, nous l'avons réduit à seulement 37 octets:

(^*).permutations.grep:{all @_ Z-^@_}

Essayez-le en ligne!

En utilisant le Whateverau début, nous pouvons éviter les crochets (enregistre 2 caractères). Utilisez ensuite le Zméta - opérateur avec- lequel prend chaque élément d'une permutation (par exemple 2,3,1) et soustrait 0,1,2 dans l'ordre. Si l'un d'eux vaut 0 (fausse), la jonction échoue.

La solution d'origine était ( Essayez-la en ligne! )

{permutations($_).grep:{none (for $_ {$++==$_})}}

Charbon de bois , 44 28 octets

barré 44 est toujours régulier 44

ＮθＩΦＥＸθθＥθ﹪÷ιＸθλθ⬤ι‹⁼μλ⁼¹№ιλ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Librement basé sur la réponse non-itertools de @ EricTheOutgolfer. Explication:

Ｎθ                              Input `n`
     Ｘθθ                        `n` raised to power `n`
    Ｅ                           Mapped over implicit range
         θ                      `n`
        Ｅ                       Mapped over implicit range
            ι                   Outer loop index
           ÷                    Integer divided by
             Ｘθ                 `n` raised to power
               λ                Inner loop index
          ﹪     θ               Modulo `n`
   Φ                            Filtered where
                  ι             Current base conversion result
                 ⬤              All digits satisfy
                         №ιλ    Count of that digit
                       ⁼¹       Equals literal 1
                   ‹            And not
                    ⁼μλ         Digit equals its position
  Ｉ                             Cast to string
                                Implicitly print

C (gcc) , 187180 octets

• Enregistré sept octets grâce au plafond .

*D,E;r(a,n,g,e){e=g=0;if(!a--){for(;e|=D[g]==g,g<E;g++)for(n=g;n--;)e|=D[n]==D[g];for(g*=e;g<E;)printf("%d ",D[g++]);e||puts("");}for(;g<E;r(a))D[a]=g++;}y(_){int M[E=_];D=M;r(_);}

Essayez-le en ligne!

Pyth , 12 octets

f*F.e-bkT.PU

Essayez-le en ligne!

           UQ # [implicit Q=input] range(0,Q)
         .P  Q# [implicit Q=input] all permutations of length Q
f             # filter that on lambda T:
   .e   T     #   enumerated map over T: lambda b (=element), k (=index):
     -bk      #     b-k
 *F           # multiply all together

Le filtre fonctionne comme ceci: si un élément est à sa place d'origine, (index-élément) sera 0 et le produit entier sera 0, et donc falsey.