Intercambiar índices y valores

29

La tarea

Escriba un programa o función cuya entrada sea una lista / matriz X de enteros, y cuya salida sea una lista de conjuntos de enteros Y , de modo que para cada elemento e en cada conjunto Y [ i ], X [ e ] = i , y tal que el número total de elementos de los sistemas en Y es igual al número de elementos en X .

(Esta es básicamente la misma operación que invertir una tabla hash / diccionario, excepto que se aplica a las matrices).

Ejemplos

Estos ejemplos suponen una indexación basada en 1, pero puede usar una indexación basada en 0 si lo prefiere.

X             Y
[4]           [{},{},{},{1}]
[1,2,3]       [{1},{2},{3}]
[2,2,2]       [{},{1,2,3}]
[5,5,6,6]     [{},{},{},{},{1,2},{3,4}]
[6,6,5,5]     [{},{},{},{},{3,4},{1,2}]

Aclaraciones

  • Puede representar un conjunto como una lista, si lo desea. Si lo hace, el orden de sus elementos no importa, pero no puede repetir elementos.
  • Puede usar cualquier formato de E / S razonablemente inequívoco; por ejemplo, podría separar elementos de un conjunto con espacios y los conjuntos con líneas nuevas.
  • Y debe ser finitamente largo, y al menos lo suficientemente largo como para tener todos los elementos de X como índices de matriz. Sin embargo, puede ser más largo que el elemento máximo de X (los elementos adicionales serían conjuntos vacíos).
  • Todos los elementos de X serán índices de matriz válidos, es decir, enteros no negativos si usa indexación basada en 0, o enteros positivos si usa indexación basada en 1.

Condición de victoria

Como un desafío de , más corto es mejor.

Cyoce
fuente
Relacionados . En la publicación de Sandbox (ahora eliminada, pero puede verla si tiene reputación), decidimos que probablemente no era un duplicado, pero no dude en votar para cerrar si no está de acuerdo.
¿"El orden de sus elementos no importa" significa que los resultados de [5,5,6,6]y [6,6,5,5]pueden ser idénticos?
Leaky Nun
1
@LeakyNun El orden de los elementos de los conjuntos en la lista de salida no importa. Por lo tanto [5,5,6,6], y [6,6,5,5]no puede tener salida idéntica, pero la salida de [5,5,6,6]también podría haber sido, por ejemplo, [{},{},{},{},{2,1},{4,3}].
ngenisis
¿Hay un valor máximo asumible de un índice en X? Además, ¿pueden los conjuntos vacíos tener un 0 en lugar de estar realmente vacíos? Por ejemplo, ¿ [{0},{0},{0},{0},{1,2},{3,4}]sería una salida válida para [5,5,6,6]?
Skidsdev
@Mayube: No a la primera respuesta (aunque si estás usando un lenguaje que tiene un rango limitado en enteros, puedes escribir el programa como si los enteros pudieran ser ilimitadamente grandes, y no te preocupes si se rompe si alguien te da un ... entero de rango como entrada). Con respecto a la segunda pregunta, esa es una sintaxis inequívoca (si es extraña) cuando está usando indexación basada en 1, por lo que sí en ese caso (obviamente, no si está usando indexación basada en 0 porque entonces 0 significaría algo más.)

Respuestas:

9

MATL , 8 bytes

tn:IXQ&D

La entrada es un vector de columna, con un ;separador (por ejemplo [2;2;2]). La salida es la representación de cadena de una matriz de celdas de vectores de fila (por ejemplo {[]; [1 2 3]}). Un vector de fila de un solo elemento es lo mismo que un número (por {1; 2; 3}lo que se generaría en lugar de {[1]; [2]; [3]}).

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

