Hitung Pengelompokan

17

Diberikan bilangan bulat positif n menghasilkan semua kekacauan dari n objek.

Detail

  • Gangguan adalah permutasi tanpa titik tetap. (Ini berarti di setiap nomor gangguan i tidak bisa berada di entri ke- i ).
  • Outputnya harus terdiri dari derangemen angka (1,2,,n) (atau sebagai alternatif (0,1,2,,n1) ).
  • Anda juga dapat selalu mencetak derangements (n,n1,,1) (atau (n1,n2,,1,0) masing-masing) tetapi Anda harus menentukannya.
  • Keluaran harus bersifat deterministik, yaitu setiap kali program dipanggil dengan beberapa n diberikan sebagai input, keluarannya harus sama (yang mencakup urutan deregemen harus tetap sama), dan keluaran lengkap harus dilakukan dalam jumlah waktu yang terbatas setiap kali (tidak cukup untuk melakukannya dengan probabilitas 1).
  • Anda dapat mengasumsikan bahwa n2
  • Untuk beberapa yang diberikan n Anda dapat menghasilkan semua kekacauan atau sebagai alternatif Anda dapat mengambil bilangan bulat k yang berfungsi sebagai indeks dan mencetak kekacauan ke- k (dalam urutan yang Anda pilih).

Contohnya

Perhatikan bahwa urutan gangguan tidak harus sama dengan yang tercantum di sini:

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 menghitung jumlah kekacauan.

cacat
sumber
Bisakah kita mengirimkan generator?
Melegalkan
@Fatalize Ya saya pikir ini akan cukup mirip dengan dua metode lain yang disebutkan (atau apakah Anda pikir ada argumen yang kuat menentangnya?).
flawr
1
@Fatalize Sebenarnya sepertinya mengembalikan generator alih-alih daftar dimungkinkan secara default.
flawr

Jawaban:

7

Jelly , 6 byte

Œ!=ÐṂR

Tautan monadik yang menerima bilangan bulat positif yang menghasilkan daftar daftar bilangan bulat.

Cobalah online!

Bagaimana?

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

Brachylog , 9 byte

⟦kpiᶠ≠ᵐhᵐ

Cobalah online!

Ini adalah generator yang menghasilkan satu gangguan yang [0, …, n-1]diberikan n.

Jika kita membungkusnya dengan ᶠ - findallmetapredicate, kita mendapatkan semua generasi yang mungkin dari kekacauan oleh generator.

Penjelasan

⟦           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
Fatalisasi
sumber
5

JavaScript (V8) , 85 byte

Fungsi rekursif mencetak semua gangguan berbasis 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)

Cobalah online!

Berkomentar

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
sumber
4

Ruby , 55 byte

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

Cobalah online!

Menghasilkan semua gangguan berbasis 0

Kirill L.
sumber
2

05AB1E , 9 byte

Lœʒāø€Ë_P

Cobalah online!

Penjelasan

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
sumber
2

Japt , 8 byte

Berbasis 0

o á fÈe¦

Cobalah (Footer menambah semua elemen untuk perbandingan yang lebih mudah dengan test case)

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
Shaggy
sumber
2

Python 2 , 102 byte

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

Cobalah online!

Pengindeksan berbasis 0, daftar tupel.

itertoolsSolusi non- berbasis:

Python 2 , 107 byte

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

Cobalah online!

Pengindeksan berbasis 0, daftar baris, program lengkap.

Catatan: Solusi ini, meskipun tidak mengimpor itertoolsperpustakaan, tidak lebih lama dari yang lain yang mengimpornya, karena sebagian besar dari jumlah besar di sini adalah membangun permutasi. Pemeriksaan kekacauan benar-benar sekitar 7 byte tambahan! Alasannya adalah bahwa pemeriksaan dilakukan dengan cepat sebagai bagian dari pembangunan setiap permutasi. Ini tidak benar untuk solusi lain, di mana Anda harus memeriksa apakah setiap permutasi yang dikembalikan oleh itertools.permutationsfungsi sebenarnya adalah kekacauan, dan, tentu saja, pemetaan itu sendiri membutuhkan banyak byte.

Erik the Outgolfer
sumber
2

MATL , 11 byte

:tY@tb-!AY)

Ini menghasilkan semua gangguan dalam urutan leksikografis.

Cobalah online!

Penjelasan dengan contoh

Pertimbangkan input 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
sumber
2

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

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

Cobalah online!

Xcali
sumber
1

Gaia , 10 byte

┅f⟨:ċ=†ỵ⟩⁇

Cobalah 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
sumber
1

J , 26 byte

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

Cobalah 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
Jonah
sumber
1

R , 81 80 byte

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

