Aufzählen von Störungen

17

Wenn eine positive ganze Zahl n , werden alle Abweichungen von n Objekten erzeugt.

Einzelheiten

  • A derangement eine Permutation ohne Fixpunkt. (Dies bedeutet , in jeder Umnachtung Zahl i nicht in dem seine i - ten Eintrag).
  • Die Ausgabe sollte aus Abweichungen der Zahlen (1,2,…,n) (oder alternativ (0,1,2,…,n−1) ) bestehen.
  • Sie können alternativ immer Abweichungen von (n,n−1,…,1) (bzw. (n−1,n−2,…,1,0) ) drucken , müssen dies jedoch angeben.
  • Die Ausgabe muss deterministisch sein, dh wenn das Programm mit einem bestimmten n als Eingabe aufgerufen wird , sollte die Ausgabe dieselbe sein (was beinhaltet, dass die Reihenfolge der Abweichungen dieselbe bleiben muss) und die vollständige Ausgabe muss innerhalb von erfolgen jedes Mal eine endliche Menge an Zeit (es ist nicht ausreichend, dies mit Wahrscheinlichkeit 1 zu tun).
  • Sie können davon ausgehen, dass n⩾2
  • Für ein bestimmtes n Sie entweder alle Abweichungen generieren oder alternativ eine andere Ganzzahl als Index verwenden und die te Abweichung ausgeben (in der von Ihnen gewählten Reihenfolge).kk

Beispiele

Beachten Sie, dass die Reihenfolge der derangements nicht die gleiche sein muss wie hier aufgeführt:

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 zählt die Anzahl der Störungen.

code-golf math number array-manipulation permutations fehlerhaft
quelle
Können wir einen Generator einreichen?
Fatalize
@Fatalize Ja, ich denke, das wäre den beiden anderen genannten Methoden ähnlich genug (oder gibt es Ihrer Meinung nach ein starkes Argument dagegen?).
Fehler
1
@Fatalize Eigentlich scheint es möglich zu sein, einen Generator anstelle einer Liste zurückzugeben .
1.

Antworten:

7

Gelee , 6 Bytes

Œ!=ÐṂR

Ein monadischer Link, der eine positive Ganzzahl akzeptiert, die eine Liste von Ganzzahllisten liefert.

Probieren Sie es online!

Wie?

Œ!=ÐṂ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]
Jonathan Allan
quelle
5

Brachylog , 9 Bytes

⟦kpiᶠ≠ᵐhᵐ

Probieren Sie es online!

Dies ist ein Generator, der eine Störung von [0, …, n-1]gegebenem ausgibt n.

Wenn wir es in ein ᶠ - findallMetapredikat einwickeln, erhalten wir alle möglichen Generationen von Störungen durch den Generator.

Erläuterung

⟦           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
Tödlich
quelle
5

JavaScript (V8) , 85 Byte

Eine rekursive Funktion, die alle 0-basierten Abweichungen ausgibt.

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)

Probieren Sie es online!

Kommentiert

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
Arnauld
quelle
4

Ruby , 55 Bytes

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

Probieren Sie es online!

Erzeugt alle 0-basierten Abweichungen

Kirill L.
quelle
2

05AB1E , 9 Bytes

Lœʒāø€Ë_P

Probieren Sie es online!

Erläuterung

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
Emigna
quelle
2

Japt , 8 Bytes

0-basiert

o á fÈe¦

Probieren Sie es aus (Fußzeile erhöht alle Elemente, um den Vergleich mit den Testfällen zu erleichtern)

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
Zottelig
quelle
2

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*

Probieren Sie es online!

0-basierte Indizierung, Liste der Tupel.

Nichtbasierte itertoolsLösung:

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

Probieren Sie es online!

0-basierte Indizierung, Listenzeilen, volles Programm.

Hinweis: Diese Lösung ist, obwohl sie die itertoolsBibliothek nicht importiert , nicht viel länger als die andere, die sie importiert, da der Großteil der hier beschriebenen Lösung die Permutationen erstellt. Die Überprüfung der Störung ist wirklich ungefähr 7 zusätzliche Bytes! Der Grund ist, dass die Prüfung im laufenden Betrieb als Teil des Aufbaus jeder Permutation durchgeführt wird. Dies gilt nicht für die andere Lösung, bei der Sie überprüfen müssen, ob jede von der itertools.permutationsFunktion zurückgegebene Permutation tatsächlich eine Störung darstellt, und die Zuordnung selbst natürlich eine Menge Bytes benötigt.

Erik der Outgolfer
quelle
2

MATL , 11 Bytes

:tY@tb-!AY)

Dies erzeugt alle Störungen in lexikographischer Reihenfolge.

Probieren Sie es online!

Erklärung mit Beispiel

