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?

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

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)

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!

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.

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

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)

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

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./*

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.

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

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 n²

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

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

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

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

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.

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.

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.

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

Rubinowy , 46 bajtów

->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

Wypróbuj online!

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

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.

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!

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)

Kotlin , 32 bajty

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

Wypróbuj online!

Mathematica 40 bajtów

RandomChoice[IntegerPartitions[n^2, {n}]]

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 $n^2$ na $n$ odrębnych części, uzyskaj partycje $n^2 - (n^2-n)/2 = (n^2+n)/2$$0 \cdots n-1$$n-1 \cdots 0$

Odpowiedź na zadanie premiowe

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

Tak. Definiować$part(n,k)$$n$$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) = 1$$n < k \Rightarrow part(n,k) = 0$

czyli w Mathematica:

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

Wypróbuj online!