Cobalah online!

Mengembalikan yang listberisi semua gangguan. Sangat tidak efisien, seperti yang dihasilkannya(n2n)nilai yang mungkin sebagai nkombinasi ukuran dari [1..n]pengulangan nkali, kemudian filter untuk permutasi 1:n%in%xdan gangguan 1:n-x,.

R + gtools , 62 byte

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

Cobalah online!

Jauh lebih efisien, mengembalikan di matrixmana setiap baris adalah kekacauan.

Giuseppe
sumber
1

C ++ (gcc) , 207 196 byte

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

Cobalah online!

movatica
sumber
Anda dapat melakukan jauh lebih baik jika Anda menggunakan parameter output, terutama jika itu adalah std :: array sehingga ukurannya sebelumnya - 145 byte
Roman Odaisky
@RomanOdaisky: ide bagus, tapi bagaimana saya memahami aturan kode golf, Anda harus mengambil kode pra-alokasi ke dalam jumlah byte Anda.
movatica
@movatica Area abu-abu, saya pikir kode ini lebih mungkin valid daripada tidak valid. Dengan senang hati akan menulis hasil yang benar di suatu tempat, dan itu adalah tanggung jawab penelepon untuk membaca hasilnya. Perhatikan bahwa algoritma STL seperti std::copyjuga mempercayakan pemanggil dengan memberikan ruang yang memadai untuk output.
Roman Odaisky
@RomanOdaisky: Perilaku STL memang argumen yang valid.
movatica
0

C ++ (gcc) , 133 byte

Saya pikir ini telah tumbuh cukup berbeda dari pengajuan lainnya untuk mendapat jawaban yang terpisah. Akhirnya digunakan untuk index[array]sintaks luar-dalam!

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

Cobalah online!

Roman Odaisky
sumber
0

Haskell, 76 byte

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

Python 2 , 82 byte

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

Cobalah online!

88 byte sebagai program:

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

Cobalah online!

93 byte menggunakan itertools:

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

Cobalah online!

Tidak
sumber
0

Perl 6 , 49 37 byte

Sunting: Setelah beberapa bolak-balik dengan Phil H, kami telah dipangkas menjadi hanya 37 byte:

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

Cobalah online!

Dengan menggunakan Whateverdi awal, kita dapat menghindari tanda kurung (menyimpan 2 karakter). Selanjutnya gunakan Zmetaoperator -yang mengambil setiap elemen permutasi (misalnya 2,3,1) dan mengurangi 0,1,2 secara berurutan. Jika salah satu dari mereka adalah 0 (salah) maka semua persimpangan gagal.


Solusi asli tadinya ( Coba online! )

{permutations($_).grep:{none (for $_ {$++==$_})}}
pengguna0721090601
sumber
1
Awal yang baik, Anda dapat membuat filter lebih pendek dengan Z on! = Untuk -7 byte: tio.run/##K0gtyjH7n1upoJamYKvwv7ogtSi3tCSxJDM/…
Phil H
@ Philip Saya tahu harus ada cara untuk mengintegrasikan operator zip tapi saya tidak bisa mengetahuinya. Bagus
user0721090601
PhilH menggunakan strategi itu, masih dapat mengetuk 3 lainnya dengan membunuh tanda kurung: tio.run/##K0gtyjH7n1upoJamYKvwv7ogtSi3tCSxJDM/…
user0721090601
PhilH yang terakhir tidak berfungsi. Untuk semua kecuali n = 2 lebih dari satu elemen akan ditolak
user0721090601
Tentu saja, lupa persyaratannya ... dihapus
Phil H
0

Arang , 44 28 byte

dicoret 44 masih teratur 44

NθIΦEXθθEθ﹪÷ιXθλθ⬤ι‹⁼μλ⁼¹№ιλ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Secara longgar didasarkan pada jawaban non-itertools @ EricTheOutgolfer. Penjelasan:

Nθ                              Input `n`
     Xθθ                        `n` raised to power `n`
    E                           Mapped over implicit range
         θ                      `n`
        E                       Mapped over implicit range
            ι                   Outer loop index
           ÷                    Integer divided by
             Xθ                 `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
  I                             Cast to string
                                Implicitly print
Neil
sumber
0

C (gcc) , 187 180 byte

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

Cobalah online!

Jonathan Frech
sumber
@ceilingcat Terima kasih.
Jonathan Frech
0

Pyth , 12 byte

f*F.e-bkT.PU

Cobalah 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

Filter bekerja seperti ini: jika ada elemen di tempat aslinya, (elemen-indeks) akan menjadi 0 dan seluruh produk akan menjadi 0, dan dengan demikian falsey.

ar4093
sumber