Ein Tanz in vielen Dimensionen

19

Herausforderung

Bei einem neindimensionalen Array von ganzen Zahlen und einer Permutation der ersten nnatürlichen Zahlen permutieren Sie die Array-Dimensionen entsprechend.

Einzelheiten

Diese Herausforderung ist von MATLABs inspiriert permute. demonstration Die Permutation wird als eine Liste von Ganzzahlen angegeben, z. B. [1,3,2]Mittel 1 wird auf 1, 2 auf 3 und 3 auf 2 abgebildet (hier ist der idritte Eintrag der Wert, auf den iabgebildet wird). Sie können jedoch auch andere geeignete Formate verwenden, z. B. als Zyklen oder als Funktion. Wenn es bequemer ist, können Sie auch die 0-basierte Indizierung verwenden.

Man kann davon ausgehen, dass es sich bei dem Array um ein vollständiges "rechteckiges" m1 x m2 x ... x mnArray handelt (dh Sie können davon ausgehen, dass es nicht zackig ist ).

Sie können davon ausgehen, dass dies nnicht zu groß ist, da in vielen Sprachen die Anzahl der Dimensionen in einem verschachtelten Array begrenzt ist.

Wenn Ihre Sprache keine mehrdimensionalen Arrays unterstützt, können Sie auch eine Zeichenfolge verwenden, die das Array als Eingabe darstellt.

Beispiele

  • Jedes neindimensionale Array mit der Identitätspermutation [1,2,3,...,n]bleibt unverändert.
  • Das Array [[10,20,30],[40,50,60]]mit der Permutation [2,1]wird zugeordnet [[10,40],[20,50],[30,60]].
  • Das Array [[[1,2],[3,4]],[[5,6],[7,8]]]mit der Permutation [2,3,1]wird zugeordnet [[[1,3],[5,7]],[[2,4],[6,8]]].
code-golf array-manipulation permutations fehlerhaft
quelle

Antworten:

9

Haskell , 168 Bytes

pist eine (typklassenpolymorphe) Funktion, die eine Permutation als Liste von Ints und eine verschachtelte Liste als mehrdimensionales Array von Ints verwendet.

Rufen Sie als auf p [2,1] [[10,20,30],[40,50,60]]. Wenn jedoch die Standardeinstellung des Typs nicht erfolgreich ist, müssen Sie möglicherweise eine Typanmerkung wie :: [[Int]](entsprechend verschachtelt) hinzufügen , die den Typ des Ergebnisses angibt.

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]

Probieren Sie es online!

Golf-Herausforderungen mit verschachtelten Arrays beliebiger Tiefe sind in Haskell etwas umständlich, da die statische Typisierung eher stört. Während Haskell-Listen (mit genau der gleichen Syntax wie in der Challenge-Beschreibung) problemlos verschachtelt werden können, sind Listen mit unterschiedlicher Verschachtelungstiefe nicht kompatibel. Für Standard-Parsingfunktionen von Haskell ist es außerdem erforderlich, den Typ des zu analysierenden Werts zu kennen.

Infolgedessen scheint es unvermeidlich, dass das Programm typbezogene Erklärungen enthalten muss, die relativ ausführlich sind. Für den Golf-Teil habe ich mich darauf festgelegt, eine Typklasse zu definieren P, pdie über den Typ des Arrays polymorph sein kann.

In der Zwischenzeit zeigt das Test-Gurtzeug des TIO einen Weg, um das Parsing-Problem zu umgehen.

Wie es funktioniert

  • Um das Wesentliche dieses Algorithmus zusammenzufassen: Er führt eine Blasensortierung für die Permutationsliste durch und transponiert benachbarte Dimensionen, wenn die entsprechenden Permutationsindizes vertauscht werden.

  • Wie in der class P aDeklaration angegeben, werden in jedem Fall pzwei Argumente verwendet, eine Permutation (immer vom Typ [Int]) und ein Array.

  • Die Permutation kann in der Form in der Herausforderungsbeschreibung angegeben werden, obwohl die Art und Weise, wie der Algorithmus arbeitet, die Auswahl der Indizes bis auf ihre relative Reihenfolge willkürlich ist. (Also sowohl 0- als auch 1-basierte Arbeit.)
  • Die Basis instance P Intbehandelt Arrays der Dimension 1, die peinfach unverändert zurückgegeben werden, da die eine Dimension nur auf sich selbst abgebildet werden kann.
  • Die andere instance P a => P [a]ist rekursiv definiert und ruft pmit Dimension n Subarrays auf, um sie für Dimension n + 1 Arrays zu definieren .
    • p(x:r)mfirst ruft p rrekursiv jedes Element von auf mund gibt ein Ergebnisfeld an, nin dem alle Dimensionen mit Ausnahme der ersten relativ zueinander korrekt permutiert wurden.
    • Die verbleibende Permutation, die durchgeführt werden muss, nist gegeben durch x:y:z = x:sort r.
    • Wenn dies x<yder Fall nist, nist die erste Dimension von bereits korrekt platziert und wird einfach zurückgegeben.
    • Wenn ja x>y, dann müssen die erste und zweite Dimension ngetauscht werden, was mit der transposeFunktion erledigt wird . Schließlich p(x:z)wird rekursiv auf jedes Element des Ergebnisses angewendet, um sicherzustellen, dass die ursprüngliche erste Dimension an die richtige Position verschoben wird.
Ørjan Johansen
quelle
3

Python 2 , 312 Bytes

Dies verwendet die 0-Indizierung für die Permutation

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

Probieren Sie es online!

-2 Bytes dank @Jonathan Frech.

fireflame241
quelle
Sie brauchen keine Klammern zum Aufrufen exec (zwei Bytes sparen) , da es sich um eine Anweisung in Python 2 handelt.
Jonathan Frech
Es gibt auch einen überflüssigen Raum in z(p) for.
Jonathan Frech
1
Gebraucht map(z,l), s%jund printfür 301 Bytes –– Probieren Sie es online!
Mr. Xcoder
3

Python 2 , 41 25 Bytes

import numpy
numpy.einsum

Probieren Sie es online!

Der Permutationsvektor pwird als Buchstabenfolge angegeben. So [2,3,1]kann als gegeben werden 'bca'.

Dank @EriktheOutgolfer 16 Bytes gespart!

rahnema1
quelle
Unterstützt dies mehr als 26 Dimensionen?
Erik der Outgolfer
Eigentlich nicht mehr als 52 Dimensionen: Großbuchstaben + Kleinbuchstaben.
Rahnema1
2

JavaScript (ES6), 136 132 Bytes

(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

0-indiziert. Erläuterung: gDurchläuft das Array rekursiv aund erstellt ein Array vvon Indizes, deren Reihenfolge mithilfe der Permutation geändert wurde p. Ist Once perschöpft, wird hdas Element unter rVerwendung der permutierten Indizes rekursiv in das Ergebnis-Array eingefügt.

Neil
quelle