Swap indices et valeurs

29

La tâche

Écrivez un programme ou une fonction dont l'entrée est une liste / tableau X d'entiers, et dont la sortie est une liste d'ensembles d'entiers Y , de telle sorte que pour chaque élément e dans chaque ensemble Y [ i ], X [ e ] = i , et de telle sorte que le nombre total d'éléments dans les ensembles en Y est égal au nombre d'éléments dans X .

(Il s'agit essentiellement de la même opération que l'inversion d'une table de hachage / dictionnaire, sauf si elle est appliquée aux tableaux à la place.)

Exemples

Ces exemples supposent une indexation basée sur 1, mais vous pouvez utiliser une indexation basée sur 0 à la place si vous préférez.

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}]

Clarifications

  • Vous pouvez représenter un ensemble sous forme de liste, si vous le souhaitez. Si vous le faites, l'ordre de ses éléments n'a pas d'importance, mais vous ne pouvez pas répéter les éléments.
  • Vous pouvez utiliser n'importe quel format d'E / S non ambigu raisonnable; par exemple, vous pouvez séparer les éléments d'un ensemble par des espaces et les ensembles eux-mêmes par des sauts de ligne.
  • Y doit être finement long et au moins suffisamment long pour avoir tous les éléments de X comme index de tableau. Il peut cependant être plus long que l'élément maximal de X (les éléments supplémentaires seraient des ensembles vides).
  • Les éléments de X seront tous des indices de tableau valides, c'est-à-dire des entiers non négatifs si vous utilisez une indexation basée sur 0, ou des entiers positifs si vous utilisez une indexation basée sur 1.

Condition de victoire

En tant que défi de , plus c'est court, mieux c'est.

Cyoce
la source
Connexes . Dans le post Sandbox (maintenant supprimé, mais vous pouvez le voir si vous avez la réputation), nous avons décidé qu'il ne s'agissait probablement pas d'un doublon, mais n'hésitez pas à voter pour fermer si vous n'êtes pas d'accord.
Est-ce que "l'ordre de ses éléments n'a pas d'importance" signifie que les sorties de [5,5,6,6]et [6,6,5,5]peuvent être identiques?
Leaky Nun
1
@LeakyNun L'ordre des éléments des ensembles dans la liste de sortie n'a pas d'importance. Donc , [5,5,6,6]et [6,6,5,5]ne peut pas avoir une sortie identique, mais la sortie pour [5,5,6,6]aurait aussi pu, par exemple, [{},{},{},{},{2,1},{4,3}].
ngenisis
Existe-t-il une valeur maximale supposée d'un index dans X? Les ensembles vides peuvent-ils également avoir un 0 au lieu d'être réellement vides? Par exemple, serait [{0},{0},{0},{0},{1,2},{3,4}]une sortie valide pour [5,5,6,6]?
Skidsdev
@Mayube: Non à la première réponse (bien que si vous utilisez un langage qui a une plage limitée sur les entiers, vous pouvez écrire le programme comme si les entiers pouvaient être illimités, et ne vous inquiétez pas de le casser si quelqu'un vous donne un out- entier compris comme entrée). En ce qui concerne la deuxième question, c'est une syntaxe non ambiguë (si bizarre) lorsque vous utilisez l'indexation basée sur 1, donc oui dans ce cas (évidemment, non si vous utilisez l'indexation basée sur 0 car alors le 0 signifierait quelque chose sinon.)

Réponses:

9

MATL , 8 octets

tn:IXQ&D

L'entrée est un vecteur colonne, avec ;comme séparateur (par exemple [2;2;2]). La sortie est la représentation sous forme de chaîne d'un tableau de cellules de vecteurs de ligne (par exemple {[]; [1 2 3]}). Un vecteur ligne d'un seul élément est identique à un nombre (il {1; 2; 3}serait donc affiché à la place de {[1]; [2]; [3]}).

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

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 plupart du travail est effectué par la fonction d'ordre supérieur de Matlab accumarray, qui regroupe les éléments dans la deuxième entrée en fonction des valeurs correspondantes dans la première, et applique une fonction spécifiée à chaque groupe. Dans ce cas @(x){sort(x).'}, la fonction est la sortie des éléments triés dans chaque groupe et le regroupement des résultats de tous les groupes dans un tableau de cellules.