t     % Implicit input, say x. Duplicate
n     % Number of elements, say N
:     % Range: [1 2 ... N]
IXQ   % accumarray(x, [1 2 ... N], [], @(x){sort(x).'})
&D    % String representation

La mayor parte del trabajo se realiza mediante la función de orden superior de Matlab accumarray, que agrupa elementos en la segunda entrada de acuerdo con valores coincidentes en la primera, y aplica una función específica a cada grupo. La función en este caso es @(x){sort(x).'}, que genera los elementos ordenados en cada grupo y hace que los resultados para todos los grupos se empaqueten en una matriz de celdas.

Luis Mendo
fuente
7

Python, 69 bytes

lambda s:[[j for j,x in enumerate(s)if x==i]for i in range(max(s)+1)]

Utiliza indexación basada en 0.

Uriel
fuente
7

Jalea , 7 5 bytes

=þṀT€

Pruébalo en línea!

Cómo funciona

=þṀT€  Main link. Argument: A (array)

  Ṁ    Yield m, the maximum of A.
=þ     Equals table; for each t in [1, ..., m], compare all elemnts of A with t,
       yielding a 2D Boolean array.
   T€  Truth each; for each Boolean array, yield all indices of 1.
Dennis
fuente
5

Jalea , 8 bytes

Jẋ"Ṭ€;"/

Pruébalo en línea!

Cómo funciona

Jẋ"Ṭ€;"/  argument: z           eg. [6,6,4,4]
J         [1 .. len(z)]             [1,2,3,4]
   Ṭ€     untruth each of z         [[0,0,0,0,0,1],
                                     [0,0,0,0,0,1],
                                     [0,0,0,1],
                                     [0,0,0,1]]
 ẋ"       repeat each of ^^         [[[],[],[],[],[],[1]],
          as many times as           [[],[],[],[],[],[2]],
          each of ^                  [[],[],[],[3]],
                                     [[],[],[],[4]]]
       /  reduce by...
     ;"   vectorized concatenation  [[],[],[],[3,4],[],[1,2]]
Monja permeable
fuente
4

Mathematica, 36 bytes

Join@@@#~Position~n~Table~{n,Max@#}&

Explicación

ingrese la descripción de la imagen aquí

Para cada uno nde {1, 2, ..., Max@#}donde Max@#es el mayor número entero en la lista de entrada, calcula los Positions donde naparece en la lista de entrada #. Como Position[{6,6,5,5},5](por ejemplo) regresa {{3},{4}}, pasamos Apply Joina todos los elementos a nivel {1}del resultado.

ngenisis
fuente
3

Haskell , 45 bytes

stoma una lista de enteros y devuelve una lista de listas. 1 indexado para mantener las entradas del caso de prueba sin modificar (aunque la salida obtiene algunas listas vacías adicionales).

s l=[[i|(i,y)<-zip[1..]l,y==x]|x<-[1..sum l]]

Pruébalo en línea!

Estas son comprensiones de listas anidadas bastante sencillas. El único pequeño ajuste es aprovechar la opción de hacer una lista más larga usando en sumlugar de maximum.

Ørjan Johansen
fuente
3

PHP, 55 bytes

<?while($i<=max($_GET))print_r(array_keys($_GET,$i++));

0 indexado.

usuario63956
fuente
3

R, 68 49 47 bytes

lapply(1:max(x<-scan()),function(y)which(y==x)) 

Sorprendentemente, mucho más sencillo que las soluciones más largas. Toma un vector xde STDIN, crea un vector de 1a max(x), genera implícitamente una lista de longitud max(x)y comprueba qué índices se xcorresponden con los de la nueva lista. Imprime implícitamente la salida.

Versión antigua:

o=vector('list',max(x<-scan()));for(i in x)o[[i]]=c(o[[i]],F<-F+1);o

Enfoque ligeramente diferente a la otra respuesta R. Toma un vector para STDIN, crea una lista con una longitud igual al valor máximo en la entrada. Recorre la entrada y agrega el índice en el lugar correcto.

Utiliza indexación basada en 1.

JAD
fuente
2

Python 2 , 91 86 85 bytes

Estoy programando en mi teléfono pero realmente me gustó este desafío. Definitivamente puedo jugar golf más allá.

def f(a):
 r=[[]for i in range(max(a)+1)]
 for i,j in enumerate(a):r[j]+=[i]
 print r

Pruébalo en línea!

totalmente humano
fuente
Fuera de golf otra vez por una lista de comprensión anidada. : D
totalmente humano
2

Jalea , 9 bytes

Ṭ+\ịĠȧ@"Ṭ

Conjuntos vacíos indexados en 1 representados como 0conjuntos de un elemento representados como Nconjuntos de elementos múltiples representados como[M,N,...]

Pruébalo en línea!

¿Cómo?

Ṭ+\ịĠȧ@"Ṭ - Main link: list a        e.g. [6,6,4,4]
Ṭ         - untruth a                     [0,0,0,1,0,1]
  \       - cumulative reduce with:
 +        -   addition                    [0,0,0,1,1,2]
    Ġ     - group indices of a by value   [[3,4],[1,2]]
   ị      - index into                    [[1,2],[1,2],[1,2],[3,4],[3,4],[1,2]]
        Ṭ - untruth a                     [0,0,0,1,0,1]
       "  - zip with:
     ȧ@   -   and with reversed @rguments [0,0,0,[3,4],0,[1,2]]
Jonathan Allan
fuente
2

JavaScript (ES6), 64 62 bytes

Guardado 2 bytes gracias a @SteveBennett


Toma entrada indexada 0. Devuelve una lista de conjuntos separados por comas.

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&`{${o.join`},{`}}`

Casos de prueba


Versión alternativa, 53 bytes.

Si una salida simplificada como '||||3,2|1,0'es aceptable, simplemente podemos hacer:

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&o.join`|`
Arnauld
fuente
Guau. Estoy tan confundido como `{${o.join`},{`}}`es legal ES2015.
Steve Bennett
@SteveBennett, es una plantilla literal . En versiones anteriores de JS lo sería "{" + o.join("},{") + "}", si eso lo aclara más.
Shaggy
No, sé sobre eso: es la cita posterior después de la palabra unirse que me confunde. ¿Eso está cerrando la cadena (en cuyo caso wtf) o es así como escapas de una llave estrecha?
Steve Bennett
Hmm, ok, entonces en este contexto join`es equivalente a join('. No tenía idea de que pudieras hacer eso.
Steve Bennett
Ah, ya veo. Es una plantilla etiquetada literal. Que se puede abusar para guardar un par de caracteres cada vez que llamar a una función que toma un argumento de serie (e ignora otros): array.join` `. Súper confuso aquí porque está incrustando eso dentro de una cadena de plantilla, y aún más confusamente, la cadena de unión es },{, que casualmente parecía parte de la cadena de plantilla ... y de todos modos es extraña y fea. :)
Steve Bennett
1

Bash , 109 bytes

Lástima que no haya incorporado un valor máximo de matriz.

a=($@)
for((x=m=1;x<=m;x++)){ for((y=0;y<$#;)){((m<a[y]))&&((m=a[y]));((a[y++]==x))&&printf "%d " $y;};echo;}

Pruébalo en línea!

Maxim Mikhaylov
fuente
1

Mathematica 62 bytes

(Y={}~Table~Max@#;Y[[#[[j]]]]~AppendTo~j~Table~{j,Tr[1^#]};Y)&

Lo correré por ti

(Y={}~Table~Max@#;Y[[#[[j]]]]~AppendTo~j~Table~{j,Tr[1^#]};Y)&[{4,5,2,3,3,8,6,3}]

{{}, {3}, {4, 5, 8}, {1}, {2}, {7}, {}, {6}}

Pruébelo en línea (solo pegue el código con ctrl-v y presione shift + enter)
no olvide pegar la lista de entrada al final como en el ejemplo anterior

J42161217
fuente
Bienvenido a PPCG! Puede guardar un byte utilizando la notación infija para AppendTo. Además, {j,1,Length[#1]}solo podría ser {j,Length@#}, o incluso más corto, {j,Tr[1^#]}. Tr[1^#]Es un truco bastante común para guardar un byte sobre el uso Length.
ngenisis
1

Perl 6 ,  36 32  29 bytes

->\a{map {a.grep(*==$_):k},1..a.max}

Intentalo

{map {.grep(*==$^a):k},1.. .max}

Intentalo

{map {.grep($^a):k},1.. .max}

Intentalo


Expandido:

{  # bare block lambda with implicit parameter 「$_」

  map

    {  # bare block lambda with placeholder parameter 「$a」

      .grep(  # grep for the values in 「$_」
        $^a   # that are equal to the currently tested value (and declare param)
      ) :k    # return the key (index) rather than the value
    },

    1 .. .max # Range from 1 to the maximum value in 「$_」

}

Devuelve índices basados ​​en cero; para obtener 1, utilice el operador cruzado ( X) combinado con +op . (33 bytes)

{1 X+.grep($^a):k}

Para que regrese , solo agregueset allí (total 37 bytes)

{set 1 X+.grep($^a):k}
Brad Gilbert b2gills
fuente
1

R, 80 72 bytes

1 indexado, toma Xde stdin. Devuelve una lista de vectores de los índices, con NULLel conjunto vacío.

X=scan();Y=vector('list',max(X));Y[X]=lapply(X,function(x)which(X==x));Y

Pruébalo en línea!

versión antigua:

X=scan();Y=vector('list',max(X));for(i in 1:length(X))Y[[X[i]]]=c(Y[[X[i]]],i);Y

Pruébalo en línea!

Giuseppe
fuente
Creo que Y=list();funciona igual de bien
rturnbull
Logré eliminar unos fewbytes en mi respuesta :) codegolf.stackexchange.com/a/120024/59530
JAD
0

Röda , 51 bytes

f s{seq(1,max(s))|[[s()|enum|[_2+1]if[_1=i]]]for i}

Es un puerto de la respuesta Python de Uriel .

Otra versión (88 bytes):

f a{I=indexOf;seq(1,max(a))|{|i|b=a[:]c=[]x=1{c+=x+I(i,b)b-=i;x++}until[I(i,b)<0];[c]}_}

Pruébalo en línea!

Ambos un 1 indexado.

fergusq
fuente
0

PowerShell, 81 bytes

$args[0]|%{if($_-gt($c=$r.count)){$r+=@($t)*($_-$c)}$r[--$_]+=,++$i};$r|%{"{$_}"}

Pruébalo en línea!

1 indexado.

Andrei Odegov
fuente
0

Marca GNU , 214 213 208 204 bytes

X=$(MAKECMDGOALS)
M=0
P=$(eval N=$(word $1,$X))$(if $N,$(if $(shell dc -e$Nd$Mds.\>.p),$(eval M=$N),)$(eval A$N+=$1$(call $0,$(shell expr $1 + 1))),)
$(call P,1)$(foreach K,$(shell seq $M),$(info $(A$K)))

I / O: matriz de entrada a través de argumentos, salida a stdout, uno por línea, separados por espacios.

$ make -f swap.mk 2 2 2

3 2 1
make: *** No rule to make target `2'.  Stop.

Explicación

X=$(MAKECMDGOALS)     # Input array
M=0                   # Max value encountered in X
P=$(eval
    N=$(word $1,$X))  # Get next word from X
  $(if $N,$(if $(shell dc -e$Nd$Mds.\>.p),
    $(eval M=$N),)    # Update M
    $(eval A$N+=$1    # Append index to a variable named after value
      $(call $0,      # Recurse (call returns empty string)
        $(shell expr $1 + 1))),)
$(call P,1)           # Initial call to P. 1 is the first index
$(foreach K,          # Print all values of A* variables
  $(shell seq $M),
  $(info $(A$K)))     # Uninitialized ones default to empty strings

El orden de los índices en conjuntos se invierte porque se Pllama recursivamente antes de actualizar A$2(llamada ejecutada en la evaluación del lado derecho).

eush77
fuente
¿ makeTiene alguna forma de hacer aritmética en sí? Llamar a programas externos para hacerlo se siente un poco como hacer trampa, porque probablemente podrías poner mucho más del algoritmo en esos programas y terminar con un programa más corto.
@ ais523 No lo ha hecho. Versión anterior utilizada bcy grep. También podría usar testy $?. dctiene una sintaxis terser, pero, francamente, todos sienten lo mismo
eush77
0

Lisp común, 91 bytes

(lambda(x &aux(l(make-list(eval`(max,@x))))(i 0))(dolist(y x l)(push(incf i)(nth(1- y)l))))

Indexación basada en 1, devuelve los conjuntos como listas.

Pruébalo en línea!

Renzo
fuente
0

k , 13 bytes

{(=x)@!1+|/x}

Esto está indexado a 0.

Pruébalo en línea!

{           } /function(x)
 (=x)         /make a map/dictionary of values to their indices
         |/x  /get maximum value in x
      !1+     /make a range from 0 to the value, inclusive
     @        /get map value at each of the values in the range
              /    0N is given where there is no result
zgrep
fuente