Supongamos que tenemos una matriz de longitud con punteros que apuntan a alguna ubicación en la matriz: el proceso de " salto de puntero " establecerá cada puntero en la ubicación a la que apunta.$\texttt{ps}$$n$

Para el propósito de este desafío, un puntero es el índice (basado en cero) de un elemento de la matriz, esto implica que cada elemento de la matriz será mayor o igual a y menor que . Usando esta notación, el proceso puede formularse de la siguiente manera:$0$$n$

for i = 0..(n-1) {
  ps[i] = ps[ps[i]]
}

Esto significa (para este desafío) que los punteros se actualizan in situ en orden secuencial (es decir, primero los índices más bajos).

Ejemplo

Analicemos un ejemplo, :$\texttt{ps = [2,1,4,1,3,2]}$

$$\texttt{i = 0}: \text{the element at position }\texttt{ps[0] = 2}\text{ points to }\texttt{4} \\ \to \texttt{ps = [4,1,4,1,3,2]} \\ \texttt{i = 1}: \text{the element at position }\texttt{ps[1] = 1}\text{ points to }\texttt{1} \\ \to \texttt{ps = [4,1,4,1,3,2]} \\ \texttt{i = 2}: \text{the element at position }\texttt{ps[2] = 4}\text{ points to }\texttt{3} \\ \to \texttt{ps = [4,1,3,1,3,2]} \\ \texttt{i = 3}: \text{the element at position }\texttt{ps[3] = 1}\text{ points to }\texttt{1} \\ \to \texttt{ps = [4,1,3,1,3,2]} \\ \texttt{i = 4}: \text{the element at position }\texttt{ps[4] = 3}\text{ points to }\texttt{1} \\ \to \texttt{ps = [4,1,3,1,1,2]} \\ \texttt{i = 5}: \text{the element at position }\texttt{ps[5] = 2}\text{ points to }\texttt{3} \\ \to \texttt{ps = [4,1,3,1,1,3]}$$

Entonces, después de una iteración de " salto de puntero " obtenemos la matriz .$\texttt{[4,1,3,1,1,3]}$

Reto

Dada una matriz con salida de índices, la matriz obtenida iterando el puntero descrito anteriormente saltando hasta que la matriz ya no cambie.

Reglas

Su programa / función tomará y devolverá / generará el mismo tipo, una lista / vector / matriz, etc., que

• se garantiza que no está vacío y
• se garantiza que solo contiene entradas .$0 \leq p < n$

Variantes: puedes elegir

• utilizar indexación basada en 1 o
• usar punteros reales,

Sin embargo, debe mencionar esto en su presentación.

Casos de prueba

[0] → [0]
[1,0] → [0,0]
[1,2,3,4,0] → [2,2,2,2,2]
[0,1,1,1,0,3] → [0,1,1,1,0,1]
[4,1,3,0,3,2] → [3,1,3,3,3,3]
[5,1,2,0,4,5,6] → [5,1,2,5,4,5,6]
[9,9,9,2,5,4,4,5,8,1,0,0] → [1,1,1,1,4,4,4,4,8,1,1,1]

JavaScript, 36 bytes

Modifica la matriz de entrada original.

a=>a.map(_=>a.map((x,y)=>a[y]=a[x]))

Pruébalo en línea

Haskell, 56 bytes

