Uma dança de muitas dimensões

19

Desafio

Dada uma nmatriz dimensional de números inteiros e uma permutação dos primeiros nnúmeros naturais, permita as dimensões da matriz de acordo.

Detalhes

Esse desafio é inspirado no MATLABs permute. demonstração A permutação é fornecida como uma lista de números inteiros, por exemplo, o [1,3,2]meio 1 é mapeado para 1, 2 é mapeado para 3 e 3 é mapeado para 2 (aqui ié a entrada na qual o valor ié mapeado). Mas você pode usar outros formatos convenientes, por exemplo, como ciclos ou como uma função. Se for mais conveniente, você também pode usar a indexação baseada em 0.

A matriz pode ser assumida como uma matriz "retangular" m1 x m2 x ... x mncompleta (ou seja, você pode assumir que ela não é irregular / irregular ).

Você pode assumir que nnão é muito grande, pois muitos idiomas têm um limite do número de dimensões em uma matriz aninhada.

Se o seu idioma não suportar matrizes multidimensionais, você também poderá usar uma string que represente a matriz como entrada.

Exemplos

  • Qualquer nmatriz dimensional com a permutação de identidade [1,2,3,...,n]permanecerá inalterada.
  • A matriz [[10,20,30],[40,50,60]]com a permutação [2,1]é mapeada para [[10,40],[20,50],[30,60]].
  • A matriz [[[1,2],[3,4]],[[5,6],[7,8]]]com a permutação [2,3,1]é mapeada para [[[1,3],[5,7]],[[2,4],[6,8]]].
code-golf array-manipulation permutations flawr
fonte

Respostas:

9

Haskell , 168 bytes

pé uma função (classe polimórfica da classe) que recebe uma permutação como uma lista de Ints e uma lista aninhada que representa uma matriz multidimensional de Ints.

Chame como p [2,1] [[10,20,30],[40,50,60]], no entanto, se o padrão de digitação não for bem-sucedido, talvez você precise adicionar uma anotação de tipo como :: [[Int]](aninhada adequadamente) fornecendo o tipo do resultado.

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]

Experimente online!

Desafios no golfe com matrizes aninhadas de profundidade arbitrária são um pouco estranhos em Haskell, porque a digitação estática tende a atrapalhar. Embora as listas Haskell (com a mesma sintaxe exata da descrição do desafio) possam ser aninhadas muito bem, listas de diferentes profundidades de aninhamento são de tipos incompatíveis. Além disso, as funções de análise Haskell padrão requerem o conhecimento do tipo do valor que você está tentando analisar.

Como resultado, parece inevitável que o programa precise incluir declarações relacionadas ao tipo, que são relativamente detalhadas. Para a parte do golfe, decidi definir uma classe de tipo P, que ppode ser polimórfica sobre o tipo da matriz.

Enquanto isso, o equipamento de teste do TIO mostra uma maneira de contornar o problema de análise.

Como funciona

  • Para resumir a essência desse algoritmo: Ele realiza uma classificação de bolha na lista de permutações, transpondo as dimensões vizinhas quando os índices de permutação correspondentes são trocados.

  • Conforme fornecido pela class P adeclaração, em qualquer caso, são pnecessários dois argumentos, uma permutação (sempre do tipo [Int]) e uma matriz.

  • A permutação pode ser dada na forma na descrição do desafio, embora, da maneira como o algoritmo funcione, a escolha dos índices seja arbitrária, exceto por sua ordem relativa. (Portanto, o trabalho baseado em 0 e 1).
  • A base instance P Intlida com matrizes da dimensão 1, que psimplesmente retorna inalterada, pois a única dimensão só pode ser mapeada para si mesma.
  • A outra instance P a => P [a]é definida recursivamente, chamando pcom dimensão n subarrays de modo a defini-lo para a dimensão n + 1 matrizes.
    • p(x:r)mprimeiro chama p rrecursivamente todos os elementos de m, fornecendo uma matriz de resultados nna qual todas as dimensões, exceto a primeira, foram permutadas corretamente em relação uma à outra.
    • A permutação restante que precisa ser executada né dada por x:y:z = x:sort r.
    • Se, x<yentão, a primeira dimensão de njá estiver corretamente posicionada e nsimplesmente retornada.
    • Se x>y, então a primeira e a segunda dimensão de nprecisam ser trocadas, o que é feito com a transposefunção Finalmente, p(x:z)é aplicado recursivamente a todos os elementos do resultado, garantindo que a primeira dimensão original seja transposta para a posição correta.
Ørjan Johansen
fonte
3

Python 2 , 312 bytes

Utiliza indexação 0 para a permutação

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

Experimente online!

-2 bytes graças a @ Jonathan Frech.

fireflame241
fonte
Você não precisa de parênteses para chamar exec (economia de dois bytes) , como é uma declaração em Python 2.
Jonathan Frech
Também há um espaço supérfluo em z(p) for.
Jonathan Frech
11
Usado map(z,l), s%je printpara 301 bytes - Experimente online!
Sr. Xcoder
3

Python 2 , 41 25 bytes

import numpy
numpy.einsum

Experimente online!

O vetor de permutação pé dado como uma sequência de letras. Então [2,3,1]pode ser dado como 'bca'.

Graças a @EriktheOutgolfer salvou 16 bytes!

rahnema1
fonte
Isso suporta mais de 26 dimensões?
Erik the Outgolfer
Na verdade, não mais que 52 dimensões: maiúsculas + minúsculas.
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

Indexado a 0. Explicação: gitera recursivamente sobre a matriz, aconstruindo uma matriz vde índices reordenados usando a permutação p. Uma vez pesgotado, hinsira recursivamente o elemento na matriz de resultados rusando os índices permutados.

Neil
fonte