Beliebige Zufälligkeit

26

Zufälligkeit macht Spaß. Herausforderungen ohne Sinn machen Spaß.

Schreiben Sie eine Funktion, die bei einer Ganzzahleingabe neine Menge (ungeordnet, eindeutig) von genau nzufälligen Ganzzahlen zwischen 1und 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?

Skidsdev
quelle
2
verwandt , aber ganz anders
Giuseppe
1
(p / s: Wenn Sie einen schnellen Algorithmus haben, aber mehr Bytes
benötigen
1
@EriktheOutgolfer Obwohl es (viel) bessere Möglichkeiten gibt, als alle Mengen zu generieren und eine zufällige zu wählen, sind sie viel schwieriger zu implementieren und wahrscheinlich länger. Behalten Sie sie für die Speed ​​Edition.
user202729
2
Die Anzahl der Sätze ist OEIS A107379 .
Nwellnhof
1
Es ist beides. Siehe den Kommentar "Auch die Anzahl der Partitionen von n ^ 2 in n verschiedene Teile."
Nwellnhof

Antworten:

9

Brachylog (v2), 15 Bytes (zufällig) oder 13 Bytes (alle Möglichkeiten)

Zufällig

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Probieren Sie es online!

Funktionsübergabe (in TIO mit einem Wrapper zu sehen, der daraus ein vollständiges Programm macht).

Erläuterung

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

Alle Möglichkeiten

~lℕ₁ᵐ<₁.+√?∧≜

Probieren Sie es online!

Funktionsübergabe, die alle möglichen Ausgaben generiert .

Erläuterung

~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

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:

1,1,3,9,30,110,436,1801,7657,33401

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

ais523
quelle
Die zweite Formel ist "der Koeffizient x^(n*(n-1)/2)in der Product_{k=1..n} 1/(1 - x^k)
Reihenexpansion
Wenn Sie die Einschränkung "Alle verschiedenen" vor dem zufälligen Markierungsschritt platzieren (z. B. A≠≜₁ᵐ), wird die Laufzeit im Durchschnitt erheblich verkürzt .
Fatalize
Ich verstehe nicht, warum du dies zu einem Community-Wiki gemacht hast. Dies ist eine archaische Methode, um bearbeitbare Beiträge zu erstellen, bevor sie bearbeitet werden konnten.
Pipe
7

05AB1E , 11 Bytes

nÅœʒDÙQ}sùΩ

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

n             # Take the square of the (implicit) input
              #  i.e. 3 → 9
 Ŝ           # Get all integer-lists using integers in the range [1, val) that sum to val
              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]
   ʒ   }      # Filter the list to only keep lists with unique values:
    D         # Duplicate the current value
     Ù        # Uniquify it
              #  i.e. [2,2,5] → [2,5]
      Q       # Check if it's still the same
              #  i.e. [2,2,5] and [2,5] → 0 (falsey)
        s     # Swap to take the (implicit) input again
         ù    # Only leave lists of that size
              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3
              #   → [[1,2,6],[1,3,5],[2,3,4]]
          Ω   # Pick a random list from the list of lists (and output implicitly)
Kevin Cruijssen
quelle
5

R , 68, 75 48 Bytes (zufällig) und 70 Bytes (deterministisch)

@ Giuseppe Ablehnungsstichprobenverfahren:

function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Probieren Sie es online!

Golf Original:

function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Probieren Sie es online!

Das *!!1:2Geschäft ist, die ungerade Weise sampleTat zu vermeiden , wenn das erste Argument Länge 1 hat.

ngm
quelle
@ Giuseppe "behoben" :-)
ngm
Sehr schön. Durch die pdirekte Verwendung als Index, anstatt ihn zu berechnen und erneut zu verwenden, sollten einige Bytes gespart werden.
Giuseppe
1
Ich habe auch function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}für 48 ...
Giuseppe
1
@ J.Doe um das Problem beim Anrufen so etwas zu vermeiden sample(2,1)was mit passiert n=2. So repgarantiert nur , dass dies nie geschehen wird. Es könnte einen besseren Weg geben, aber das ging schnell und ich war sauer auf sample.
ngm 20.11.18 Uhr
1
Sie können ein Byte mit x*!!1:2über speichern, rep(x,2)wenn Ihre Meta-Frage ein Nein erhält.
J.Doe
4

