Überblick

In dieser Herausforderung besteht Ihre Aufgabe darin, eine monotone mathematische Funktion zwischen zwei Mengen zufällig zu generieren .

Eingang

Ihre Eingaben sind zwei positive ganze Zahlen sund n.

Nachdem Sie diese Eingaben erhalten haben, soll Ihr Programm eine zufällige mathematische Funktion faus der Menge bis erzeugen . Mit anderen Worten, ist eine "Regel", die ein -Tupel von Ganzzahlen zwischen und aufnimmt und eine solche Ganzzahl zurückgibt. Darüber hinaus sollte im folgenden Sinne monoton sein . Wenn und zwei Tupel sind, die für jede Koordinate gelten , dann .{0,1,...,s-1}n{0,1,...,s-1}fn0s-1fABnA[i] ≥ B[i]if(A) ≥ f(B)

Die genaue Verteilung der monotonen Funktionen fspielt keine Rolle, solange für jede dieser Funktionen eine positive Wahrscheinlichkeit der Erzeugung besteht (unter der Annahme eines perfekten RNG).

Ausgabe

Ihr Output soll eine Aufzählung der Inputs und Outputs von sein f. Es muss alle n-tupel von ganzen Zahlen zwischen 0und s-1in einer bestimmten Reihenfolge enthalten, gefolgt von der entsprechenden Ausgabe von f. Das genaue Ausgabeformat ist flexibel (in Grenzen).

Beispiele

Die Eingaben s = 3und n = 2können die Ausgabe erzeugen

(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2

Es enthält alle Paare über die Menge {0, 1, 2}genau einmal, und jedem folgt sein fWert. Die Monotonie-Bedingung ist ebenfalls erfüllt. Die Tupel werden hier in lexikografischer Reihenfolge angegeben, dies ist jedoch nicht erforderlich.

Als weiteres Beispiel s = 2und n = 4könnte produzieren

(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1

Das Folgende sind alle möglichen Ausgaben für s = 2und n = 2(bis zur Neuordnung der Tupel); Ihr Programm sollte zufällig eines davon ausgeben:

(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1

Regeln und Wertung

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Code mit Erklärung wird bevorzugt.

Es gibt keine Einschränkungen hinsichtlich der Zeitkomplexität, aber ich werde einen Bonus von -15% gewähren, wenn Ihre Lösung immer in einer bestimmten Zeit fertig ist (abhängig von den Eingaben und unter der Annahme eines perfekten RNG, das in konstanter Zeit ausgeführt wird). .

Pyth, 35 Bytes (38 - 15% = 31,45 weiter unten)

#I!sm><FhMds<MCeMd^JC,mOQK^UQvzK2JB

Demonstration

Die Eingabe erfolgt im Format:

n
s

Die Ausgabe erfolgt im Format:

[[value, tuple], [value, tuple], ...]

Generiert einfach zufällige Möglichkeiten und testet sie.

Alternative 37-Byte-Version, von der ich glaube, dass sie für den Bonus geeignet ist:

Of!sm><FhMds<MCeMd^T2mC,d^UQvz^UQ^Qvz

Demonstration

Dies beginnt mit der Erzeugung aller möglichen monotonen Funktionen und gibt dann eine zufällige aus. Es ist viel langsamer und rundet ab 2,2.

CJam, 40 Bytes - 15% = 34 Bytes

q~1$\m*\1$,m*{W$\.+2m*{:.<2b}%1&!},mR]zp

Dieser Ansatz generiert alle gültigen Funktionen und wählt sie dann nach dem Zufallsprinzip aus. Die Laufzeit beträgt mindestens O (s ^{2s n} ) , ist jedoch für eine bestimmte Eingabe konstant.

Ich bezweifle, dass dies das Ziel des OP ist, aber es wird garantiert in einer bestimmten Zeit (abhängig von den Eingaben) [...] beendet und qualifiziert sich daher für den Bonus.

Probieren Sie es online im CJam-Interpreter aus .

Julia, 64 Byte (-15% = 54,4)

g(s,n)=(K=rand(0:s-1,ntuple(n,i->s));for i=1:n K=sort(K,i)end;K)

Ungolfed:

function g(s,n)
  # Generates a random n-dimensional array with s per dimension
  # and all values being integers between 0 and s-1
  K=rand(0:s-1,ntuple(n,i->s))
  # Loop over the various dimensions
  for i=1:n
    # Sort in the current dimension
    K=sort(K,i)
  end
  return K
end

Dies wird schnell ausgeführt, wobei das einzige mögliche Problem darin besteht, dass der Speicher für s groß genug ist und n (g (10,10) ein 10 ^ 10-Array erzeugen muss, sodass der Speicher offensichtlich knapp wird - selbst wenn es sich um eine Zahl handelt ein Byte, das sind 10 Gigabyte Daten).

Bei der Ausgabe handelt es sich um eine 1-basierte Indizierung. Um das Ergebnis für eine bestimmte Eingabe zu ermitteln, müssen Sie zu jedem Eingabewert einen hinzufügen. Um zum Beispiel f (1,2,6,0,3) zu finden, müssen Sie untersuchen K[2,3,7,1,4].