Luis Mendo
la source
7

Python, 69 octets

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

Utilise l'indexation basée sur 0.

Uriel
la source
7

Gelée , 7 5 octets

=þṀT€

Essayez-le en ligne!

Comment ça marche

=þṀ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
la source
5

Gelée , 8 octets

Jẋ"Ṭ€;"/

Essayez-le en ligne!

Comment ça marche

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]]
Leaky Nun
la source
4

Mathematica, 36 octets

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

Explication

entrez la description de l'image ici

Pour chaque nin {1, 2, ..., Max@#}, où Max@#est le plus grand entier de la liste d'entrée, calcule le Positions où napparaît dans la liste d'entrée #. Puisque Position[{6,6,5,5},5](par exemple) retourne {{3},{4}}, on passe alors Apply Joinà tous les éléments au niveau {1}du résultat.

ngenisis
la source
3

Haskell , 45 octets

sprend une liste d'entiers et retourne une liste de listes. 1-indexé pour garder les entrées du scénario de test non modifiées (bien que la sortie obtienne des listes vides supplémentaires).

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

Essayez-le en ligne!

Ce sont des compréhensions de listes imbriquées assez simples. Le seul léger ajustement profite de l'option pour faire une liste plus longue en utilisant sumau lieu de maximum.

Ørjan Johansen
la source
3

PHP, 55 octets

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

0 indexé.

user63956
la source
3

R, 68 49 47 octets

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

Étonnamment, beaucoup plus simple que les solutions plus longues. Prend un vecteur xde STDIN, crée un vecteur de 1à max(x), génère implicitement une liste de longueur max(x)et vérifie quels indices xcorrespondent à ceux de la nouvelle liste. Imprime implicitement la sortie.

Ancienne version:

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

Approche légèrement différente de l'autre réponse R. Prend un vecteur pour STDIN, crée une liste avec une longueur égale à la valeur maximale dans l'entrée. Boucle sur l'entrée et ajoute l'index au bon endroit.

Utilise l'indexation basée sur 1.

JAD
la source
2

Python 2 , 91 86 85 octets

Je programme sur mon téléphone mais j'ai vraiment aimé ce défi. Je peux certainement jouer au golf plus loin.

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

Essayez-le en ligne!

totalement humain
la source
Out-golfed à nouveau par une compréhension de liste imbriquée. : D
totalement humain
2

Gelée , 9 octets

Ṭ+\ịĠȧ@"Ṭ

Ensembles vides indexés 1 représentés comme 0, ensembles d'un élément représentés comme des Nensembles d'éléments multiples représentés comme[M,N,...]

Essayez-le en ligne!

Comment?

Ṭ+\ịĠȧ@"Ṭ - 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
la source
2

JavaScript (ES6), 64 62 octets

Enregistré 2 octets grâce à @SteveBennett


Prend une entrée indexée 0. Renvoie une liste d'ensembles séparés par des virgules.

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

Cas de test


Version alternative, 53 octets

Si une sortie simplifiée telle que '||||3,2|1,0'acceptable, nous pouvons simplement faire:

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&o.join`|`
Arnauld
la source
Sensationnel. Je suis tellement confus sur la façon dont `{${o.join`},{`}}`est légal ES2015.
Steve Bennett
@SteveBennett, c'est un modèle littéral . Dans les anciennes versions de JS, ce serait le cas "{" + o.join("},{") + "}", si cela le rend plus clair.
Shaggy
Non, je les connais - c'est la citation après le mot rejoindre qui me déroute. Est-ce que cela ferme la chaîne (dans ce cas wtf) ou est-ce ainsi que vous échappez à une accolade?
Steve Bennett
Hmm, ok, donc dans ce contexte join`est équivalent à join('. Je ne savais pas que tu pouvais faire ça.
Steve Bennett
Ah, maintenant je vois. C'est un littéral de modèle balisé. Que vous pouvez abuser de sauver un couple de caractères à chaque fois que vous appelez une fonction qui prend un argument de chaîne (et ne tient pas compte d' autres): array.join` `. Super déroutant ici parce que vous l'incorporez dans une chaîne de modèle, et encore plus confus, la chaîne de jonction est },{, qui ressemblait par hasard à une partie de la chaîne de modèle ... et est juste bizarre et laide de toute façon. :)
Steve Bennett
1

Bash , 109 octets

Dommage qu'il n'y ait pas de valeur maximale intégrée pour le tableau.

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;}

Essayez-le en ligne!

Maxim Mikhaylov
la source
1

Mathematica 62 octets

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

Je le ferai pour toi

(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}}

Essayez-le en ligne (collez simplement le code avec ctrl-v et appuyez sur Maj + Entrée)
n'oubliez pas de coller la liste d'entrée à la fin comme dans l'exemple ci-dessus

J42161217
la source
Bienvenue chez PPCG! Vous pouvez enregistrer un octet en utilisant la notation infixe pour AppendTo. Aussi, {j,1,Length[#1]}pourrait-être {j,Length@#}, ou encore plus court, {j,Tr[1^#]}. Tr[1^#]est une astuce assez courante pour enregistrer un octet par-dessus l'utilisation Length.
ngenisis
1

Perl 6 ,  36 32  29 octets

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

Essayez-le

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

Essayez-le

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

Essayez-le


Étendu:

{  # 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 「$_」

}

Renvoie des index à base zéro, pour obtenir 1, utiliser l'opérateur croisé ( X) combiné avec +op . (33 octets)

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

Pour qu'il retourne les Set s, ajoutez-set y simplement (total de 37 octets)

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

R, 80 72 octets

1 indexé, Xextrait de stdin. Renvoie une liste de vecteurs des indices, avec NULLcomme ensemble vide.

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

Essayez-le en ligne!

ancienne version:

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

Essayez-le en ligne!

Giuseppe
la source
Je pense que ça Y=list();marche aussi bien
rturnbull
fewJ'ai réussi
JAD
0

Röda , 51 octets

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

C'est un portage de la réponse Python d'Uriel .

Une autre version (88 octets):

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]}_}

Essayez-le en ligne!

Les deux sont indexés sur 1.

fergusq
la source
0

PowerShell, 81 octets

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

Essayez-le en ligne!

1 indexé.

Andrei Odegov
la source
0

Marque GNU , 214 213 208 204 octets

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

E / S: tableau d'entrée via des arguments, sortie vers stdout, un par ligne, séparés par des espaces.

$ make -f swap.mk 2 2 2

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

Explication

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

L'ordre des indices dans les ensembles est inversé car il Ps'appelle récursivement avant la mise à jour A$2(appel exécuté dans l'évaluation du côté droit).

eush77
la source
A-t make-il un moyen de faire de l'arithmétique elle-même? Faire appel à des programmes externes pour le faire ressemble un peu à de la triche, car vous pourriez probablement mettre beaucoup plus d'algorithme dans ces programmes et vous retrouver avec un programme plus court.
@ ais523 Ce n'est pas le cas. Version précédente utilisée bcet grep. Je pourrais aussi utiliser testet $?. dca une syntaxe terser, mais franchement, tous ces sentiments sont les mêmes.
eush77
0

Lisp commun, 91 octets

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

Indexation basée sur 1, renvoie les ensembles sous forme de listes.

Essayez-le en ligne!

Renzo
la source
0

k , 13 octets

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

Ceci est indexé 0.

Essayez-le en ligne!

{           } /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
la source