(Angepasst an Problem C des ersten Qualifikanten des ACM-Programmierwettbewerbs 2012/2013 )

Sie haben mehrere Arrays mit den Namen A ₁ , A ₂ , ..., A _n , die jeweils in aufsteigender Reihenfolge sortiert sind. Jedes Element im Array ist eine 32-Bit-Ganzzahl.

Ein Sandwich ist eine Menge von Indizes j ₁ , j ₂ , ..., j _n, so dass A ₁ [j ₁ ] ≤ A ₂ [j ₂ ] ≤ .... ≤ A _n [j _n ].
A _i [0] ist das erste Element von A _i .

Geben Sie bei einigen Arrays jedes mögliche Sandwich aus, das Sie von diesen Arrays haben können, getrennt durch eine neue Zeile.

Wenn es eine integrierte Funktion gibt, die dies in Ihrer Sprache tut, verwenden Sie sie nicht.

Die Eingabe kann auf beliebige Weise erfolgen, die Ausgabe muss durch Leerzeichen getrennt werden, kann jedoch in beliebiger Reihenfolge erfolgen.

Testfall:
[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]

Ausgabe:

0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2

Testfall:
[[10, 20, 30], [1, 2, 3]]

Ausgabe:

Der kürzeste Code gewinnt.

APL (33)

