Учитывая некоторое положительное целое число $n$ генерируют все нарушения $n$ объектов.

Детали

• Нарушение - это перестановка без фиксированной точки. (Это означает, что в каждом номере расстройства не могу быть в записи).$i$$i$
• Вывод должен состоять из отклонений чисел (или альтернативно ).$(1,2,\ldots,n)$$(0,1,2,\ldots,n-1)$
• Вы можете альтернативно всегда печатать из расстройств (или ( п - 1 , п - 2 , ... , 1 , 0 ) , соответственно) , но вы должны указать так.$(n,n-1,\ldots,1)$$(n-1,n-2,\ldots,1,0)$
• Выходные данные должны быть детерминированными, то есть всякий раз, когда программа вызывается с некоторым заданным $n$ качестве входных данных, выходные данные должны быть одинаковыми (что подразумевает, что порядок неисправностей должен оставаться неизменным), и полный вывод должен быть выполнен в течение ограниченное количество времени каждый раз (этого недостаточно для вероятности 1).
• $n \geqslant 2$
• Для некоторого заданного вы можете сгенерировать все отклонения или, альтернативно, вы можете взять другое целое число которое служит индексом, и вывести отклонение (в выбранном вами порядке).$n$$k$$k$

Примеры

Обратите внимание, что порядок неисправностей не должен быть таким, как указано здесь:

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 подсчитывает количество неисправностей.

Желе , 6 байт

Œ!=ÐṂR

Монадическая ссылка, принимающая положительное целое число, которое выдает список списков целых чисел.

Попробуйте онлайн!

Как?

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

Брахилог , 9 байт

⟦kpiᶠ≠ᵐhᵐ

Попробуйте онлайн!

Это генератор, который выводит одно расстройство [0, …, n-1] данных n.

Если мы завернем это в ᶠ - findall обернем метапредикат, мы получим все возможные поколения расстройств от генератора.

объяснение

⟦           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 байт

Рекурсивная функция, печатающая все неисправности на основе 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)

Попробуйте онлайн!

комментарии

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

Рубин , 55 байт

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

Попробуйте онлайн!

Генерирует все 0 основанные неисправности

05AB1E , 9 байтов

Lœʒāø€Ë_P

Попробуйте онлайн!

объяснение

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 байтов

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

Попробуйте онлайн!

Japt , 8 байт

0 на основе

o á fÈe¦

Попробуйте (нижний колонтитул увеличивает все элементы для упрощения сравнения с контрольными примерами)

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 байта

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

Попробуйте онлайн!

Индексирование на основе 0, список кортежей.

Non- itertoolsоснованное решение:

Python 2 , 107 байт

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

Попробуйте онлайн!

Индексирование на основе 0, строки списков, полная программа.

Примечание. Это решение, даже несмотря на то, что оно не импортирует itertoolsбиблиотеку, не намного дольше, чем другое, которое импортирует ее, потому что большая часть этого объема строит перестановки. Проверка неисправности действительно составляет около 7 дополнительных байтов! Причина в том, что проверка выполняется на лету как часть построения каждой перестановки. Это не верно для другого решения, где вы должны проверить, является ли каждая перестановка, возвращаемая itertools.permutationsфункцией, на самом деле отклонением, и, конечно, само отображение занимает много байтов.

MATL , 11 байт

:tY@tb-!AY)

Это создает все нарушения в лексикографическом порядке.

Попробуйте онлайн!

Пояснение с примером

Рассмотрим ввод 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 байт

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

Попробуйте онлайн!

Haskell , 58 байт

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

Попробуйте онлайн!

60 байт

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

Попробуйте онлайн!

Gaia , 10 байт

┅f⟨:ċ=†ỵ⟩⁇

Попробуйте онлайн!

┅		| 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 байт

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

Попробуйте онлайн!

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 байт

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

Попробуйте онлайн!

Возвращает listсодержащий все неисправности. Очень неэффективно, так как генерирует$n^2\choose n$Возможные значения в качестве размерно nкомбинаций [1..n]повторяющихся nраз, а затем фильтры для перестановок 1:n%in%xи расстройств, 1:n-x.

R + gtools , 62 байта

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

Попробуйте онлайн!

Гораздо эффективнее, возвращает matrixгде каждая строка является нарушением.

Python 3.8 (предварительная версия) , 96 байт

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)

Попробуйте онлайн!

C ++ (gcc) , 207 196 байт

-5 байт от потолочного кота -6 байт от Романа Одайского

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

Попробуйте онлайн!

C ++ (gcc) , 133 байта

Я думаю, что это достаточно сильно отличается от других представлений, чтобы заслужить отдельный ответ. Наконец, использование для index[array]синтаксиса наизнанку!

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

Попробуйте онлайн!

Haskell, 76 байт

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

Python 2 , 82 байта

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

Попробуйте онлайн!

88 байтов как программа:

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

Попробуйте онлайн!

93 байта, используя itertools:

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

Попробуйте онлайн!

Perl 6 , 49 37 байт

Изменить: После некоторого перемотки с Филом Н мы сократили его до 37 байт:

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

Попробуйте онлайн!

Используя Whateverв начале, мы можем избежать скобок (экономит 2 символа). Далее используйте Zметаоператор с- которого берется каждый элемент перестановки (например, 2,3,1) и вычитается 0,1,2 по порядку. Если какой-либо из них равен 0 (ложно), то весь переход не выполняется.

Оригинальное решение было ( Попробуйте онлайн! )

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

Древесный уголь , 44 28 байт

вычеркнул 44 все еще регулярно 44

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

Попробуйте онлайн! Ссылка на подробную версию кода. Свободно основанный на не-itertools @ EricTheOutgolfer ответ. Объяснение:

Ｎθ                              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 байт

• Сэкономлено семь байтов благодаря функциюcatcat .

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

Попробуйте онлайн!

Pyth , 12 байт

f*F.e-bkT.PU

Попробуйте онлайн!

           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

Фильтр работает следующим образом: если какой-либо элемент находится в исходном месте, (element-index) будет равен 0, а весь продукт будет равен 0, и, следовательно, будет ложным.