Dowolność przypadkowa

26

Losowość to dobra zabawa. Wyzwania bez sensu są zabawne.

Napisz funkcję, która, biorąc pod uwagę całkowitą wejście n, wyjście wola do zestawu (nieuporządkowana, niepowtarzalny) z dokładnie nlosowych liczb całkowitych między 1a n^2(włącznie) takich, że suma wszystkich liczb całkowitych jest równy n^2.

Losowość nie musi być jednorodna, pod warunkiem że każdy prawidłowy zestaw ma niezerową szansę wystąpienia.

Najkrótsza odpowiedź w bajtach (na każdy język) wygrywa.

Przykłady

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

Zadanie premiowe: Czy istnieje wzór do obliczania liczby prawidłowych permutacji dla danego n?

Skidsdev
źródło
2
powiązane , ale zupełnie inne
Giuseppe,
1
(p / s: jeśli masz szybki algorytm, ale zajmuje on więcej bajtów, rozważ poczekanie, aż opublikuje go szybkie wydanie (obecnie w piaskownicy)).
user202729,
1
@EriktheOutgolfer Chociaż istnieją (znacznie) lepsze sposoby niż generowanie wszystkich zestawów i wybranie losowego zestawu, są one znacznie trudniejsze do wdrożenia i prawdopodobnie dłużej. Zachowaj je do edycji Speed.
user202729,
2
Liczba zestawów to OEIS A107379 .
nwellnhof,
1
To jedno i drugie. Patrz komentarz „Również liczba partycji n ^ 2 na n różnych części”.
nwellnhof,

Odpowiedzi:

9

Brachylog (v2), 15 bajtów (losowo) lub 13 bajtów (wszystkie możliwości)

Losowy

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

Wypróbuj online!

Podanie funkcji (widoczne w TIO z opakowaniem czyniącym z niego pełny program).

Wyjaśnienie

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

Wszystkie możliwości

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

Wypróbuj online!

Podanie funkcji, które generuje wszystkie możliwe wyniki.

Wyjaśnienie

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

Jestem dość zaskoczony, że to ∧≜działa (normalnie musiałbyś pisać ∧~≜, aby brutalnie wymusić wyjście, a nie wejście), ale okazuje się, że ma założenie wejściowe = wyjście, więc nie ma znaczenia, w którą stronę Uruchom.

Zadanie premiowe

Aby uzyskać wgląd w sekwencję liczby możliwości, stworzyłem inne opakowanie TIO, które uruchamia program na kolejnych liczbach całkowitych w celu podania sekwencji liczb wyjściowych:

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

Podróż do OEIS odkrywa, że ​​jest to już znana sekwencja, A107379 , opisana podobnie jak w pytaniu (najwyraźniej otrzymujesz tę samą sekwencję, jeśli ograniczysz ją do liczb nieparzystych). Strona zawiera kilka wzorów dla sekwencji (choć żadna nie jest szczególnie prosta; druga wygląda jak bezpośrednia formuła wartości, ale nie rozumiem zapisu).

ais523
źródło
Druga formuła to „współczynnik x^(n*(n-1)/2)rozszerzania szeregowego Product_{k=1..n} 1/(1 - x^k)” (niestety wcale nie bezpośredni)
user202729,
Wprowadzenie ograniczenia „całkowicie różne” przed etapem losowej etykietowania (np. A≠≜₁ᵐ) Powoduje, że czas wykonywania jest średnio znacznie szybszy.
Fatalize
Nie rozumiem, dlaczego stworzyłeś to wiki społeczności. To archaiczny sposób na edytowanie postów, zanim możliwe było ich edytowanie.
rura
7

05AB1E , 11 bajtów

nÅœʒDÙQ}sùΩ

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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
źródło
5

Python (2 lub 3), 85 bajtów

def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)
from random import*

Wypróbuj online!

Jonathan Allan
źródło
5