Betrachten Sie die Eingabe 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]
Luis Mendo
quelle
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

Probieren Sie es online!

Xcali
quelle
1

Gaia , 10 Bytes

┅f⟨:ċ=†ỵ⟩⁇

Probieren Sie es online!

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

J , 26 Bytes

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

Probieren Sie es online!

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
Jona
quelle
1

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

Probieren Sie es online!

Gibt ein zurück, listdas alle Abweichungen enthält. Sehr ineffizient, wie es erzeugt(n2n)mögliche Werte wie die größen- nKombinationen von [1..n]wiederholten nMal, dann filtert für Permutationen 1:n%in%xund Störungen, 1:n-x.

R + gtools , 62 Bytes

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

Probieren Sie es online!

Sehr viel effizienter, gibt eine zurück, matrixbei der jede Zeile eine Störung darstellt.

Giuseppe
quelle
1

C ++ (GCC) , 207 196 Bytes

-5 Bytes von ceilingcat -6 Bytes von 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;}

Probieren Sie es online!

movatica
quelle
Sie können viel bessere Ergebnisse erzielen, wenn Sie einen Ausgabeparameter verwenden, insbesondere, wenn es sich um ein std :: -Array handelt, das also eine Größe von 145 Byte hat
Roman Odaisky
@RomanOdaisky: Gute Idee, aber wie ich die Regeln des Codegolfs verstehe, müssen Sie den Vorbelegungscode in Ihre Byteanzahl aufnehmen.
movatica
@movatica Eine Grauzone, ich denke der Code ist eher gültig als ungültig. Die korrekten Ergebnisse werden gerne irgendwo geschrieben, und es liegt in der Verantwortung des Aufrufers, die Ausgabe zu lesen. Beachten Sie, dass STL-Algorithmen, wie sie std::copydem Aufrufer ebenfalls anvertrauen, ausreichend Platz für die Ausgabe zur Verfügung zu stellen.
Roman Odaisky
@ RomanOdaisky: STL-Verhalten ist in der Tat ein gültiges Argument.
Movatica
0

C ++ (gcc) , 133 Bytes

Ich denke, dies hat sich von der anderen Vorlage so stark verändert, dass es eine separate Antwort verdient. Endlich eine Verwendung für index[array]Inside-Out-Syntax!

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

Probieren Sie es online!

Roman Odaisky
quelle
0

Haskell, 76 Bytes

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

Perl 6 , 49 37 Bytes

Edit: Nach einigem Hin und Her mit Phil H haben wir es auf nur 37 Bytes reduziert:

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

Probieren Sie es online!

Durch die Verwendung von Whateveram Anfang können wir die Klammern vermeiden (spart 2 Zeichen). Verwenden Sie als Nächstes den ZMetaoperator, mit -dem jedes Element einer Permutation (z. B. 2,3,1) in der angegebenen Reihenfolge subtrahiert wird. Wenn einer von ihnen 0 (falsch) ist, schlägt die all-Junction fehl.

Ursprüngliche Lösung war ( Online ausprobieren! )

{permutations($_).grep:{none (for $_ {$++==$_})}}
user0721090601
quelle
1
Guter Anfang, Sie können den Filter kürzer machen, wenn Z aktiviert ist ! = Für -7 Bytes: tio.run/##K0gtyjH7n1upoJamYKvwv7ogtSi3tCSxJDM/…
Phil H
@PhilH Ich wusste, dass es eine Möglichkeit geben muss, den zip-Operator zu integrieren, aber ich konnte es nicht ganz herausfinden. nett
user0721090601
PhilH, der diese Strategie anwendet, kann noch weitere 3 durch Töten von Klammern schlagen : tio.run/##K0gtyjH7n1upoJamYKvwv7ogtSi3tCSxJDM/…
user0721090601
PhilH das letzte funktioniert nicht. Für alle außer n = 2 wird mehr als nur ein Element verworfen
user0721090601
Natürlich vergessen die Anforderung ... entfernt
Phil H
0

Holzkohle , 44 28 Bytes

durchgestrichen 44 ist immer noch regulär 44

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Lose basierend auf der Antwort von @ EricTheOutgolfers Nicht-Itertools. Erläuterung:

Ｎθ                              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
Neil
quelle
0

C (gcc) , 187-180 Bytes

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

Probieren Sie es online!

Jonathan Frech
quelle
@ceilingcat Vielen Dank.
Jonathan Frech
0

Pyth , 12 Bytes

f*F.e-bkT.PU

Probieren Sie es online!

           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

Der Filter funktioniert folgendermaßen: Wenn sich ein Element an seiner ursprünglichen Stelle befindet, ist (Element-Index) 0 und das gesamte Produkt ist 0 und daher falsch.

ar4093
quelle