foldr(\_->([]#))=<<id
x#a@(b:c)=(x++[(x++a)!!b])#c
x#_=x

Haskell y las actualizaciones en el lugar son una mala combinación.

Pruébalo en línea!

Python 2 , 53 bytes

def f(l):L=len(l);i=0;exec'l[i]=l[l[i]];i=-~i%L;'*L*L

Pruébalo en línea!

-6 gracias a HyperNeutrino .

Altera lel resultado en su lugar.

C ++ 14 (gcc) , 61 bytes

Como lambda genérico sin nombre. Requiere contenedores secuenciales como std::vector.

[](auto&c){auto d=c;do{d=c;for(auto&x:c)x=c[x];}while(d!=c);}

Pruébalo en línea!

Swift , 68 53 bytes

{a in for _ in a{var i=0;a.forEach{a[i]=a[$0];i+=1}}}

Pruébalo en línea!

-15 gracias a BMO

JavaScript (ES6), 41 bytes

f=a=>a+''==a.map((x,i)=>a[i]=a[x])?a:f(a)

Pruébalo en línea!

05AB1E (heredado) , 8 bytes

ΔDvDyèNǝ

Pruébalo en línea!

Explicación

Δ          # apply until the top of the stack stops changing
 D         # duplicate current list
  v        # for each (element y, index N) in the list
   Dyè     # get the element at index y
      Nǝ   # and insert it at index N

05AB1E , 14 bytes

[D©vDyèNǝ}D®Q#

Pruébalo en línea!

Japt, 15 13 7 bytes

Modifica la matriz de entrada original.

££hYXgU

Pruébelo (los bytes adicionales son para escribir la entrada modificada en la consola)

££hYXgU
£           :Map
 £          :  Map each X at index Y
  hY        :    Replace the element at index Y
    XgU     :    With the element at index X

Java 8, 105 54 bytes

a->{for(int l=a.length,i=0;i<l*l;)a[i%l]=a[a[i++%l]];}

Modifica la matriz de entrada en lugar de devolver una nueva para guardar bytes.

$length^2$

Pruébalo en línea.

Explicación:

a->{                // Method with integer-array parameter and no return-type
  int l=a.length,   //  Length of the input-array
  i=0;i<l*l;)       //  Loop `i` in the range [0, length squared):
    a[i%l]=         //   Set the (`i` modulo-length)'th item in the array to:
      a[            //    The `p`'th value of the input-array,
        a[i++%l]];} //    where `p` is the (`i` modulo-length)'th value of the array

Japt , 17 bytes

®
£hYUgX
eV ?U:ß

Pruebe todos los casos de prueba

Parece que debería ser más corto, pero desafortunadamente mi pensamiento inicial UmgUno funciona porque cada uno gaccede al original en Ulugar de modificarlo en cada paso. La preservación de diferentes componentes también cuesta un puñado de bytes.

Explicación:

           #Blank line preserves input in U long enough for the next line

®          #Copy U into V to preserve its original value

£hY        #Modify U in-place by replacing each element X with...
   UgX     #The value from the current U at the index X

eV ?U      #If the modified U is identical to the copy V, output it
     :ß    #Otherwise start again with the modified U as the new input

C (clang) , 32 bits, 49 44 bytes

i;f(**p,n){for(i=0;i<n*n;)p[i++%n]=*p[i%n];}

Pruébalo en línea!

Utiliza punteros.

50 45 bytes con enteros:

i;f(*p,n){for(i=0;i<n*n;)p[i++%n]=p[p[i%n]];}

Pruébalo en línea!

Ruby , 37 34 bytes

->a{a.size.times{a.map!{|x|a[x]}}}

Pruébalo en línea!

Devuelve modificando la matriz de entrada en el lugar.

Rojo , 63 bytes

func[b][loop(l: length? b)* l[repeat i l[b/:i: b/(1 + b/:i)]]b]

Pruébalo en línea!

Modifica la matriz en su lugar.

R , 60 58 bytes

-2 bytes gracias a @digEmAll por leer las reglas.

function(x,n=sum(x|1)){for(i in rep(1:n,n))x[i]=x[x[i]];x}

Pruébalo en línea!

1 indexado.

n es la longitud de la matriz de entrada.

rep(1:n,n)replica los 1:n ntiempos (p n=3 => 1,2,3,1,2,3,1,2,3. ej. )

Recorre los ntiempos de la matriz . El estado estable se alcanzará para entonces con seguridad, de hecho, al final de la n-1ra vez, creo. La prueba se deja para el lector.

Lisp común, 59 58 bytes

(lambda(a)(dolist(j a)(map-into a(lambda(x)(elt a x))a))a)

Pruébalo en línea!

Limpio , 80 bytes

import StdEnv

limit o iterate\b=foldl(\l i=updateAt i(l!!(l!!i))l)b(indexList b)

Pruébalo en línea!

Clojure , 136 bytes

(defn j[a](let[f(fn[a](loop[i 0 a a](if(= i(count a))a(recur(inc i)(assoc a i(a(a i)))))))](loop[p nil a a](if(= p a)a(recur a(f a))))))

Pruébalo en línea!

Perl 5, 35 34 26 bytes

usando el hecho de que la convergencia es alcanzar como máximo el número de iteraciones

$_=$F[$_]for@F x@F;$_="@F"

26 bytes

$_=$F[$_]for@F;/@F/ or$_="@F",redo

34 bytes

$_=$F[$_]for@F;$_="@F",redo if!/@F/

35 bytes

Clojure , 88 bytes

#(reduce(fn[x i](assoc x i(get x(get x i))))%(flatten(repeat(count %)(range(count %)))))

Pruébalo en línea!

Carbón , 16 bytes

ＦθＦＬθ§≔θκ§θ§θκＩθ

Pruébalo en línea! El enlace es a la versión detallada del código. Lamentablemente, todas las funciones de mapeo habituales solo funcionan en una copia de la matriz con el resultado de que simplemente permutan los elementos en lugar de saltarlos, por lo que el código tiene que hacer todo manualmente. Explicación:

Ｆθ

Repita el bucle interno una vez para cada elemento. Esto solo asegura que el resultado se estabilice.

ＦＬθ

Recorrer los índices de la matriz.

§≔θκ§θ§θκ

Obtenga el elemento de matriz en el índice actual, úselo para indexar en la matriz y reemplace el elemento actual con ese valor.

Ｉθ

Convierta los elementos en cadenas e imprima implícitamente cada uno en su propia línea.

F #, 74 73 bytes

fun(c:'a[])->let l=c.Length in(for i in 0..l*l do c.[i%l]<-c.[c.[i%l]]);c

Nada especial. Utiliza la idea de módulo vista en otras respuestas.

K, 27 bytes

{{@[x;y;:;x x y]}/[x;!#x]}/

• {..}/ aplica lambda {..} sobre arg (hasta la convergencia)

• interior lambda exterior:

  • {..}/[x;y]aplica lambda iterativamente sobre x (actualizado en cada iteración) y un elemento de y (y es una lista de valores, y utiliza un elemento en cada iteración). En este caso, arg y es !#x(hasta contar x, es decir, índices de la matriz)

  • @[x;y;:;x x y] modificar matriz x (en el índice y asignar x [x [y]])

APL (Dyalog Unicode) , ^{SBCS de} 26 bytes

Requiere ⎕IO←0

{m⊣{m[⍵]←m[m[⍵]]}¨⍳≢m←⍵}⍣≡

Pruébalo en línea!