R , 68, 75 48 bajtów (losowo) i 70 bajtów (deterministycznie)

@ Metoda próbkowania odrzucenia Giuseppe:

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

Wypróbuj online!

Oryginał golfa:

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

Wypróbuj online!

*!!1:2Firma jest uniknięcie dziwny sposób sampledziałania, gdy pierwszy argument ma długość 1.

ngm
źródło
@Giuseppe „fixed” :-)
ngm
bardzo dobrze. użycie pbezpośrednio jako indeksu zamiast obliczania go i ponowne użycie powinno zaoszczędzić trochę bajtów.
Giuseppe,
1
Mam też function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}48 ...
Giuseppe,
1
@ J.Doe, aby uniknąć problemu podczas dzwonienia w podobny sposób, sample(2,1)co się dzieje n=2. Więc reptylko gwarantuje, że tak się nigdy nie stanie. Może być lepszy sposób, ale to było szybkie i byłem wściekły sample.
ngm
1
Możesz zapisać bajt z x*!!1:2nad, rep(x,2)jeśli twoje meta-pytanie otrzyma odpowiedź przeczącą.
J.Doe
4

Galaretka , 9 bajtów

²œcS=¥Ƈ²X

Wypróbuj online!

Wygeneruj wszystkie n-kombinacje z listy [1..n²], przefiltruj, aby zachować te z sumą n², a następnie wybierz losową.

użytkownik202729
źródło
4

Java 10, 250 242 222 bajtów

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 bajtów dzięki @nwellnhof .

Uważaj, nadchodzi Java. Jest „tylko” pięć razy tak długo, jak pozostałe cztery odpowiedzi łącznie, więc nieźle jak sądzę… rofl.
To działa n=1poprzez n=25(łącznie) w czasie krótszym niż 2 sekundy, choć, więc prawdopodobnie będę pisać zmodyfikowaną wersję do wersji to wyzwanie prędkości (który jest obecnie jeszcze w Sandbox), jak również.

Wypróbuj online.

Wyjaśnienie:

W pseudo-kodzie wykonujemy następujące czynności:

1) Generowanie tablicę wielkości n+1zawierający: 0, nkwadratu, a n-1ilość losowych liczb całkowitych w przedziale [0, n squared)
2) Sortuj tej tablicy
3) tworzą drugą tablicę wielkości nzawierający forward różnic par
Te pierwsze trzy kroki dadzą nam tablicę zawierającą nlosowe liczby całkowite (w zakresie [0, n squared)sumy do nkwadratu.
4a) Jeśli nie wszystkie losowe wartości są unikalne lub jedna z nich ma wartość 0: spróbuj ponownie od kroku 1
4b) W przeciwnym razie zwróć tablicę różnic w wyniku

