Zadanie

Napisz program lub funkcję, której wejściem jest lista / tablica X liczb całkowitych, a wyjściem jest lista zbiorów liczb całkowitych Y , takich, że dla każdego elementu e w każdym zestawie Y [ i ], X [ e ] = i , i tak, aby całkowita liczba elementów w zestawach w Y jest równa liczbie elementów X .

(Jest to w zasadzie ta sama operacja, co odwracanie tablicy hashującej / słownika, z tą różnicą, że stosuje się ją zamiast tablic).

Przykłady

W tych przykładach założono indeksowanie na podstawie 1, ale zamiast tego można użyć indeksowania na podstawie 0.

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

Wyjaśnienia

• Możesz reprezentować zestaw jako listę, jeśli chcesz. Jeśli to zrobisz, kolejność jego elementów nie ma znaczenia, ale nie możesz powtarzać elementów.
• Możesz użyć dowolnego rozsądnego jednoznacznego formatu We / Wy; na przykład, możesz oddzielić elementy zestawu spacjami, a same zestawy nowymi liniami.
• Y powinno być skończone i co najmniej wystarczająco długie, aby mieć wszystkie elementy X jako indeksy tablic. Może jednak być dłuższy niż maksymalny element X (dodatkowymi elementami byłyby puste zestawy).
• Wszystkie elementy X będą poprawnymi indeksami tablicowymi, tj. Nieujemnymi liczbami całkowitymi, jeśli użyjesz indeksowania opartego na 0, lub dodatnimi liczbami całkowitymi, jeśli użyjesz indeksowania opartego na 1.

Warunek zwycięstwa

Jako wyzwanie dla golfa kodowanego krótszy jest lepszy.

MATL , 8 bajtów

tn:IXQ&D

Dane wejściowe to wektor kolumny z ;separatorem (na przykład [2;2;2]). Dane wyjściowe to ciąg znaków reprezentujący tablicę komórkową wektorów wierszowych (na przykład {[]; [1 2 3]}). Wektor wiersza pojedynczego elementu jest taki sam jak liczba (więc {1; 2; 3}byłby wyprowadzany zamiast {[1]; [2]; [3]}).

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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

