Dado un número entero positivo, $n$ genera todos los trastornos de $n$ objetos.

Detalles

• Un trastorno es una permutación sin punto fijo. (Esto significa, en todos los números de desarreglo no pueden estar en el entrada-ésimo).$i$$i$
• La salida debe consistir en alteraciones de los números (o alternativamente ).$(1,2,\ldots,n)$$(0,1,2,\ldots,n-1)$
• Alternativamente, siempre puede imprimir alteraciones de (o respectivamente) pero debe especificarlo.$(n,n-1,\ldots,1)$$(n-1,n-2,\ldots,1,0)$
• La salida tiene que ser determinista, es decir, cada vez que se llama al programa con alguna dada como entrada, la salida debe ser la misma (lo que incluye que el orden de los trastornos debe permanecer igual), y la salida completa debe hacerse dentro de una cantidad de tiempo finita cada vez (no es suficiente hacerlo con probabilidad 1).$n$
• Puede suponer que$n \geqslant 2$
• Para algunos $n$ dados , puede generar todos los trastornos o, alternativamente, puede tomar otro número entero $k$ que sirva como índice e imprimir el $k$ -ésimo trastorno (en el orden que elija).

Ejemplos

Tenga en cuenta que el orden de los trastornos no tiene que ser el mismo que se enumera aquí:

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 cuenta el número de trastornos.

Jalea , 6 bytes

Œ!=ÐṂR

Un enlace monádico que acepta un entero positivo que produce una lista de listas de enteros.

Pruébalo en línea!

¿Cómo?

Œ!=ÐṂ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 bytes

⟦kpiᶠ≠ᵐhᵐ

Pruébalo en línea!

Este es un generador que genera un trastorno de [0, …, n-1]dado n.

Si lo ᶠ - findallenvolvemos en un metapredicado, obtenemos todas las generaciones posibles de trastornos por el generador.

Explicación

⟦           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 bytes

Una función recursiva que imprime todas las alteraciones basadas en 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)

Pruébalo en línea!

Comentado

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 bytes

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

Pruébalo en línea!

Genera todos los trastornos basados ​​en 0

05AB1E , 9 bytes

Lœʒāø€Ë_P

Pruébalo en línea!

Explicación

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 bytes

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

Pruébalo en línea!

Japt , 8 bytes

Basado en 0

o á fÈe¦

Pruébelo (el pie de página incrementa todos los elementos para facilitar la comparación con los casos de prueba)

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 bytes

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

Pruébalo en línea!

Indización basada en 0, lista de tuplas.

itertoolsSolución no basada:

Python 2 , 107 bytes

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

Pruébalo en línea!

Indización basada en 0, líneas de listas, programa completo.

Nota: Esta solución, a pesar de que no importa la itertoolsbiblioteca, no es mucho más larga que la otra que sí la importa, porque la mayor parte del volumen aquí está construyendo las permutaciones. ¡La verificación de desorden es realmente de unos 7 bytes adicionales! La razón es que la verificación se realiza sobre la marcha como parte de la construcción de cada permutación. Esto no es cierto para la otra solución, donde debe verificar si cada permutación devuelta por la itertools.permutationsfunción es de hecho un trastorno, y, por supuesto, la asignación en sí misma toma muchos bytes.

MATL , 11 bytes

:tY@tb-!AY)

Esto genera todos los trastornos en orden lexicográfico.

Pruébalo en línea!

Explicación con ejemplo

Considere la entrada 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 bytes

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

Pruébalo en línea!

Haskell , 58 bytes

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

Pruébalo en línea!

60 bytes

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

Pruébalo en línea!

Gaia , 10 bytes

┅f⟨:ċ=†ỵ⟩⁇

Pruébalo en línea!

┅		| 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 bytes

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

Pruébalo en línea!

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 bytes

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

Pruébalo en línea!

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

R + gtools , 62 bytes

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

Pruébalo en línea!

Mucho más eficiente, devuelve un matrixdonde cada fila es un trastorno.

Python 3.8 (prelanzamiento) , 96 bytes

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)

Pruébalo en línea!

C ++ (gcc) , 207 196 bytes

-5 bytes por ceilingcat -6 bytes por 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;}

Pruébalo en línea!

C ++ (gcc) , 133 bytes

Creo que esto ha crecido lo suficientemente diferente de la otra presentación como para merecer una respuesta por separado. ¡Finalmente un uso para index[array]la sintaxis de adentro hacia afuera!

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

Pruébalo en línea!

Haskell, 76 bytes

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

Python 2 , 82 bytes

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

Pruébalo en línea!

88 bytes como programa:

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

Pruébalo en línea!

93 bytes usando itertools:

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

Pruébalo en línea!

Perl 6 , 49 37 bytes

Editar: después de un poco de ida y vuelta con Phil H, lo hemos reducido a solo 37 bytes:

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

Pruébalo en línea!

Al usar el Whateveral principio, podemos evitar los corchetes (ahorra 2 caracteres). A continuación, utilice un Zmetaoperador con el -que toma cada elemento de una permutación (por ejemplo, 2,3,1) y resta 0,1,2 en orden. Si alguno de ellos es 0 (falso), la unión completa falla.

La solución original era (¡ Pruébelo en línea! )

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

Carbón , 44 28 bytes

tachado 44 sigue siendo regular 44

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

Pruébalo en línea! El enlace es a la versión detallada del código. Basada en la respuesta no itertools de @ EricTheOutgolfer. Explicación:

Ｎθ                              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) , 187 180 bytes

• Guardado siete bytes gracias a ceilingcat .

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

Pruébalo en línea!

Pyth , 12 bytes

f*F.e-bkT.PU

Pruébalo en línea!

           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

El filtro funciona así: si algún elemento está en su lugar original, (element-index) será 0 y todo el producto será 0, y por lo tanto falsey.