Tarian Banyak Dimensi

19

Tantangan

Diberikan narray -dimensi dari bilangan bulat dan permutasi dari nbilangan asli pertama , permutasi dimensi array sesuai.

Detail

Tantangan ini terinspirasi oleh MATLABs permute. Demonstrasi Permutasi diberikan sebagai daftar bilangan bulat, mis. [1,3,2]berarti 1 dipetakan ke 1, 2 dipetakan menjadi 3 dan 3 dipetakan ke 2 (di sini ientri adalah nilai idipetakan ke). Tetapi Anda dapat menggunakan format lain yang nyaman, misalnya sebagai siklus atau sebagai fungsi. Jika lebih nyaman, Anda juga dapat menggunakan pengindeksan berbasis 0.

Array dapat diasumsikan sebagai m1 x m2 x ... x mn-array "persegi panjang" penuh (yaitu Anda dapat menganggap itu tidak compang - camping / bergerigi ).

Anda dapat menganggap itu ntidak terlalu besar, karena banyak bahasa memiliki batasan jumlah dimensi dalam array bersarang.

Jika bahasa Anda tidak mendukung array multidimensi, Anda juga dapat mengambil string yang mewakili array sebagai input.

Contohnya

  • Setiap narray yang berdimensi dengan permutasi identitas [1,2,3,...,n]akan berubah.
  • Array [[10,20,30],[40,50,60]]dengan permutasi [2,1]dipetakan ke [[10,40],[20,50],[30,60]].
  • Array [[[1,2],[3,4]],[[5,6],[7,8]]]dengan permutasi [2,3,1]dipetakan ke [[[1,3],[5,7]],[[2,4],[6,8]]].
code-golf array-manipulation permutations cacat
sumber

Jawaban:

9

Haskell , 168 byte

padalah (tipe kelas polimorfik) fungsi mengambil permutasi sebagai daftar Ints, dan daftar bersarang mewakili array multidimensi Ints.

Sebutlah sebagai p [2,1] [[10,20,30],[40,50,60]], namun jika jenis default tidak berhasil, Anda mungkin harus menambahkan anotasi jenis seperti :: [[Int]](bersarang dengan tepat) memberikan jenis hasil.

import Data.List
class P a where p::[Int]->[a]->[a]
instance P Int where p _=id
instance P a=>P[a]where p(x:r)m|n<-p r<$>m,y:z<-sort r=last$n:[p(x:z)<$>transpose n|x>y]

Cobalah online!

Tantangan bermain golf dengan array bersarang dari kedalaman arbitrer agak canggung di Haskell, karena pengetikan statis cenderung menghalangi. Sementara daftar Haskell (dengan sintaks yang sama persis seperti pada deskripsi tantangan) dapat disarangkan dengan baik, daftar kedalaman bersarang yang berbeda adalah jenis yang tidak kompatibel. Selain itu, fungsi parsing Haskell standar memerlukan mengetahui jenis nilai yang Anda coba parsing.

Akibatnya, tampaknya tak terhindarkan bahwa program perlu menyertakan deklarasi terkait tipe, yang relatif bertele-tele. Untuk bagian golf, saya memutuskan untuk mendefinisikan kelas tipe P, sehingga pbisa polimorfik atas jenis array.

Sementara itu, harness pengujian TIO menunjukkan cara untuk mengatasi masalah parsing.

Bagaimana itu bekerja

  • Untuk meringkas inti dari algoritma ini: Ia melakukan semacam gelembung pada daftar permutasi, mentransposisi dimensi tetangga ketika indeks permutasi yang sesuai bertukar.

  • Seperti yang diberikan oleh class P adeklarasi, dalam setiap contoh, pmembutuhkan dua argumen, permutasi (selalu bertipe [Int]) dan array.

  • Permutasi dapat diberikan dalam bentuk dalam deskripsi tantangan, meskipun cara algoritme bekerja, pemilihan indeks bersifat arbitrer, kecuali untuk urutan relatifnya. (Jadi pekerjaan berbasis 0- dan 1-.)
  • Basis instance P Intmenangani array dimensi 1, yang phanya mengembalikan tidak berubah, karena satu dimensi hanya dapat dipetakan ke dirinya sendiri.
  • Yang lain instance P a => P [a]didefinisikan secara rekursif, memanggil pdengan dimensi dan sub- array untuk mendefinisikannya untuk dimensi dan array 1 .
    • p(x:r)mpanggilan pertama p rsecara rekursif pada setiap elemen m, memberikan array hasil ndi mana semua dimensi kecuali yang pertama telah diijinkan dengan benar relatif satu sama lain.
    • Permutasi yang tersisa yang perlu dilakukan ndiberikan oleh x:y:z = x:sort r.
    • Jika x<ykemudian dimensi pertama nsudah ditempatkan dengan benar, dan nhanya dikembalikan.
    • Jika x>y, maka dimensi pertama dan kedua nperlu ditukar, yang dilakukan dengan transposefungsi. Akhirnya p(x:z)diterapkan secara rekursif untuk setiap elemen hasil, memastikan dimensi pertama asli ditransformasikan ke posisi yang tepat.
Ørjan Johansen
sumber
3

Python 2 , 312 byte

Ini menggunakan pengindeksan 0 untuk permutasi

from numpy import*
from itertools import*
z=range
def f(i,r):
	l=array(i).shape;R={b:a for a,b in enumerate(r)};r=len(r);m=eval('['*r+'0'+q('for k in z(l[R[%s]])]',r-1,-1,-1))
	for d in product(*[z(p) for p in l]):exec'm'+q('[d[R[%s]]]',r)+'=i'+q('[d[%s]]',r)
	return m
q=lambda s,*j:''.join(s%(j)for j in z(*j))

Cobalah online!

-2 byte terima kasih kepada @Jonathan Frech.

fireflame241
sumber
Anda tidak perlu tanda kurung untuk memanggil exec (menyimpan dua byte) , karena ini adalah pernyataan dengan Python 2.
Jonathan Frech
Ada juga ruang berlebihan di z(p) for.
Jonathan Frech
1
Digunakan map(z,l), s%jdan printuntuk 301 byte –– Cobalah online!
Tn. Xcoder
3

Python 2 , 41 25 byte

import numpy
numpy.einsum

Cobalah online!

Vektor permutasi pdiberikan sebagai string huruf. Jadi [2,3,1]bisa diberikan sebagai 'bca'.

Berkat @EriktheOutgolfer menghemat 16 byte!

rahnema1
sumber
Apakah ini mendukung lebih dari 26 dimensi?
Erik the Outgolfer
Sebenarnya tidak lebih dari 52 dimensi: huruf besar + huruf kecil.
rahnema1
2

JavaScript (ES6), 136 132 byte

(a,p,v=[],r=[],g=(a,[d,...p],_,h=(r,[i,...v])=>1/v[0]?h(r[i]=r[i]||[],v):r[i]=a)=>1/d?a.map((e,i)=>g(e,p,v[d]=i)):h(r,v))=>g(a,p)&&r

Diindeks 0. Penjelasan: gberulang secara berulang di atas array amembangun array vindeks disusun kembali menggunakan permutasi p. Setelah phabis, hmaka secara rekursif memasukkan elemen ke dalam array hasil rmenggunakan indeks yang diijinkan.

Neil
sumber