Co do faktycznego kodu:

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
źródło
1
n=25w mniej niż 2 sekundy robi wrażenie! Będę musiał przeczytać wyjaśnienie i zobaczyć, jak to działa. Czy to wciąż metoda bruteforce?
Skidsdev,
Czy to jest jednolite? -
user202729,
@ user202729 Chociaż nie jestem pewien, jak to udowodnić, myślę, że tak. Wbudowane środowisko Java jest jednolite i wykorzystuje to, aby [0, n squared)najpierw uzyskać losowe wartości z zakresu , a następnie oblicza różnice między tymi posortowanymi wartościami losowymi (w tym wiodącymi 0i końcowymi n squared. Więc jestem pewien, że te różnice są również jednolite. Ale znowu , Nie jestem pewien, jak to udowodnić. Jednorodność losowości nie jest tak naprawdę moją wiedzą specjalistyczną
Kevin Cruijssen,
3
Nigdy nie czytasz z tablicy różnic dczy coś mi brakuje?
nwellnhof,
1
Jestem trochę zadowolony z rozwiązania 127 bajtów : D
Olivier Grégoire,
4

Perl 6 , 41 bajtów

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

Wypróbuj online!

  • (1 .. $_²) to zakres liczb od 1 do kwadratu liczby wejściowej
  • .pick($_) losowo wybiera odrębny podzbiór tego zakresu
  • xx * nieskończenie replikuje poprzednie wyrażenie
  • first *.sum == $_² wybiera pierwszy z tych zestawów liczb, który sumuje się do kwadratu liczby wejściowej
Sean
źródło
40 bajtów
Jo King
2

Pyth, 13 12 bajtów

Ofq*QQsT.cS*

Wypróbuj online tutaj . Zauważ, że interpreter online napotyka błąd MemoryError dla danych wejściowych większych niż 5.

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

Edycja: zapisano bajt, przyjmując alternatywne podejście. Poprzednia wersja: Of&qQlT{IT./*

Sok
źródło
2

Python 3 , 136 134 127 121 114 bajtów

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)

Wypróbuj online!

Komentator mnie poprawił, a teraz osiąga maksymalną głębokość rekurencji na f (5) zamiast f (1). Znacznie bliżej bycia prawdziwą konkurencyjną odpowiedzią.

Widziałem to zrobić f (5) jeden raz , a ja pracuję nad próbując wdrożyć to z shuffle.

Próbowałem utworzyć wyrażenia lambda s=..., ale to nie pomogło w bajtach. Może ktoś inny może coś z tym zrobić: s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)

Dzięki Kevinowi za golenie kolejnych 7 bajtów.

Gigaflop
źródło
1
Czy to wykorzystuje rekurencję do „regeneracji” zestawu, jeśli wygenerowany jest nieprawidłowy? Zdecydowanie coś jest nie tak z twoim kodem, jeśli osiąga głębokość rekurencji f(1), jedyną możliwą tablicą, która powinna być generowalna, n=1jest [1]również wiele dodatkowych białych spacji do usunięcia tutaj. Pamiętaj, że jest to wyzwanie dla golfa, więc celem jest osiągnięcie najniższej liczby bajtów
Skidsdev,
1
range(1,n)-> range(n)Uważam, że powinien rozwiązać problem.
Jonathan Allan,
1
To powinno naprawić twój błąd, a także usunie zbędne białe znaki. Wyobrażam sobie, że jest też o wiele więcej miejsca na
grę w
1
Chociaż rekursja nieznacznie się pogarsza z 5 do 4, możesz połączyć dwie instrukcje zwracające w następujący sposób: return len(s)==n and sum(s)==n*n and s or f(n)( Wypróbuj online 114 bajtów ).
Kevin Cruijssen
1
Możesz mieć to wszystko w jednym wierszu. 111 bajtów
Jo King
2

APL (Dyalog Unicode) , 20 bajtów SBCS

Anonimowy przedrostek lambda.

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

Wypróbuj online!

{} „Dfn”;jest argumentem

⍵*2 rozwiąż argument

s← przypisać do s(dla s quare)

⍵? znajdź nlosowe wskaźniki od 1…s bez zamiany

c← przypisać do c(dla c iidate)

+/ zsumuj je

s= porównać do s

: jeśli równe

  c zwrócić kandydata

 jeszcze

  ∇⍵ powrócić do argumentu

Adám
źródło
widziałeś 18 bajtów mojego i H.PWiza ?
ngn
@ngn Nie, oczywiście, że nie, ale sprawdziłem, czy żadne rozwiązanie APL nie zostało opublikowane przed opublikowaniem. Dlaczego nikt z was nie
Adám
cóż, po tym jak grałem w golfa i pokazałem go sadzie, nie ma prawie żadnej zachęty do publikowania :)
ngn
@ngn Dla ciebie nie, ale dla mnie jest.
Adám
1
na pewno i myślę, że wykonujesz świetną robotę popularyzując tutaj apl. ja tylko upewniłem się, że wiesz, że znaleziono krótsze rozwiązania i prawdopodobnie lepiej jest wyjaśnić jedno z nich (lub odmianę) zamiast tego
ngn
2

APL (Dyalog Classic) , 18 bajtów

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

Wypróbuj online!

wykorzystuje ⎕io←1

generuje liczby 1 2 ... n

(... )⍣(... )stosuj funkcję po lewej stronie, aż funkcja po prawej stronie zwróci wartość true

długość, tj n

≢?≢×≢wybierz losowo nróżne liczby całkowite od 1 do n2

+.-∘≢ odejmij długość od każdej liczby i sumy

0= jeśli suma wynosi 0, przestań zapętlać, w przeciwnym razie spróbuj ponownie

ngn
źródło
1

MATL , 18 13 bajtów

`xGU:GZrtsGU-

Wypróbuj 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
źródło
Nie spróbowałbym tego w R - losowe postacie prawie nigdy nie produkują prawidłowego programu.
ngm
@ngm hahaha Przypuszczam, że wyjaśnienie jest w porządku.
Giuseppe,
1

Japt, 12 bajtów

²õ àU ö@²¥Xx

Spróbuj

                 :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
Kudłaty
źródło
Zgodnie z komentarzem PO, kolejność elementów w danych wyjściowych jest nieistotna, więc àpowinno być w porządku.
Kamil Drakari,
Dzięki, @KamilDrakari. Zaktualizowano
Shaggy
1

Java (JDK) , 127 bajtów

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

Wypróbuj online!

Pętla nieskończona, aż zestaw z kryteriami się dopasuje.

Mam nadzieję, że masz czas, ponieważ jest bardzo powolny! Nie może nawet dojść do 10 bez przekroczenia limitu czasu.

Olivier Grégoire
źródło
Możesz zagrać w 3 bajty, zmieniając if(r.size()==n&s==0)na if(r.size()+s==n).
Kevin Cruijssen
@KevinCruijssen Też o tym myślałem, ale nie, nie mogę, ponieważ s może być -1, a n może mieć rozmiar () - 1.
Olivier Grégoire
Ach, czekaj, ciągle dodajesz elementy do zestawu tak długo s>0, aby rozmiar mógł być większy niż n. Ok, w takim przypadku to naprawdę nie działa. njest stała, ale niestety zarówno si r.size()są zmiennymi, które mogą być zarówno poniżej lub powyżej 0i nodpowiednio.
Kevin Cruijssen
1

Partia, 182 145 bajtów

@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%%

Objaśnienie: Oblicza minimalny i maksymalny dopuszczalny wybór, biorąc pod uwagę, że liczby mają być wybierane w kolejności malejącej, i wybiera losową wartość z zakresu. Przykład danych wejściowych 4:

  • Zaczynamy od 16 pozostałych. Nie możemy wybrać 11 lub więcej, ponieważ pozostałe 3 typy muszą dodać co najmniej 6. Musimy również wybrać co najmniej 6, ponieważ jeśli wybierzemy tylko 5, pozostałe 3 typy mogą dodać tylko do 9, co nie jest wystarczy na 16. Wybieramy losową wartość od 6 do 10, powiedzmy 6.
  • Zostało 10. Nie możemy wybrać 8 lub więcej, ponieważ pozostałe 2 typy muszą dodać co najmniej 3. Jak się zdarza, nie możemy wybrać 6 lub więcej, ponieważ ostatnio wybraliśmy 6. Musimy również wybrać co najmniej 5, ponieważ jeśli wybieramy tylko 4, pozostałe 2 typy mogą dodać tylko do 5, co daje w sumie 15. Wybieramy losową wartość od 5 do 5, powiedzmy 5 (!).
  • Zostało nam 5. Nie możemy wybrać 5 lub więcej, ponieważ pozostała część musi dodać co najmniej 1, a także dlatego, że wybraliśmy 5 ostatnim razem. Musimy również wybrać co najmniej 3, ponieważ jeśli wybieramy tylko 2, pozostały wybór może wynosić tylko 1, w sumie 14. Wybieramy losową wartość od 3 do 4, powiedzmy 4.
  • Zostało 1. Jak się okazuje, algorytm wybiera zakres od 1 do 1, a jako liczbę końcową wybieramy 1.
Neil
źródło
1

JavaScript, 647 291 261 260 259 251 239 bajtów

Dzięki @Veskah za -10 bajtów w oryginalnej wersji i „Och tak, wyprowadzasz wszystkie zestawy, podczas gdy wyzwanie prosi o zwrócenie losowego”

(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]()]

Wypróbuj online!

Utwórz tablicę n^2indeksów opartych na 1, losowo sortuj tablicę, wycinaj nelementy z tablicy. Podczas gdy suma losowych elementów nie jest równa n^2pętli tablicy losowych elementów; jeśli suma elementów tablicy jest większa niż, n^2a bieżący element -1nie jest równy zero lub bieżący element -1nie znajduje się w bieżącej tablicy, odejmij 1; jeśli suma tablicy jest mniejsza niż, n^2a bieżącego elementu +1nie ma w tablicy, dodaj 1do elementu. Jeśli suma tablic jest równa n^2pętli przerwania, tablica wyjściowa.

guest271314
źródło
1
637 bajtów poprzez wciągnięcie z.join do zmiennej orazk++
Veskah
@Veskah Dwie whilepętle prawdopodobnie można by również zredukować do treści pojedynczej funkcji, która akceptuje parametry; i może zastąpić if..elsetwierdzenia operatorami warunkowymi (trójskładnikowymi) ; wśród innych części kodu, które można by bardziej niż w przypadku golfa dostosować; ieg, usuwanie letoświadczeń.
guest271314,
@Veskah 601 bajtów bez podstawienia trójskładnikowegoif..else
guest271314
1
O tak, wyprowadzasz wszystkie zestawy, podczas gdy wyzwanie prosi o
zwrócenie losowego zestawu (
@Veskah Musiał źle zinterpretować wyzwanie i przykłady lub był zbyt skoncentrowany na rozwiązaniu tej części pytania Zadanie premiowe: Czy istnieje wzór do obliczenia liczby prawidłowych kombinacji dla danej n?” . testowania jeśli algorytm konsekwentnie zwrócony oczekiwany wynik dla n^2tablic wyjściowych generowanych w jednym wywołaniu funkcji, jednocześnie biorąc pod uwagę podobieństwa w tej kwestii N N ^ N-wymiarowej macierzy wypełniony N .
guest271314,
0

Japt , 20 bajtów

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

Wypróbuj online!

Niezwykle mocno wykorzystuje losowość „nierównomierną”, prawie zawsze wypisuje pierwsze nliczby nieparzyste, które się sumują n^2. Teoretycznie może wypisać dowolny inny prawidłowy zestaw, chociaż byłem w stanie to potwierdzić tylko dla małychn .

Wyjaśnienie:

²õ                      :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
źródło
0

C (gcc) , 128 125 bajtów

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

Wypróbuj online!

-3 bajty dzięki pułapce cat

UWAGA: prawdopodobieństwo jest bardzo dalekie od jednolitości. Zobacz wyjaśnienie, co mam na myśli, i lepszy sposób przetestowania, czy to działa (przez zbliżenie dystrybucji do jednolitego [ale nadal daleko od niego]).

W jaki sposób?

Podstawową ideą jest wybieranie tylko rosnących liczb, aby nie martwić się duplikatami. Za każdym razem, gdy wybieramy liczbę, mamy niezerową szansę na „pominięcie”, jeśli jest to dopuszczalne.

xky

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

Niemniej jednak logiką jest szansa na odrzucenie każdego, yktóry spełnia powyższe równanie.

Kod

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.

Sztuczka, którą wspomniałem, aby lepiej przetestować kod, polega na zastąpieniu rand()&&go rand()%2&&tak, aby istniało 50-50 szans na pominięcie dowolnego y, a nie 1 RAND_MAXszansa na użycie dowolnego y.

LambdaBeta
źródło
Bardzo bym chciał, gdyby ktoś sprawdził moją matematykę pod kątem spójności. Zastanawiam się również, czy ten rodzaj rozwiązania może uprościć jednolite losowe wyzwanie prędkości. Formuła umieszcza górną i dolną granicę odpowiedzi, czy jednolita liczba losowa w tym zakresie daje jednolite losowe wyniki? Nie rozumiem, dlaczego nie - ale od jakiegoś czasu nie robiłem dużo kombinatoryki.
LambdaBeta,
Sugerować p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++; zamiast){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;}
ceilingcat
@ceilingcat Uwielbiam te małe ulepszenia, które znajdziesz. Zawsze skupiam się na ogólnym algorytmie, który zapominam zoptymalizować pod kątem implementacji (w zasadzie wybieram tryb golfowy z autopilotem, gdy mam źródło, które nie działa w golfa - więc brakuje mi wielu oszczędności)
LambdaBeta
Hej, to nie tylko ty masz te pola składniowe. Znajduję niewielkie ulepszenia w wielu takich odpowiedziach w języku C / C ++ (z wyjątkiem innych, @ceilingcat zwykle je łapie).
Zacharý
Tak, zauważyłem, że wy dwaj jesteście prawdopodobnie najbardziej aktywnymi putterami C / C ++ (czy możemy użyć putingu, aby rozszerzyć analogię golfa do kilku ostatnich uderzeń? Dlaczego nie!). Zawsze robi na mnie wrażenie, że potrafisz nawet zrozumieć golfowy kod na tyle dobrze, aby go poprawić.
LambdaBeta
0

Czysty , 172 bajty

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

Wypróbuj online!

Obrzydliwe
źródło
0

Python (2 lub 3), 84 bajtów

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

Wypróbuj online!

Trafia maksymalną głębokość rekurencji przy około l (5)

ArBo
źródło
0

Kotlin , 32 bajty

{(1..it*it).shuffled().take(it)}

Wypróbuj online!

ślimak_
źródło
1
Suma musi wynosić n ^ 2
Mee
0

Mathematica 40 bajtów

RandomChoice[IntegerPartitions[n^2, {n}]]
David G. Stork
źródło
1
Przede wszystkim jest to n ^ 2, a nie 2 ^ n. Po drugie, twój program musi być funkcją, a także golfem. Spróbuj tego RandomChoice@IntegerPartitions[#^2,{#}]&
J42161217,
1
Wynik musi być również (nieuporządkowany, niepowtarzalny), ale funkcja ta kończy się niepowodzeniem w obu przypadkach
J42161217,
0

Wolfram Language (Mathematica) , 49 bajtów

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

Wypróbuj online!

Wersja w golfa autorstwa @ J42161217.


Wolfram Language (Mathematica) , 62 bajty

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

Wypróbuj online!

Jak to działa

Głównie na podstawie tego pytania Math.SE . Aby podzielić partycje n2 na n odrębnych części, uzyskaj partycje n2(n2n)/2=(n2+n)/20n1n10


Odpowiedź na zadanie premiowe

Zadanie premiowe: Czy istnieje wzór do obliczania liczby prawidłowych permutacji dla danego n?

Tak. Definiowaćpart(n,k)nk

part(n,k)=part(n1,k1)+part(nk,k)

Możesz to zrozumieć jako „Jeśli partycja zawiera 1, usuń ją; w przeciwnym razie odejmij 1 od każdego terminu”. Więcej wyjaśnień tutaj w innym pytaniu Math.SE . W połączeniu z warunkami początkowymi part(n,1)=1n<kpart(n,k)=0

part(n2+n2,n)

czyli w Mathematica:

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

Wypróbuj online!

Bubbler
źródło
To jest kod golfowy .. 49 bajtów(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
J42161217