Taniec wielu wymiarów

19

Wyzwanie

Biorąc pod uwagę n-wymiarową tablicę liczb całkowitych i permutację pierwszych nliczb naturalnych, odpowiednio permutuj wymiary tablicy.

Detale

To wyzwanie jest inspirowane MATLAB-ami permute. demonstracja Permutacja jest podana jako lista liczb całkowitych, np. [1,3,2]oznacza , że 1 zostaje zamapowane na 1, 2 zamapowane na 3, a 3 zamapowane na 2 (tutaj iwpis jest wartością izamapowaną na). Ale możesz używać innych formatów, które są wygodne, na przykład jako cykle lub jako funkcja. Jeśli jest to wygodniejsze, możesz także użyć indeksowania opartego na 0.

Można założyć, że tablica jest pełną „prostokątną” m1 x m2 x ... x mntablicą (tzn. Można założyć, że nie jest poszarpana / postrzępiona ).

Możesz założyć, że nnie jest on zbyt duży, ponieważ wiele języków ma ograniczenie liczby wymiarów w zagnieżdżonej tablicy.

Jeśli twój język nie obsługuje tablic wielowymiarowych, możesz również wziąć ciąg znaków reprezentujący tablicę jako dane wejściowe.

Przykłady

  • Każda n-wymiarowa tablica z permutacją tożsamości [1,2,3,...,n]pozostanie niezmieniona.
  • Tablica [[10,20,30],[40,50,60]]z permutacją [2,1]zostaje odwzorowana na [[10,40],[20,50],[30,60]].
  • Tablica [[[1,2],[3,4]],[[5,6],[7,8]]]z permutacją [2,3,1]zostaje odwzorowana na [[[1,3],[5,7]],[[2,4],[6,8]]].
code-golf array-manipulation permutations wada
źródło

Odpowiedzi:

9

Haskell , 168 bajtów

pjest funkcją (polimorficzną klasy typu) przyjmującą permutację jako listę Ints oraz zagnieżdżoną listę reprezentującą wielowymiarową tablicę Ints.

Wywołaj jako p [2,1] [[10,20,30],[40,50,60]], jednak jeśli domyślne ustawienie typu się nie powiedzie, może być konieczne dodanie adnotacji typu, takiej jak :: [[Int]](odpowiednio zagnieżdżona), podającej typ wyniku.

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]

Wypróbuj online!

Wyzwania w golfa z zagnieżdżonymi tablicami o dowolnej głębokości są w Haskell nieco niezręczne, ponieważ typowe pisanie staje się przeszkodą. Podczas gdy listy Haskell (z dokładnie taką samą składnią jak w opisie wyzwania) mogą być dobrze zagnieżdżone, listy o różnej głębokości zagnieżdżenia są niezgodnych typów. Ponadto standardowe funkcje parsowania Haskella wymagają znajomości typu wartości, którą próbujesz przeanalizować.

W rezultacie wydaje się nieuniknione, że program musi zawierać deklaracje związane z typem, które są stosunkowo szczegółowe. W części golfowej postanowiłem zdefiniować klasę typów P, która pmoże być polimorficzna w stosunku do typu tablicy.

Tymczasem uprząż testowa TIO pokazuje sposób na obejście problemu z analizą.

Jak to działa

  • Podsumowując istotę tego algorytmu: wykonuje sortowanie bąbelkowe na liście permutacji, transponując sąsiednie wymiary, gdy odpowiednie wskaźniki permutacji zostaną zamienione.

  • Jak podano w class P adeklaracji, w każdym przypadku pprzyjmuje dwa argumenty, permutację (zawsze typu [Int]) i tablicę.

  • Permutacja może być podana w formie w opisie wyzwania, chociaż sposób działania algorytmu, wybór wskaźników jest dowolny, z wyjątkiem ich względnej kolejności. (Więc działa zarówno na 0, jak i na 1).
  • Baza instance P Intobsługuje tablice wymiaru 1, który ppo prostu zwraca niezmieniony, ponieważ jeden wymiar można odwzorować tylko na siebie.
  • Drugi instance P a => P [a]jest definiowany rekurencyjnie, wywołując podarunki pwymiaru n , aby zdefiniować je dla tablic wymiaru n + 1 .
    • p(x:r)mpierwsze wywołuje p rrekurencyjnie dla każdego elementu m, dając tablicę wyników, nw której wszystkie wymiary oprócz pierwszego zostały poprawnie permutowane względem siebie.
    • Pozostałą permutację, którą należy wykonać, npodaje x:y:z = x:sort r.
    • Jeśli x<ywtedy pierwszy wymiar njest już poprawnie umieszczony i npo prostu jest zwracany.
    • Jeśli x>y, to pierwszy i drugi wymiar npotrzeby muszą zostać zamienione, co odbywa się za pomocą transposefunkcji. Na koniec p(x:z)stosuje się rekurencyjnie do każdego elementu wyniku, zapewniając przeniesienie pierwotnego pierwszego wymiaru do właściwej pozycji.
Ørjan Johansen
źródło
3

Python 2 , 312 bajtów

Wykorzystuje to indeksowanie 0 do permutacji

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

Wypróbuj online!

-2 bajty dzięki @Jonathan Frech.

fireflame241
źródło
Nie potrzebujesz nawiasów do wywołania exec (oszczędzając dwa bajty) , ponieważ jest to instrukcja w Pythonie 2.
Jonathan Frech
Istnieje również zbyteczna przestrzeń w z(p) for.
Jonathan Frech
1
Używane map(z,l), s%ja printdla 301 bajtów - Spróbuj online!
Pan Xcoder,
3

Python 2 , 41 25 bajtów

import numpy
numpy.einsum

Wypróbuj online!

Wektor permutacji ppodano jako ciąg liter. [2,3,1]Można więc podać jako 'bca'.

Dzięki @EriktheOutgolfer zapisano 16 bajtów!

rahnema1
źródło
Czy obsługuje to więcej niż 26 wymiarów?
Erik the Outgolfer
W rzeczywistości nie więcej niż 52 wymiary: wielkie litery + małe litery.
rahnema1
2

JavaScript (ES6), 136 132 bajtów

(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-indeksowane. Objaśnienie: grekurencyjnie iteruje tablicę, atworząc tablicę vindeksów uporządkowanych za pomocą permutacji p. Po pwyczerpaniu, hrekurencyjnie wstawia element do tablicy wyników rza pomocą permutowanych indeksów.

Neil
źródło