Gelee , 9 Bytes

²œcS=¥Ƈ²X

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.

user202729
quelle
4

Java 10, 250 242 222 Bytes

import java.util.*;n->{for(;;){int i=n+1,r[]=new int[i],d[]=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

-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=1durch , n=25obwohl (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+1enthalten: 0, nquadriert und n-1Menge von Zufallszahlen im Bereich [0, n squared)
2) Sortieren dieses Array
3) Erstellen Sie eine zweite Array der Größe nder Vorwärts-Differenzen von Paaren enthalten
Diese ersten drei Schritte wird uns ein Array mit nZufalls Ganzzahlen (im Bereich [0, n squared)der Summe bis zum nQuadrat.
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:

import java.util.*;      // Required import for HashSet and Arrays
n->{                     // Method with int parameter and Set return-type
  for(;;){               //  Loop indefinitely
    int i=n+1,           //   Set `i` to `n+1`
        r[]=new int[i];  //   Create an array of size `n+1`
    var S=new HashSet(); //   Result-set, starting empty
    for(r[n<2?           //   If `n` is 1:
           0             //    Set the first item in the first array to:
          :              //   Else:
           1]            //    Set the second item in the first array to:
             =n*n;       //   `n` squared
        i-->2;)          //   Loop `i` in the range [`n`, 2]:
      r[i]=              //    Set the `i`'th value in the first array to:
           (int)(Math.random()*n*n); 
                         //     A random value in the range [0, `n` squared)
    for(Arrays.sort(r),  //   Sort the first array
        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:
      S.add(             //    Add to the Set:
        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array
    if(!S.contains(0)    //   If the Set does not contain a 0
       &S.size()==n)     //   and its size is equal to `n`:
      return S;}}        //    Return this Set as the result
                         //   (Implicit else: continue the infinite loop)
Kevin Cruijssen
quelle
1
n=25in weniger als 2 Sekunden ist beeindruckend! Ich muss die Erklärung durchlesen und sehen, wie es funktioniert. Ist es immer noch eine Bruteforce-Methode?
Skidsdev
Ist es einheitlich? -
user202729
@ user202729 Obwohl ich nicht sicher bin, wie ich es beweisen soll, denke ich, dass es so ist. Das Java-Builtin ist einheitlich und verwendet es, um zuerst Zufallswerte im Bereich abzurufen [0, n squared)und dann die Unterschiede zwischen diesen sortierten Zufallswerten (einschließlich führenden 0und nachgestellten Werten) zu berechnen n 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 Fachwissen
Kevin Cruijssen
3
Sie lesen nie aus dem Unterschiedsfeld doder vermisse ich etwas?
Nwellnhof
1
Ich bin mit meiner 127-Byte-Lösung ein
Olivier Grégoire
4

Perl 6 , 41 Bytes

{first *.sum==$_²,(1..$_²).pick($_)xx*}

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 aus
  • xx * repliziert den vorhergehenden Ausdruck unendlich
  • first *.sum == $_² Wählt die erste dieser Zahlenmengen aus, die dem Quadrat der eingegebenen Zahl entsprechen
Sean
quelle
40 Bytes
Jo King
2

Pyth, 13 12 Bytes

Ofq*QQsT.cS*

Probieren Sie es hier online aus . Beachten Sie, dass der Online-Interpreter bei Eingaben über 5 auf einen MemoryError stößt.

Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())
                 Trailing QQQ inferred
          S*QQQ   [1-Q*Q]
        .c    Q   All combinations of the above of length Q, without repeats
 f                Keep elements of the above, as T, where the following is truthy:
      sT            Is the sum of T...
  q                 ... equal to...
   *QQ              ... Q*Q?
O                 Choose a random element of those remaining sets, implicit print

Bearbeiten: Ein Byte wurde gespeichert, indem ein alternativer Ansatz gewählt wurde. Vorherige Version: Of&qQlT{IT./*

Sok
quelle
2

Python 3 , 136 134 127 121 114 Bytes

from random import*
def f(n):
	s={randint(1,n*n)for _ in range(n)}
	return len(s)==n and sum(s)==n*n and s or f(n)

Probieren 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.

Gigaflop
quelle
1
Dies verwendet also eine Rekursion, um die Menge zu "regenerieren", wenn die generierte ungültig ist. Auf jeden Fall stimmt etwas mit Ihrem Code nicht, wenn er die Rekursionstiefe von f(1)erreicht hat. Das einzige mögliche Array, das generierbar sein sollte, n=1ist, [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 erreichen
Skidsdev,
1
range(1,n)-> range(n)Ich glaube, sollte den Fehler beheben.
Jonathan Allan
1
Dies sollte Ihren Fehler beheben und auch überflüssige Leerzeichen entfernen. Ich stelle mir vor, es gibt viel mehr Platz zum Golfen
Skidsdev 20.11.18
1
Obwohl sich die Rekursion von 5 auf 4 leicht verschlechtert, können Sie Ihre beiden return-Anweisungen wie folgt kombinieren: return len(s)==n and sum(s)==n*n and s or f(n)( Probieren Sie es online aus, 114 Bytes ).
Kevin Cruijssen
1
Sie können alles in einer Zeile haben. 111 Bytes
Jo King
2

APL (Dyalog Unicode) , 20 Byte SBCS

Anonymes Präfix Lambda.

{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

Probieren Sie es online!

{... } "dfn"; ist ein Argument

⍵*2 Quadrieren Sie das Argument

s← zuweisen s(für s quare)

⍵? Finde nzufällige Indizes von 1 ... sohne Ersatz

c← zuweisen c(für c andidate)

+/ summiere sie

s= vergleichen mit s

: wenn gleich

  c Geben Sie den Kandidaten zurück

 sonst

  ∇⍵ auf das Argument zurückgreifen

Adam
quelle
Hast du meine und die 18 Bytes von H.PWiz gesehen ?
25.
@ngn Nein, natürlich nicht, aber ich habe vor dem Posten überprüft, ob keine APL-Lösung veröffentlicht wurde. Warum hat keiner von Ihnen
Adám
Nun, wenn ich es einmal golfen und es dem Obstgarten gezeigt habe, gibt es kaum einen Anreiz, es zu posten :)
ngn
@ngn Für dich, nein, aber für mich gibt es.
Adám
1
auf jeden fall, und ich denke, du machst einen tollen job, um apl hier bekannt zu machen. Ich habe nur dafür gesorgt, dass Sie wissen, dass kürzere Lösungen gefunden wurden, und es ist wahrscheinlich besser, eine davon (oder eine Variante) zu erklären
ngn
2

APL (Dyalog Classic) , 18 Byte

(≢?≢×≢)⍣(0=+.-∘≢)⍳

Probieren Sie es online!

Verwendet ⎕io←1

generiert die Zahlen 1 2 ... n

(... )⍣(... )wenden Sie die Funktion links weiter an, bis die Funktion rechts true zurückgibt

Länge, dh n

≢?≢×≢wähle zufällig nverschiedene ganze Zahlen zwischen 1 und n2

+.-∘≢ subtrahieren Sie die Länge von jeder Zahl und Summe

0= Wenn die Summe 0 ist, beenden Sie die Schleife, andernfalls versuchen Sie es erneut

ngn
quelle
1

MATL , 18 13 Bytes

`xGU:GZrtsGU-

Probieren Sie es online!

`	# do..while:
x	# delete from stack. This implicitly reads input the first time
	# and removes it. It also deletes the previous invalid answer.
GU:	# paste input and push [1...n^2]
GZr	# select a single combination of n elements from [1..n^2]
tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top
Giuseppe
quelle
Ich würde dies nicht in R - Zufallszeichen versuchen, aber es wird fast nie ein gültiges Programm erstellt.
ngm
@ngm hahaha ich nehme an eine erklärung ist angebracht.
Giuseppe
1

Japt, 12 Bytes

²õ àU ö@²¥Xx

Versuch es

                 :Implicit input of integer U
²                :U squared
 õ               :Range [1,U²]
   àU            :Combinations of length U
      ö@         :Return a random element that returns true when passed through the following function as X
        ²        :  U squared
         ¥       :  Equals
          Xx     :  X reduced by addition
Zottelig
quelle
Laut einem Kommentar des OP ist die Reihenfolge der Elemente in der Ausgabe irrelevant, àsollte also in Ordnung sein.
Kamil Drakari
Vielen Dank, @KamilDrakari. Aktualisiert.
Shaggy
1

Java (JDK) , 127 Byte

n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

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.

Olivier Grégoire
quelle
Sie können Golf 3 Bytes durch Änderung if(r.size()==n&s==0)zu if(r.size()+s==n).
Kevin Cruijssen
@ KevinCruijssen Ich habe auch darüber nachgedacht, aber nein, ich kann nicht, weil s -1 sein könnte und n Größe sein könnte () - 1.
Olivier Grégoire
Warten Sie, Sie fügen dem Set so lange Elemente hinzu, bis s>0die Größe erreicht ist n. Ok, in diesem Fall funktioniert es in der Tat nicht. neine Konstante ist, aber leider beide sund r.size()sind Variablen, die beide unterhalb oder oberhalb sein können 0und njeweils.
Kevin Cruijssen
1

Batch, 182 145 Bytes

@set/an=%1,r=n*n,l=r+1
@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

Erlä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:

  • Wir beginnen mit 16 links. Wir können nicht 11 oder mehr auswählen, da die verbleibenden 3 Picks mindestens 6 hinzufügen müssen. Wir müssen auch mindestens 6 auswählen, da die verbleibenden 3 Picks nur 9 hinzufügen können, was nicht der Fall ist, wenn wir nur 5 auswählen genug für 16. Wir wählen einen zufälligen Wert von 6 bis 10, sagen wir 6.
  • Wir haben 10 übrig. Wir können nicht 8 oder mehr auswählen, da die verbleibenden 2 Picks mindestens 3 ergeben müssen. Zufälligerweise können wir nicht 6 oder mehr auswählen, da wir beim letzten Mal 6 ausgewählt haben. Wir müssen auch mindestens 5 auswählen, denn wenn wir nur 4 auswählen, können die verbleibenden 2 Auswahlen nur zu 5 addieren, was eine Gesamtsumme von 15 ergibt. Wir wählen einen zufälligen Wert von 5 bis 5, z. B. 5 (!).
  • Wir haben 5 übrig. Wir können nicht 5 oder mehr auswählen, da die verbleibende Auswahl mindestens 1 ergeben muss, und auch, weil wir beim letzten Mal 5 ausgewählt haben. Wir müssen auch mindestens 3 auswählen, denn wenn wir nur 2 auswählen, kann die verbleibende Auswahl nur 1 sein, was einer Gesamtsumme von 14 entspricht. Wir wählen einen zufälligen Wert von 3 bis 4, z. B. 4.
  • Wir haben 1 übrig. Wie sich herausstellt, wählt der Algorithmus einen Bereich von 1 bis 1 und wir wählen 1 als endgültige Zahl.
Neil
quelle
1

JavaScript, 647 291 261 260 259 251 239 Bytes

Vielen 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."

(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

Probieren Sie es online!

Erstellen Sie ein Array mit n^21-basierten Indizes, sortieren Sie das Array nach dem Zufallsprinzip und schneiden Sie die nElemente aus dem Array. Während die Summe der Zufallselemente nicht gleich dem n^2Schleifenarray von Zufallselementen ist; Wenn die Summe der Array-Elemente größer ist als n^2und das aktuelle Element -1ungleich Null ist oder das aktuelle Element -1nicht im aktuellen Array enthalten ist, subtrahieren Sie 1; Wenn die Summe des Arrays kleiner als ist n^2und das aktuelle Element +1nicht im Array enthalten ist, fügen Sie 1zum Element hinzu. Wenn die Array-Summe gleich n^2break loop ist, wird das Array ausgegeben.

guest271314
quelle
1
637 Bytes durch Ziehen von z.join in eine Variable undk++
Veskah
@Veskah Die zwei whileSchleifen könnten wahrscheinlich auch auf den Hauptteil einer einzelnen Funktion reduziert werden, die Parameter akzeptiert. und könnten bedingte Operatoren (ternäre) für die if..elseAnweisungen ersetzen ; unter anderen Teilen des Codes, die mehr als wahrscheinlich für Golf angepasst werden könnten; ieg, letAnweisungen entfernen .
guest271314
@Veskah 601 Bytes, ohne ternären Ersatz fürif..else
guest271314
1
Oh ja, du gibst alle Sets aus, während die Challenge die Rückgabe eines zufälligen Sets verlangt (siehe OP-Kommentare für weitere Details)
Veskah,
@Veskah Muss die Herausforderung und die Beispiele falsch interpretiert haben oder war zu sehr auf die Lösung dieses Teils der Frage konzentriert " Bonusaufgabe: Gibt es eine Formel zur Berechnung der Anzahl der gültigen Permutationen für eine bestimmte Aufgaben ?" . Testen , ob der Algorithmus konsistent erwartete Ergebnis für zurück n^2in 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 .
guest271314
0

Japt , 20 Bytes

²õ ö¬oU íUõ+)Õæ@²¥Xx

Probieren Sie es online!

Nützt extrem stark die "ungleichmäßige" Zufälligkeit aus und gibt fast immer die ersten nungeraden Zahlen aus, die sich zufällig summieren n^2. Theoretisch kann jede andere gültige Menge ausgegeben werden, obwohl ich dies nur für kleine Mengen bestätigen konnte n.

Erläuterung:

²õ                      :Generate the range [1...n^2]
   ö¬                   :Order it randomly
     oU                 :Get the last n items
        í   )Õ          :Put it in an array with...
         Uõ+            : The first n odd numbers
              æ_        :Get the first one where...
                  Xx    : The sum
                ²¥      : equals n^2
Kamil Drakari
quelle
0

C (GCC) , 128 125 Bytes

p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

Probieren 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.

xky

y+(y+1)+(y+2)+...
x
k(k+1)2+k(y+1)+y<x

Trotzdem besteht die Logik darin, eine Chance zu haben, alles zu verwerfen y, was die obige Gleichung erfüllt.

Der Code

p(_){printf("%d ",_);}  // Define print(int)
f(n,x,y,i){             // Define f(n,...) as the function we want
    x=n*n;              // Set x to n^2
    y=1;                // Set y to 1
    for(i=0;++i<n;){    // n-1 times do...
        while(rand()&&  // While rand() is non-zero [very very likely] AND
            (n-i)*      // (n-i) is the 'k' in the formula
            (n-i+1)/2+  // This first half takes care of the increment
            (n-i)*(y+1) // This second half takes care of the y+1 starting point
            +y<x)       // The +y takes care of the current value of y
        y++;            // If rand() returned non-zero and we can skip y, do so
    p(y);               // Print y
    x-=y++;             // Subtract y from the total and increment it
    }p(x);}             // Print what's left over.

Der Trick , den ich zu einer besseren Test erwähnt der Code beinhaltet Ersatz rand()&&mit rand()%2&&so dass es eine 50-50 Chance , dass eine bestimmte y übersprungen wird, sondern als ein 1 RAND_MAXChance , dass eine bestimmte y verwendet wird.

LambdaBeta
quelle
Ich würde es lieben, wenn jemand meine Mathematik auf Konsistenz überprüfen würde. Ich frage mich auch, ob diese Art von Lösung die Herausforderung einer gleichmäßigen Zufallsgeschwindigkeit einfach machen könnte. Die Formel legt eine obere und untere Grenze für die Antwort fest. Ergibt eine einheitliche Zufallszahl in diesem Bereich einheitliche Zufallsergebnisse? Ich verstehe nicht warum nicht - aber ich habe in einer Weile nicht mehr viel Kombinatorik gemacht.
LambdaBeta
Schlagen Sie 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++;}
ceilingcat
@ceilingcat Ich liebe diese kleinen Verbesserungen, die Sie finden. Ich konzentriere mich immer so sehr auf den Gesamtalgorithmus, dass ich vergesse, ihn für die Implementierung zu optimieren (ich gehe im Grunde genommen in den Autopilot-Golfmodus, sobald ich eine nicht-golfende Quelle habe, die funktioniert - daher vermisse ich viele Einsparungen)
LambdaBeta
Hey, es sind nicht nur Sie, die diese Syntax-Golfs haben. Ich finde kleine Verbesserungen in vielen C / C ++ - Antworten wie diesen (außer in Ihren, @ceilingcat schnappt sich diese normalerweise).
Zacharý
Ja, mir ist aufgefallen, dass Sie beide wahrscheinlich die aktivsten C / C ++ - Putter sind (können wir Putten verwenden, um die Golfanalogie auf die letzten paar Schläge zu erweitern? Warum nicht!). Es beeindruckt mich immer wieder, dass Sie den Golf-Code sogar gut genug verstehen, um ihn zu verbessern.
LambdaBeta
0

Sauber , 172 Bytes

import StdEnv,Math.Random,Data.List
? ::!Int->Int
?_=code{
ccall time "I:I"
}
$n=find(\s=length s==n&&sum s==n^2)(subsequences(nub(map(inc o\e=e rem n^2)(genRandInt(?0)))))

Probieren Sie es online!

Οurous
quelle
0

Python (2 oder 3), 84 Bytes

from random import*;l=lambda n,s=[]:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

Probieren Sie es online!

Erreicht die maximale Rekursionstiefe bei ungefähr l (5)

ArBo
quelle
0

Mathematica 40 Bytes

RandomChoice[IntegerPartitions[n^2, {n}]]
David G. Stork
quelle
1
Zuallererst ist es n ^ 2, nicht 2 ^ n. Zweitens muss Ihr Programm eine Funktion und auch eine Golf-Funktion sein. Versuchen Sie dies RandomChoice@IntegerPartitions[#^2,{#}]&
J42161217
1
Das Ergebnis muss ebenfalls (ungeordnet, eindeutig) sein, aber diese Funktion schlägt in beiden
Fällen
0

Wolfram Language (Mathematica) , 49 Byte

(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

Probieren Sie es online!

Golf Version von @ J42161217.


Wolfram Language (Mathematica) , 62 Byte

Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

Probieren Sie es online!

Wie es funktioniert

n2nn2-(n2-n)/2=(n2+n)/20n-1n-10


Die Antwort auf die Bonusaufgabe

Bonusaufgabe: Gibt es eine Formel, mit der die Anzahl der gültigen Permutationen für eine bestimmte Zahl berechnet werden kann n?

peinrt(n,k)nk

peinrt(n,k)=peinrt(n-1,k-1)+peinrt(n-k,k)

peinrt(n,1)=1n<kpeinrt(n,k)=0

peinrt(n2+n2,n)

Das heißt, in Mathematica:

Length@IntegerPartitions[#*(#+1)/2,{#}]&

Probieren Sie es online!

Bubbler
quelle
Dies ist Code Golf .. 49 Bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
J42161217