↑1-⍨B/⍨{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B←,⍳⊃∘⍴¨A←⎕

Die Eingabe wird vom Tastenfeld gelesen, muss jedoch als APL-Liste angegeben werden, d. H.

(1 5 7 10) (2 6 6 8 12) (4 5 9)

Erläuterung:

• B←,⍳⊃∘⍴¨A←⎕: A wird als Eingabe ausgewertet, B sind alle möglichen Sätze von Indizes in den in A angegebenen Listen.
• {(⍳⍴A)∘≡⍋⍵⌷¨A}¨B: Holen Sie sich für jeden Satz von Indizes die Werte aus den Listen ( ⍵⌷¨A) und prüfen Sie, ob sie sortiert sind ( (⍳⍴A)∘=⍋)
• B/⍨: Wählen Sie aus B alle Indexsätze aus, bei denen der vorherige Ausdruck wahr war (dh alle Sandwiches).
• 1-⍨: subtrahiere eins von allen Indizes, da diese Frage davon ausgeht, dass 0-basierte Arrays und APL-Arrays standardmäßig 1-basiert sind.
• ↑: Ordnen Sie die Liste der Indexsätze als Matrix an (so dass jeder Satz in einer eigenen Zeile steht).

Mathematica 120 130

Bearbeiten

Diese Version funktioniert mit Arrays unterschiedlicher Größe.

l = List;
g = Grid@Cases[Outer[l, Sequence @@ MapIndexed[l, #, {2}], 1]~Flatten~(Length[#] - 1), 
x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1] &

Verwendungszweck

g@{{10, 20, 30}, {1, 22, 3}}
g@{{1, 5, 7, 10}, {2, 6, 6, 8, 12}, {4, 5, 9}}
g@{{10, 20, 30}, {1, 2, 3}}
g@{{1, -2, 3}, {-12, -7, 8, 9, 6}, {3, 99, 9}, {100, 10, -23}, {90, 10}}

Erläuterung

Verwenden Sie das erste Beispiel von oben,

a = {{10, 20, 30}, {1, 22, 3}}

MapIndexedLegt Indizes für alle Elemente fest. NB: Mathematica beginnt mit 1 zu zählen. (Wir werden das später berücksichtigen.)

MapIndexed[l, a, {2}]

{{{10, {1, 1}}, {20, {1, 2}}, {30, {1, 3}}, {{1, {2, 1}}, {22, {2, 2}}, {3, {2, 3}}}}

Outergeneriert alle Listen, jeweils einen Kandidaten als Sandwich-Array, und die Indizes ihrer Elemente; %enthält die Ergebnisse der vorherigen Ausgabe. Die Zahlen, 10und 22die I markiert , nachdem sie Ausgang waren, beziehen sich auf eine Sandwich - Anordnung , {10,22}die noch als solche zu identifizieren hat.

Outer[l, Sequence @@ %, 1]~Flatten~(Length[a] - 1)

{{{10, {1, 1}}, {1, {2, 1}}, {{ 10 , {1, 1}}, { 22 , {2, 2}}, {{10, { 1, 1}}, {3, {2, 3}}}, {{20, {1, 2}}, {1, {2, 1}}, {{20, {1, 2}}, {22, {2, 2}}, {{20, {1, 2}}, {3, {2, 3}}, {{30, {1, 3}}, {1, {2, 1}}}, {{30, {1, 3}}, {22, {2, 2}}, {{30, {1, 3}}, {3, {2, 3}}}

Casestestet jedes der oben genannten Elemente, um festzustellen, ob eine LessEqualBeziehung (kleiner oder gleich) gilt. Die unten gezeigten Ergebnisse sind diejenigen Fälle, in denen Array-Sandwiches erkannt wurden. Ich habe noch einmal {10,22}in der Ausgabe hervorgehoben.

Cases[%, x_ /; LessEqual @@ x[[All, 1]] == True]

{{{ 10 , {1, 1}}, { 22 , {2, 2}}, {{20, {1, 2}}, {22, {2, 2}}}

%%bezieht sich auf die vorletzten Ergebnisse. :>, [RuleDelayed] gibt diese Teile der interessierenden Instanzen zurück, nämlich die Indizes der Array-Sandwiches.  -1korrigiert die Tatsache, dass Mathematica Arrays mit 1 anstelle von 0 beginnt. 

Cases[%%, 

x_ /; LessEqual @@ x [[All, 1]] == True:> x [[All, 2, 2]] - 1]

{{0, 1}, {1, 1}}

Gridzeigt die Ergebnisse in einem Raster an. Die erste Zeile 0 1bedeutet, dass das Element 0 aus der ersten Unterliste (dh 10 ) und das Element 1 aus der zweiten Unterliste (dh 22 ) das erste gefundene Sandwich-Array bilden.

Grid@%

0 1

1 1

GolfScript, 51 Zeichen

~:A{,}%{*}*,{A{,.@.@/\@%}%\;}%{:k,,{.A=\k==}%.$=},`

Beispieleingabe (auf stdin):

[[1 5 7 10] [2 6 6 8 12] [4 5 9]]

Beispielausgabe (zu stdout):

[[0 0 0] [0 0 1] [0 0 2] [0 1 2] [1 1 2] [0 2 2] [1 2 2] [0 3 2] [1 3 2] [2 3 2]]

(Beachten Sie, dass die Eingabe muss ohne Komma angegeben werden, sonst wird das Programm höchstwahrscheinlich zum Absturz bringen.)

Ich denke, ich sollte eine Erklärung hinzufügen, wie dieser Code funktioniert:

• ~:Awertet die Eingabe einfach als GolfScript-Code aus und weist das Ergebnis (ein Array von Arrays) zu A. Außerdem bleibt eine Kopie Afür den nächsten Schritt auf dem Stapel.

• {,}%Ersetzt jedes Subarray durch seine Länge und {*}*multipliziert diese Längen miteinander, um die Gesamtzahl der möglichen Sandwichkandidaten zu erhalten. Diese Zahl wird dann von ,in ein Array mit so vielen aufeinanderfolgenden Ganzzahlen ab 0 konvertiert .

• {A{,.@.@/\@%}%\;}%wandelt jede Zahl in einen entsprechenden Sandwich-Kandidaten um (dh ein Array gültiger Indizes in jedes Sub-Array in A). Zum Beispiel, da der Eingang über, 0kartieren würde [0 0 0], 1zu [1 0 0], 2auf [2 0 0], 3zu [3 0 0], 4auf [0 1 0]und so weiter. (Genau herauszufinden, wie der Code dies erreicht, bleibt dem interessierten Leser als Übung.)

• {:k,,{.A=\k==}%.$=},filtert den Sandwich - Kandidaten von jedem von ihnen mit den entsprechenden Elementen der Subanordnungen des Abbilden A(so dass beispielsweise [0 0 0]ergeben würde [1 2 4], [1 0 0]ergeben würde [5 2 4], und so weiter, für die Eingabe oben), ist die resultierende Anordnung Sortieren und mit einer unsortierten Kopie zu vergleichen . Wenn sie gleich sind, wurde das Array bereits sortiert, und somit ist der Kandidat tatsächlich ein Sandwich.

• Schließlich wird `nur das gefilterte Array von Sandwiches in eine Zeichenfolge für die Ausgabe umgewandelt.

R - 89 Zeichen

i=do.call(expand.grid,lapply(x,seq_along))
i[apply(diff(t(mapply(`[`,x,i)))>=0,2,all),]-1

wo

x = list(c(1, 5, 7, 10), c(2, 6, 6, 8, 12), c(4, 5, 9))

oder

x = list(c(10, 20, 30), c(1, 2, 3))

Python, 149 141 140

import itertools as I;x=input();r=range;print[p for p in I.product(*map(r,map(len,x)))if all(x[i][p[i]]<=x[i+1][p[i+1]]for i in r(len(x)-1))]

Python verfügt über eine nützliche itertools-Bibliothek, die Permutationen generieren kann. Dies durchläuft lediglich alle möglichen Permutationen gültiger Indizes und prüft, ob sie die Kriterien erfüllen.

Ich denke, ich kann das kürzer machen und arbeite noch daran.

Bearbeiten: Jetzt alle eine Zeile für Ihr Lesen (in) Bequemlichkeit!

Python 120

f=lambda p,k=0:['%i '%j+m for j,v in enumerate(p[0])if v>=k for m in f(p[1:],v)]if p else['']
print'\n'.join(f(input()))

... denke immer noch, "aufzählen" ist ein sehr langes Wort.

GolfScript (44 Zeichen)

~{.,,]zip}%{{`{+}+1$\/}%\;}*{2%.$=},{(;2%}%`

Gleiches Eingabe- und Ausgabeformat wie Ilmaris Eintrag.

Demo

Grobe Aufschlüsselung:

Ordnen Sie jede Eingabezeile einem Array von Paaren zu [value index]

{.,,]zip}%

Falten Sie ein kartesisches Produkt über die Reihen

{{`{+}+1$\/}%\;}*

Filtern Sie nach denen, deren Einträge 0, 2, 4 usw. nicht abnehmen.

{2%.$=},

Ordnen Sie jeden Eintrag dem 1., 3., 5. usw. zu.

{(;2%}%

Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}