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 code-golf , plus c'est court, mieux c'est.

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.

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.

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.

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

Mathematica, 36 octets

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

Explication

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.

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.

PHP, 55 octets

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

0 indexé.

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.

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!

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

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

let f =

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

console.log(f([3]))
console.log(f([0,1,2]))
console.log(f([1,1,1]))
console.log(f([4,4,5,5]))
console.log(f([5,5,4,4]))

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

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!

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

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}

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!

05AB1E , 10 octets

ZFā¹N-ψ}¯

Essayez-le en ligne!

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.

PowerShell, 81 octets

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

Essayez-le en ligne!

1 indexé.

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

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!

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