Indizes und Werte tauschen

29

Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion, deren Eingabe eine Liste / ein Array X von Ganzzahlen ist und deren Ausgabe eine Liste von Mengen von Ganzzahlen Y ist , so dass für jedes Element e in jeder Menge Y [ i ], X [ e ] = i und so dass die Gesamtzahl der Elemente in den Mengen in Y der Anzahl der Elemente in X entspricht .

(Dies ist im Grunde derselbe Vorgang wie das Umkehren einer Hash-Tabelle / eines Wörterbuchs, außer dass dies stattdessen auf Arrays angewendet wird.)

Beispiele

In diesen Beispielen wird eine 1-basierte Indizierung vorausgesetzt. Sie können jedoch auch eine 0-basierte Indizierung verwenden, wenn Sie dies vorziehen.

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

Klarstellungen

  • Wenn Sie möchten, können Sie ein Set als Liste darstellen. In diesem Fall spielt die Reihenfolge der Elemente keine Rolle, Sie können jedoch möglicherweise keine Elemente wiederholen.
  • Sie können jedes vernünftige, eindeutige E / A-Format verwenden. Sie können beispielsweise Elemente einer Menge durch Leerzeichen und die Mengen selbst durch Zeilenumbrüche trennen.
  • Y sollte endlich lang sein und mindestens so lang, dass alle Elemente von X als Array-Indizes vorliegen. Es kann jedoch länger als das maximale Element von X sein (die zusätzlichen Elemente wären leere Mengen).
  • Die Elemente von X sind alle gültige Array-Indizes, dh nicht negative Ganzzahlen, wenn Sie eine 0-basierte Indizierung verwenden, oder positive Ganzzahlen, wenn Sie eine 1-basierte Indizierung verwenden.

Siegbedingung

Als Herausforderung ist kürzer besser.

Cyoce
quelle
Verwandte . Im Sandbox-Beitrag (der jetzt gelöscht wurde, den Sie jedoch anzeigen können, wenn Sie den Ruf haben) haben wir entschieden, dass es sich wahrscheinlich nicht um ein Duplikat handelt. Sie können jedoch abzustimmen, um den Beitrag zu schließen, wenn Sie anderer Meinung sind.
Bedeutet "die Reihenfolge seiner Elemente spielt keine Rolle", dass die Ausgaben von [5,5,6,6]und [6,6,5,5]identisch sein können?
Undichte Nonne
1
@LeakyNun Die Reihenfolge der Elemente der Mengen in der Ausgabeliste spielt keine Rolle. Also [5,5,6,6]und [6,6,5,5]kann keine identische Ausgabe haben, aber die Ausgabe für [5,5,6,6]könnte auch zB gewesen sein [{},{},{},{},{2,1},{4,3}].
Genisis
Gibt es einen annehmbaren Maximalwert eines Index in X? Können leere Mengen auch eine 0 enthalten, anstatt tatsächlich leer zu sein? Zum Beispiel wäre [{0},{0},{0},{0},{1,2},{3,4}]eine gültige Ausgabe für [5,5,6,6]?
Skidsdev
@Mayube: Nein zur ersten Antwort (obwohl Sie, wenn Sie eine Sprache mit begrenztem Bereich für Ganzzahlen verwenden, das Programm so schreiben können, als könnten Ganzzahlen unbegrenzt groß sein, und sich keine Sorgen darüber machen, dass es kaputt geht, wenn Ihnen jemand einen Fehler macht). of-range Ganzzahl als Eingabe). In Bezug auf die zweite Frage ist dies eine eindeutige (wenn auch seltsame) Syntax, wenn Sie eine auf 1 basierende Indexierung verwenden. In diesem Fall also ja (natürlich nein, wenn Sie eine auf 0 basierende Indexierung verwenden, denn dann würde die 0 etwas bedeuten sonst.)

Antworten:

9

MATL , 8 Bytes

tn:IXQ&D

Die Eingabe ist ein Spaltenvektor mit einem ;Trennzeichen (zum Beispiel [2;2;2]). Die Ausgabe ist die Zeichenfolgendarstellung eines Zellenarrays von Zeilenvektoren (zum Beispiel {[]; [1 2 3]}). Ein Zeilenvektor eines einzelnen Elements ist derselbe wie eine Zahl (wird also {1; 2; 3}statt ausgegeben {[1]; [2]; [3]}).

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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

