Zufälligkeit macht Spaß. Herausforderungen ohne Sinn machen Spaß.
Schreiben Sie eine Funktion, die bei einer Ganzzahleingabe n
eine Menge (ungeordnet, eindeutig) von genau n
zufälligen Ganzzahlen zwischen 1
und n^2
(einschließlich) ausgibt , sodass die Summe aller Ganzzahlen gleich ist n^2
.
Die Zufälligkeit muss nicht einheitlich sein, vorausgesetzt, jeder gültige Satz weist eine Wahrscheinlichkeit ungleich Null auf.
Die kürzeste Antwort in Bytes (pro Sprache) gewinnt.
Beispiele
Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1
Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3
Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2
Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4
Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8
Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1
Bonusaufgabe: Gibt es eine Formel, mit der die Anzahl der gültigen Permutationen für eine bestimmte Zahl berechnet werden kann n
?
code-golf
random
combinatorics
Skidsdev
quelle
quelle
Antworten:
Brachylog (v2), 15 Bytes (zufällig) oder 13 Bytes (alle Möglichkeiten)
Zufällig
Probieren Sie es online!
Funktionsübergabe (in TIO mit einem Wrapper zu sehen, der daraus ein vollständiges Programm macht).
Erläuterung
Alle Möglichkeiten
Probieren Sie es online!
Funktionsübergabe, die alle möglichen Ausgaben generiert .
Erläuterung
Ich bin ziemlich überrascht, dass dies
∧≜
funktioniert (normalerweise müsste man schreiben,∧~≜
um die Ausgabe und nicht die Eingabe zu brachialisieren), aber es hat sich herausgestellt, dass≜
eine Eingabe = Ausgabe-Annahme vorliegt, sodass es keine Rolle spielt, in welche Richtung Sie gehen starte es.Bonusaufgabe
Um einen Einblick in die Reihenfolge der Anzahl der Möglichkeiten zu bekommen, habe ich einen anderen TIO-Wrapper erstellt , der das Programm auf aufeinanderfolgenden ganzen Zahlen ausführt, um die Reihenfolge der Ausgabezahlen anzugeben:
Eine Reise zu OEIS stellt fest, dass es sich um die bereits bekannte Sequenz A107379 handelt , die ähnlich wie in der Frage beschrieben wurde (anscheinend erhalten Sie dieselbe Sequenz, wenn Sie sie auf ungerade Zahlen beschränken). Die Seite listet verschiedene Formeln für die Sequenz auf (obwohl keine besonders einfach ist; die zweite sieht aus wie eine direkte Formel für den Wert, aber ich verstehe die Notation nicht).
quelle
x^(n*(n-1)/2)
in derProduct_{k=1..n} 1/(1 - x^k)
A≠≜₁ᵐ
), wird die Laufzeit im Durchschnitt erheblich verkürzt .05AB1E , 11 Bytes
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
quelle
Python (2 oder 3), 85 Bytes
Probieren Sie es online!
quelle
R ,
68, 7548 Bytes (zufällig) und 70 Bytes (deterministisch)@ Giuseppe Ablehnungsstichprobenverfahren:
Probieren Sie es online!
Golf Original:
Probieren Sie es online!
Das
*!!1:2
Geschäft ist, die ungerade Weisesample
Tat zu vermeiden , wenn das erste Argument Länge 1 hat.quelle
p
direkte Verwendung als Index, anstatt ihn zu berechnen und erneut zu verwenden, sollten einige Bytes gespart werden.function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}
für 48 ...sample(2,1)
was mit passiertn=2
. Sorep
garantiert nur , dass dies nie geschehen wird. Es könnte einen besseren Weg geben, aber das ging schnell und ich war sauer aufsample
.x*!!1:2
über speichern,rep(x,2)
wenn Ihre Meta-Frage ein Nein erhält.Gelee , 9 Bytes
Probieren Sie es online!
Generieren Sie alle n-Kombinationen der Liste [1..n²], filtern Sie, um die mit der Summe n² beizubehalten, und wählen Sie dann eine zufällige aus.
quelle
Java 10,
250242222 Bytes-20 Bytes dank @nwellnhof .
Pass auf, Java kommt durch ... Es ist 'nur' fünfmal so lang wie die anderen vier Antworten zusammen, also nicht schlecht, denke ich ... rofl.
Es läuft
n=1
durch ,n=25
obwohl (kombiniert) in weniger als 2 Sekunden, so dass ich wahrscheinlich eine modifizierte Version der Geschwindigkeit Version dieser Herausforderung Post würde auch (die in der Sandbox zur Zeit noch ist).Probieren Sie es online aus.
Erläuterung:
Im Pseudocode machen wir folgendes:
1) Erstellen Sie eine Reihe von Größe
n+1
enthalten:0
,n
quadriert undn-1
Menge von Zufallszahlen im Bereich[0, n squared)
2) Sortieren dieses Array
3) Erstellen Sie eine zweite Array der Größe
n
der Vorwärts-Differenzen von Paaren enthaltenDiese ersten drei Schritte wird uns ein Array mit
n
Zufalls Ganzzahlen (im Bereich[0, n squared)
der Summe bis zumn
Quadrat.4a) Wenn nicht alle Zufallswerte eindeutig sind oder einer von ihnen 0 ist: Versuchen Sie es ab Schritt 1 erneut.
4b) Andernfalls: Geben Sie dieses Differenzen-Array als Ergebnis zurück
Wie für den tatsächlichen Code:
quelle
n=25
in weniger als 2 Sekunden ist beeindruckend! Ich muss die Erklärung durchlesen und sehen, wie es funktioniert. Ist es immer noch eine Bruteforce-Methode?[0, n squared)
und dann die Unterschiede zwischen diesen sortierten Zufallswerten (einschließlich führenden0
und nachgestellten Werten) zu berechnenn squared
. Ich bin mir also ziemlich sicher, dass diese Unterschiede auch einheitlich sind Ich bin mir nicht sicher, wie ich das beweisen soll. Einheitlichkeit in der Zufälligkeit ist nicht wirklich mein Fachwissend
oder vermisse ich etwas?Perl 6 , 41 Bytes
Probieren Sie es online!
(1 .. $_²)
ist der Zahlenbereich von 1 bis zum Quadrat der eingegebenen Zahl.pick($_)
wählt zufällig eine bestimmte Teilmenge dieses Bereichs ausxx *
repliziert den vorhergehenden Ausdruck unendlichfirst *.sum == $_²
Wählt die erste dieser Zahlenmengen aus, die dem Quadrat der eingegebenen Zahl entsprechenquelle
Pyth,
1312 BytesProbieren Sie es hier online aus . Beachten Sie, dass der Online-Interpreter bei Eingaben über 5 auf einen MemoryError stößt.
Bearbeiten: Ein Byte wurde gespeichert, indem ein alternativer Ansatz gewählt wurde. Vorherige Version:
Of&qQlT{IT./*
quelle
Python 3 ,
136 134 127 121114 BytesProbieren Sie es online!
Ein Kommentator hat mich korrigiert und dies trifft nun die maximale Tiefe der Rekursion bei f (5) anstelle von f (1). Viel näher dran, eine echte konkurrierende Antwort zu sein.
Ich habe f (5) einmal gesehen und arbeite daran, dies mit shuffle zu implementieren.
Ich habe versucht, einige Lambda-Ausdrücke für zu schreiben
s=...
, aber das hat bei Bytes nicht geholfen. Vielleicht kann jemand anderes etwas damit anfangen:s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)
Vielen Dank an Kevin für das Abschneiden von weiteren 7 Byte.
quelle
f(1)
erreicht hat. Das einzige mögliche Array, das generierbar sein sollte,n=1
ist,[1]
dass hier eine Menge überflüssiger Leerzeichen entfernt werden müssen. Denken Sie daran, dass dies eine Code-Golf-Herausforderung ist. Ziel ist es, den niedrigsten Bytecount zu erreichenrange(1,n)
->range(n)
Ich glaube, sollte den Fehler beheben.return len(s)==n and sum(s)==n*n and s or f(n)
( Probieren Sie es online aus, 114 Bytes ).APL (Dyalog Unicode) , 20 Byte SBCS
Anonymes Präfix Lambda.
Probieren Sie es online!
{
...}
"dfn";⍵
ist ein Argument⍵*2
Quadrieren Sie das Arguments←
zuweisens
(für s quare)⍵?
Finden
zufällige Indizes von 1 ...s
ohne Ersatzc←
zuweisenc
(für c andidate)+/
summiere sies=
vergleichen mits
:
wenn gleichc
Geben Sie den Kandidaten zurück⋄
sonst∇⍵
auf das Argument zurückgreifenquelle
APL (Dyalog Classic) , 18 Byte
Probieren Sie es online!
Verwendet
⎕io←1
⍳
generiert die Zahlen1 2 ... n
(
...)⍣(
...)
wenden Sie die Funktion links weiter an, bis die Funktion rechts true zurückgibt≢
Länge, dhn
≢?≢×≢
wähle zufällign
verschiedene ganze Zahlen zwischen 1 undn
2+.-∘≢
subtrahieren Sie die Länge von jeder Zahl und Summe0=
Wenn die Summe 0 ist, beenden Sie die Schleife, andernfalls versuchen Sie es erneutquelle
MATL ,
1813 BytesProbieren Sie es online!
quelle
Japt, 12 Bytes
Versuch es
quelle
à
sollte also in Ordnung sein.Java (JDK) , 127 Byte
Probieren Sie es online!
Endlosschleife, bis ein Satz mit den Kriterien übereinstimmt.
Ich hoffe du hast die Zeit, denn es ist sehr langweilig! Es kann nicht einmal bis 10 gehen, ohne Zeitüberschreitung.
quelle
if(r.size()==n&s==0)
zuif(r.size()+s==n)
.s>0
die Größe erreicht istn
. Ok, in diesem Fall funktioniert es in der Tat nicht.n
eine Konstante ist, aber leider beides
undr.size()
sind Variablen, die beide unterhalb oder oberhalb sein können0
undn
jeweils.Batch,
182145 BytesErläuterung: Berechnet die minimal und maximal zulässige Auswahl, sofern die Zahlen in absteigender Reihenfolge ausgewählt werden sollen, und wählt einen zufälligen Wert innerhalb des Bereichs aus. Beispiel für eine Eingabe von
4
:quelle
JavaScript,
647291261260259251239 BytesVielen Dank an @Veskah für -10 Bytes in der Originalversion und "Oh ja, du gibst alle Sets aus, während die Challenge die Rückgabe eines zufälligen Sets verlangt."
Probieren Sie es online!
Erstellen Sie ein Array mit
n^2
1-basierten Indizes, sortieren Sie das Array nach dem Zufallsprinzip und schneiden Sie dien
Elemente aus dem Array. Während die Summe der Zufallselemente nicht gleich demn^2
Schleifenarray von Zufallselementen ist; Wenn die Summe der Array-Elemente größer ist alsn^2
und das aktuelle Element-1
ungleich Null ist oder das aktuelle Element-1
nicht im aktuellen Array enthalten ist, subtrahieren Sie1
; Wenn die Summe des Arrays kleiner als istn^2
und das aktuelle Element+1
nicht im Array enthalten ist, fügen Sie1
zum Element hinzu. Wenn die Array-Summe gleichn^2
break loop ist, wird das Array ausgegeben.quelle
k++
while
Schleifen könnten wahrscheinlich auch auf den Hauptteil einer einzelnen Funktion reduziert werden, die Parameter akzeptiert. und könnten bedingte Operatoren (ternäre) für dieif..else
Anweisungen ersetzen ; unter anderen Teilen des Codes, die mehr als wahrscheinlich für Golf angepasst werden könnten; ieg,let
Anweisungen entfernen .if..else
n
?" . Testen , ob der Algorithmus konsistent erwartete Ergebnis für zurückn^2
in einem einzigen Aufruf der Funktion erzeugte Ausgabe - Arrays und gleichzeitig unter Berücksichtigung der Ähnlichkeiten auf diese Frage N-dimensionalen N ^ N - Array mit N gefüllt .Japt , 20 Bytes
Probieren Sie es online!
Nützt extrem stark die "ungleichmäßige" Zufälligkeit aus und gibt fast immer die ersten
n
ungeraden Zahlen aus, die sich zufällig summierenn^2
. Theoretisch kann jede andere gültige Menge ausgegeben werden, obwohl ich dies nur für kleine Mengen bestätigen konnten
.Erläuterung:
quelle
Ruby , 46 Bytes
Probieren Sie es online!
quelle
C (GCC) ,
128125 BytesProbieren Sie es online!
-3 Bytes dank ceilingcat
HINWEIS: Die Wahrscheinlichkeit ist sehr, sehr weit von der Uniform entfernt. Siehe die Erklärung für das, was ich meine und ein besseres Mittel, um zu testen, ob es funktioniert (indem Sie die Verteilung näher an die Gleichmäßigkeit heranführen [aber noch weit davon entfernt]).
Wie?
Die Grundidee ist, nur steigende Zahlen zu wählen, um sich keine Gedanken über Duplikate zu machen. Wann immer wir eine Zahl auswählen, haben wir die Möglichkeit, sie zu überspringen, sofern dies zulässig ist.
x
k
y
x
Trotzdem besteht die Logik darin, eine Chance zu haben, alles zu verwerfen
y
, was die obige Gleichung erfüllt.Der Code
Der Trick , den ich zu einer besseren Test erwähnt der Code beinhaltet Ersatz
rand()&&
mitrand()%2&&
so dass es eine 50-50 Chance , dass eine bestimmte y übersprungen wird, sondern als ein 1RAND_MAX
Chance , dass eine bestimmte y verwendet wird.quelle
p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++;
stattdessen vor){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;}
Sauber , 172 Bytes
Probieren Sie es online!
quelle
Python (2 oder 3), 84 Bytes
Probieren Sie es online!
Erreicht die maximale Rekursionstiefe bei ungefähr l (5)
quelle
Kotlin , 32 Bytes
Probieren Sie es online!
quelle
Mathematica 40 Bytes
quelle
RandomChoice@IntegerPartitions[#^2,{#}]&
Wolfram Language (Mathematica) , 49 Byte
Probieren Sie es online!
Golf Version von @ J42161217.
Wolfram Language (Mathematica) , 62 Byte
Probieren Sie es online!
Wie es funktioniert
Die Antwort auf die Bonusaufgabe
Das heißt, in Mathematica:
Probieren Sie es online!
quelle
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&