Większość pracy jest wykonywana przez funkcję wyższego rzędu Matlaba accumarray, która grupuje elementy na drugim wejściu zgodnie z dopasowanymi wartościami na pierwszym i stosuje określoną funkcję do każdej grupy. W tym przypadku jest to funkcja @(x){sort(x).'}, która wysyła posortowane elementy w każdej grupie i powoduje, że wyniki dla wszystkich grup są upakowane w tablicy komórkowej.

Python, 69 bajtów

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

Korzysta z indeksowania opartego na 0.

Galaretka , 7 5 bajtów

=þṀT€

Wypróbuj online!

Jak to działa

=þṀ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.

Galaretki , 8 bajtów

Jẋ"Ṭ€;"/

Wypróbuj online!

Jak to działa

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 bajtów

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

Wyjaśnienie

Dla każdego nin {1, 2, ..., Max@#}, gdzie Max@#jest największą liczbą całkowitą z listy wejściowego oblicza PositionS, jeżeli npojawi się na liście wejściowego #. Ponieważ Position[{6,6,5,5},5](na przykład) powraca {{3},{4}}, przechodzimy Apply Joindo wszystkich elementów na poziomie {1}wyniku.

Haskell , 45 bajtów

spobiera listę liczb całkowitych i zwraca listę list. 1 indeksowany, aby zachować niezmodyfikowane dane wejściowe przypadku testowego (chociaż dane wyjściowe otrzymują dodatkowe puste listy).

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

Wypróbuj online!

Są to bardzo proste zestawienia zagnieżdżonych list. Jedynym drobnym ulepszeniem jest skorzystanie z opcji tworzenia dłuższej listy za pomocą sumzamiast maximum.

PHP, 55 bajtów

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

0-indeksowane.

R, 68 49 47 bajtów

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

Zaskakujące, o wiele prostsze niż dłuższe rozwiązania. Pobiera wektor xze STDIN, tworzy wektor od 1do max(x), domyślnie generuje listę długości max(x)i sprawdza, które indeksy xodpowiadają tym z nowej listy. Domyślnie drukuje dane wyjściowe.

Starsza wersja:

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

Nieco inne podejście do drugiej odpowiedzi R. Pobiera wektor do STDIN, tworzy listę o długości równej maksymalnej wartości na wejściu. Zapętla dane wejściowe i dodaje indeks we właściwe miejsce.

Wykorzystuje indeksowanie 1.

Python 2 , 91 86 85 bajtów

Programuję na telefonie, ale naprawdę podobało mi się to wyzwanie. Z całą pewnością mogę dalej grać w golfa.

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

Wypróbuj online!

Galaretka , 9 bajtów

Ṭ+\ịĠȧ@"Ṭ

1-indeksowane, puste zestawy reprezentowane jako 0, zestawy jednego elementu reprezentowane jako Nzestawy wielu elementów reprezentowanych jako[M,N,...]

Wypróbuj online!

W jaki sposób?

Ṭ+\ịĠȧ@"Ṭ - 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 bajtów

Zaoszczędzono 2 bajty dzięki @SteveBennett

Pobiera dane z indeksem 0. Zwraca rozdzieloną przecinkami listę zestawów.

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

Przypadki testowe

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

Wersja alternatywna, 53 bajty

Jeśli uproszczone wyjście, takie jak '||||3,2|1,0'jest dopuszczalne, możemy po prostu:

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

Bash , 109 bajtów

Szkoda, że ​​nie ma wbudowanej wartości maksymalnej dla tablicy.

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

Wypróbuj online!

Mathematica 62 bajty

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

Uruchomię to dla ciebie

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

Wypróbuj online (po prostu wklej kod za pomocą Ctrl-V i naciśnij Shift + Enter)
Nie zapomnij wkleić listy wprowadzania na końcu, jak w powyższym przykładzie

Perl 6 ,  36 32  29 bajtów

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

Spróbuj

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

Spróbuj

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

Spróbuj

Rozszerzony:

{  # 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 ｢$_｣

}

Zwraca indeksy oparte na zerach, aby uzyskać 1 operator cross operator ( X) w połączeniu z +op . (33 bajty)

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

Aby go zwrócić Zestaw s po prostu dodajset tam (razem 37 bajtów)

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

R 80 80 bajtów

1-indeksowany, pobiera Xze standardowego wejścia. Zwraca listę wektorów indeksów z NULLpustym zbiorem.

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

Wypróbuj online!

stara wersja:

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

Wypróbuj online!

05AB1E , 10 bajtów

ZFā¹N-ψ}¯

Wypróbuj online!

Röda , 51 bajtów

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

Jest to port odpowiedzi Pytona autorstwa Uriela .

Inna wersja (88 bajtów):

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

Wypróbuj online!

Zarówno indeksowane 1.

PowerShell, 81 bajtów

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

Wypróbuj online!

1-indeksowany.

Marka GNU , 214 213 208 204 bajtów

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: tablica wejściowa za pomocą argumentów, wyjście na standardowe wyjście, po jednym w wierszu, oddzielone spacjami.

$ make -f swap.mk 2 2 2

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

Wyjaśnienie

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

Kolejność indeksów w zestawach jest odwrócona, ponieważ Pwywołuje się rekurencyjnie przed aktualizacją A$2(wywołanie wykonywane w ocenie po prawej stronie).

Common Lisp, 91 bajtów

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

Indeksowanie 1, zwraca zestawy jako listy.

Wypróbuj online!

k , 13 bajtów

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

To jest indeksowane na 0.

Wypróbuj online!

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