Die meiste Arbeit erledigt die Matlab-Funktion höherer Ordnung accumarray, die Elemente in der zweiten Eingabe nach übereinstimmenden Werten in der ersten gruppiert und für jede Gruppe eine bestimmte Funktion anwendet. In diesem Fall @(x){sort(x).'}gibt die Funktion die sortierten Elemente in jeder Gruppe aus und bewirkt, dass die Ergebnisse für alle Gruppen in ein Zellenarray gepackt werden.

Luis Mendo
quelle
7

Python, 69 Bytes

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

Verwendet eine 0-basierte Indizierung.

Uriel
quelle
7

Gelee , 7 5 Bytes

=þṀT€

Probieren Sie es online!

Wie es funktioniert

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

Gelee , 8 Bytes

Jẋ"Ṭ€;"/

Probieren Sie es online!

Wie es funktioniert

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]]
Undichte Nonne
quelle
4

Mathematica, 36 Bytes

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

Erläuterung

Bildbeschreibung hier eingeben

Für jeden nin {1, 2, ..., Max@#}, wo Max@#die größte ganze Zahl in der Eingabeliste wird, berechnet der Positions wo nerscheint in der Eingabeliste #. Da Position[{6,6,5,5},5](zum Beispiel) zurückkehrt {{3},{4}}, kehren wir dann Apply Joinzu allen Elementen auf der Ebene {1}des Ergebnisses zurück.

Genisis
quelle
3

Haskell , 45 Bytes

sNimmt eine Liste von ganzen Zahlen und gibt eine Liste von Listen zurück. 1-indiziert, um die Eingaben des Testfalls unverändert zu lassen (obwohl die Ausgabe einige zusätzliche leere Listen enthält).

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

Probieren Sie es online!

Dies sind ziemlich einfache, verschachtelte Listenverständnisse. Die einzige kleine Verbesserung besteht darin, die Option zu nutzen, eine längere Liste zu erstellen, indem sumstatt verwendet wird maximum.

Ørjan Johansen
quelle
3

PHP, 55 Bytes

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

0-indiziert.

user63956
quelle
3

R 68 49 47 Bytes

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

Überraschenderweise viel einfacher als die längeren Lösungen. Nimmt einen Vektor xvon STDIN, erstellt einen Vektor von 1bis max(x), generiert implizit eine Längenliste max(x)und prüft, in welchen Indizesx mit denen in der neuen Liste übereinstimmen. Druckt implizit die Ausgabe.

Ältere Version:

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

Etwas andere Herangehensweise an die andere R-Antwort. Führt einen Vektor zu STDIN und erstellt eine Liste mit der Länge des Maximalwerts in der Eingabe. Durchläuft die Eingabe und fügt den Index an der richtigen Stelle ein.

Verwendet 1-basierte Indizierung.

JAD
quelle
2

Python 2 , 91 86 85 Bytes

Ich programmiere auf meinem Handy, aber diese Herausforderung hat mir sehr gut gefallen. Ich kann dies definitiv weiter Golf spielen.

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

Probieren Sie es online!

total menschlich
quelle
Durch ein verschachteltes Listenverständnis wieder out-golfed. : D
totalhuman
2

Gelee , 9 Bytes

Ṭ+\ịĠȧ@"Ṭ

1-indizierte, leere Mengen, dargestellt als 0, Mengen eines Elements, dargestellt als NMengen mehrerer Elemente, dargestellt als[M,N,...]

Probieren Sie es online!

Wie?

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

JavaScript (ES6), 64 62 Byte

2 Bytes gespart dank @SteveBennett


Nimmt 0-indizierte Eingaben an. Gibt eine durch Kommas getrennte Liste von Mengen zurück.

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

Testfälle


Alternative Version, 53 Byte

Wenn eine vereinfachte Ausgabe wie '||||3,2|1,0'akzeptabel ist, können wir einfach Folgendes tun:

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&o.join`|`
Arnauld
quelle
Wow. Ich bin so verwirrt, wie `{${o.join`},{`}}`legal ES2015 ist.
Steve Bennett
@SteveBennett, es ist ein Vorlagenliteral . In älteren Versionen von JS wäre es "{" + o.join("},{") + "}", wenn das alles klarer macht.
Shaggy
Nein, ich weiß von denen - es ist das Backquote nach dem Wort verbinden, das mich verwirrt. Schließt das die Zeichenkette (in welchem ​​Fall wtf) oder entgeht Ihnen so eine enge Klammer?
Steve Bennett
Hmm, ok, also in diesem Zusammenhang join`entspricht join('. Hatte keine Ahnung, dass du das machen könntest.
Steve Bennett
Ah, jetzt verstehe ich. Es ist ein mit Tags versehenes Vorlagenliteral. Welche können Sie missbrauchen ein paar Zeichen zu speichern , wenn eine Funktion aufrufen , die ein String - Argument (und ignoriert andere): array.join` `. Super verwirrend hier, weil Sie das in eine Template-Zeichenfolge einbetten, und noch verwirrender ist, dass die Join-Zeichenfolge },{zufällig wie ein Teil der Template-Zeichenfolge aussah ... und sowieso nur seltsam und hässlich ist. :)
Steve Bennett
1

Bash , 109 Bytes

Schade, dass es keinen eingebauten Wert für das maximale Array gibt.

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

Probieren Sie es online!

Maxim Mikhaylov
quelle
1

Mathematica 62 Bytes

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

Ich werde es für dich laufen lassen

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

Probieren Sie es online aus (fügen Sie einfach den Code mit Strg-V ein und drücken Sie die Umschalttaste + Eingabetaste) und
vergessen Sie nicht, die Eingabeliste am Ende wie im obigen Beispiel einzufügen

J42161217
quelle
Willkommen bei PPCG! Sie können ein Byte speichern, indem Sie die Infixnotation für verwenden AppendTo. Könnte {j,1,Length[#1]}auch nur {j,Length@#}oder noch kürzer sein {j,Tr[1^#]}. Tr[1^#]ist ein ziemlich häufiger Trick , um ein Byte zu sparen Length.
Genisis
1

Perl 6 ,  36 32  29 Bytes

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

Versuch es

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

Versuch es

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

Versuch es


Erweitert:

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

}

Gibt nullbasierte Indizes zurück, um den 1-basierten use cross operator ( X) in Kombination mit +op zu erhalten . (33 Bytes)

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

Um es zu erhalten zurückzukehren Set s nur Addset dort (insgesamt 37 Bytes)

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

R 80 72 Bytes

1-indiziert, nimmt Xvon stdin. Gibt eine Liste von Vektoren der Indizes mit NULLals leere Menge zurück.

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

Probieren Sie es online!

alte Version:

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

Probieren Sie es online!

Giuseppe
quelle
Ich denke , dass Y=list();funktioniert genauso gut
rturnbull
Es ist fewmir gelungen
JAD
0

Röda , 51 Bytes

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

Es ist ein Hafen der Python-Antwort von Uriel .

Eine andere Version (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]}_}

Probieren Sie es online!

Beides eine 1-indizierte.

fergusq
quelle
0

PowerShell, 81 Byte

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

Probieren Sie es online!

1-indiziert.

Andrei Odegov
quelle
0

GNU Make , 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)))

E / A: Array über Argumente eingeben, Ausgabe an stdout, eines pro Zeile, durch Leerzeichen getrennt.

$ make -f swap.mk 2 2 2

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

Erläuterung

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

Die Reihenfolge der Indizes in Mengen ist umgekehrt, da Psich vor dem Aktualisieren rekursiv aufruft A$2(Aufruf in der Auswertung der rechten Seite ausgeführt).

eush77
quelle
Gibt makees eine Möglichkeit, selbst zu rechnen? Das Aufrufen von externen Programmen zu diesem Zweck fühlt sich ein bisschen wie Schummeln an, da Sie wahrscheinlich viel mehr Algorithmus in diese Programme einbauen und ein kürzeres Programm erhalten könnten.
@ ais523 Hat es nicht. Vorgängerversion verwendet bcund grep. Ich könnte auch testund benutzen $?. dchat eine engere Syntax, aber ehrlich gesagt fühlen sich alle gleich an.
Eush77
0

Common Lisp, 91 Bytes

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

1-basierte Indizierung, gibt die Mengen als Listen zurück.

Probieren Sie es online!

Renzo
quelle
0

k , 13 Bytes

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

Dies ist 0-indiziert.

Probieren Sie es 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
zgrep
quelle