Liczby losowe ze stałą sumą

32

Twoim zadaniem jest napisanie programu lub funkcji tego wyjścia n liczb losowych z przedziału [0,1] z ustaloną sumę s.

Wkład

n, n≥1, liczba liczb losowych do wygenerowania

s, s>=0, s<=n, suma liczb do wygenerowania

Wydajność

Losowa nliczba liczb zmiennoprzecinkowych ze wszystkimi elementami z przedziału [0,1] i sumą wszystkich elementów równych s, jest generowana w dowolny dogodny, jednoznaczny sposób. Wszystkie ważne npary muszą być jednakowo prawdopodobne w granicach liczb zmiennoprzecinkowych.

Jest to równoznaczne z równomiernym próbkowaniem z przecięcia punktów wewnątrz nsześcianu -wymiarowej jednostki i n-1-wymiarowej hiperpłaszczyzny, która przechodzi (s/n, s/n, …, s/n)i jest prostopadła do wektora (1, 1, …, 1)(trzy przykłady patrz czerwony obszar na rycinie 1).

Przykłady z n = 3 i sumy 0,75, 1,75 i 2,75

Rysunek 1: Płaszczyzna prawidłowych wyników przy n = 3 i suma 0,75, 1,75 i 2,75

Przykłady

n=1, s=0.8 → [0.8]
n=3, s=3.0 → [1.0, 1.0, 1.0]
n=2, s=0.0 → [0.0, 0.0]
n=4, s=2.0 → [0.2509075946818119, 0.14887693388076845, 0.9449661625992032, 0.6552493088382167]
n=10, s=9.999999999999 → [0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999,0.9999999999999]

Zasady

  • Twój program powinien zakończyć się na sekundę na twoim komputerze co najmniej za pomocą n≤10i prawidłowych s.
  • Jeśli chcesz, twój program może być wyłączny na górnym końcu, tj. s<nI liczbach wyjściowych z półotwartego przedziału [0,1) (przełamując drugi przykład)
  • Jeśli twój język nie obsługuje liczb zmiennoprzecinkowych, możesz sfałszować wynik co najmniej dziesięcioma cyframi dziesiętnymi po przecinku.
  • Standardowe luki są niedozwolone i dozwolone są standardowe metody wejścia / wyjścia.
  • To jest , więc wygrywa najkrótszy wpis, mierzony w bajtach.
Angs
źródło
Związane z.
Martin Ender
Kiedy mówisz This is equal to uniformly sampling from the intersection- widzę, że program wybiera losowo tylko z rogów tego skrzyżowania. Czy to byłoby ważne?
JayCe
2
@KevinCruijssen Nie, to prawda s==0 or s==3. Dla wszystkich innych wartości spłaszczyzna ma niezerowe pole i musisz jednorodnie losowo wybrać punkt na tej płaszczyźnie.
user202729,
3
Wymaganie, aby przedział czasu był zamknięty lub pół-zamknięty (w przeciwieństwie do otwarcia), jest teoretycznie nie do zaobserwowania. Wiele generatorów liczb losowych podaje dane wyjściowe w (0,1). Jak sprawdzić, czy interwał wyjściowy wynosi [0,1), a nie (0,1)? W każdym razie wartość 0 „nigdy” nie występuje
Luis Mendo
2
Czy to w porządku, jeśli nasz kod używa próbkowania odrzucania, a więc zajmuje bardzo dużo przypadków testowych, takich jak s=2.99999999999, n=3? Czy możemy generować losowe liczby rzeczywiste w wielokrotnościach, powiedzmy 1e-9,?
xnor

Odpowiedzi:

1

Wolfram Language (Mathematica) , 92 90 bajtów

If[2#2>#,1-#0[#,#-#2],While[Max[v=Differences@Sort@Join[{0,#2},RandomReal[#2,#-1]]]>1];v]&

Wypróbuj online!

Kod bez golfa:

R[n_, s_] := Module[{v},
  If[s <= n/2,             (* rejection sampling for s <= n/2:                        *)
    While[
      v = Differences[Sort[
            Join[{0},RandomReal[s,n-1],{s}]]];         (* trial randoms that sum to s *)
      Max[v] > 1           (* loop until good solution found                          *)
    ];
    v,                     (* return the good solution                                *)
    1 - R[n, n - s]]]      (* for s > n/2, invert the cube and rejection-sample       *)

Oto rozwiązanie, które działa w 55 bajtach, ale na razie (Mathematica wersja 12) jest ograniczone, n=1,2,3ponieważ RandomPointodmawia rysowania punktów z hiperpłaszczyzn o wyższych wymiarach (w wersji 11.3 TIO również się nie udaje n=1). Może jednak nw przyszłości działać lepiej :

RandomPoint[1&~Array~#~Hyperplane~#2,1,{0,1}&~Array~#]&

Wypróbuj online!

Kod bez golfa:

R[n_, s_] :=
  RandomPoint[                           (* draw a random point from *)
    Hyperplane[ConstantArray[1, n], s],  (* the hyperplane where the sum of coordinates is s *)
    1,                                   (* draw only one point *)
    ConstantArray[{0, 1}, n]]            (* restrict each coordinate to [0,1] *)
rzymski
źródło
7

JavaScript (Node.js) , 122 115 bajtów

N=>W=S=>2*S>N?W(N-S).map(t=>1-t):(t=(Q=s=>n?[r=s-s*Math.random()**(1/--n),...r>1?[++Q]:Q(s-r)]:[])(S,n=N),Q?t:W(S))

Wypróbuj online!

l4m2
źródło
6

Python 2 , 144 128 119 bajtów

from random import*
def f(n,s):
 r=min(s,1);x=uniform(max(0,r-(r-s/n)*2),r);return n<2and[s]or sample([x]+f(n-1,s-x),n)

Wypróbuj online!


  • -20 bajtów, dzięki Kevin Cruijssen
TFeld
źródło
@LuisMendo Powinien zostać teraz naprawiony
TFeld
nadal wydają się niejednolite
m2
@ l4m2 Pobiegłem g(4, 2.0)1000 razy, aby uzyskać 4000 punktów, a wyniki wyglądają tak, jak się wydaje, dość jednolite.
Inżynier Toast
122 bajty?
Giuseppe,
2
Nadal nie tak
14m2
4

Java 8, 194 188 196 237 236 bajtów

n->s->{double r[]=new double[n+1],d[]=new double[n],t;int f=0,i=n,x=2*s>n?1:0;for(r[n]=s=x>0?n-s:s;f<1;){for(f=1;i-->1;)r[i]=Math.random()*s;for(java.util.Arrays.sort(r);i<n;d[i++]=x>0?1-t:t)f=(t=Math.abs(r[i]-r[i+1]))>1?0:f;}return d;}

+49 bajtów (188 → 196 i 196 → 237), aby naprawić szybkość przypadków testowych zbliżonych do 1, a także ogólnie naprawić algorytm.

Wypróbuj online

Wyjaśnienie:

Wykorzystuje podejście z tej odpowiedzi StackoverFlow , w pętli, dopóki jeden z elementów jest nadal większy niż 1.
Ponadto, jeśli 2*s>n, szostanie zmieniony na n-s, a ustawiona jest flaga wskazująca, że ​​powinniśmy użyć 1-diffzamiast diffw tablicy wyników (dzięki za wskazówkę @soktinpk i @ l4m2 ).

n->s->{              // Method with integer & double parameters and Object return-type
  double r[]=new double[n+1]
                     //  Double-array of random values of size `n+1`
         d[]=new double[n],
                     //  Resulting double-array of size `n`
         t;          //  Temp double
  int f=0,           //  Integer-flag (every item below 1), starting at 0
      i=n,           //  Index-integer, starting at `n`
      x=             //  Integer-flag (average below 0.5), starting at:
        2*s>n?       //   If two times `s` is larger than `n`:
         1           //    Set this flag to 1
        :            //   Else:
         0;          //    Set this flag to 0
  for(r[n]=s=        //  Set both the last item of `r` and `s` to:
       x>0?          //   If the flag `x` is 1:
        n-s          //    Set both to `n-s`
       :             //   Else:
        s;           //    Set both to `s`
      f<1;){         //  Loop as long as flag `f` is still 0
    for(f=1;         //   Reset the flag `f` to 1
        i-->1;)      //   Inner loop `i` in range (n,1] (skipping the first item)
      r[i]=Math.random()*s;
                     //    Set the i'th item in `r` to a random value in the range [0,s)
    for(java.util.Arrays.sort(r);
                     //   Sort the array `r` from lowest to highest
        i<n;         //   Inner loop `i` in the range [1,n)
        ;d[i++]=     //     After every iteration: Set the i'th item in `d` to:
          x>0?       //      If the flag `x` is 1:
           1-t       //       Set it to `1-t`
          :          //      Else:
           t)        //       Set it to `t`
      f=(t=Math.abs( //    Set `t` to the absolute difference of:
            r[i]-r[i+1])) 
                     //     The i'th & (i+1)'th items in `r`
        >1?          //    And if `t` is larger than 1 (out of the [0,1] boundary)
         0           //     Set the flag `f` to 0
        :            //    Else:
         f;}         //     Leave the flag `f` unchanged
  return d;}         //  Return the array `d` as result
Kevin Cruijssen
źródło
Czas natest(10, 9.99);
14m2
@ l4m2 Tak, zauważyłem to samo 10, 9.0zaraz po tym, jak edytowałem, aby naprawić n=10, s=9.999999999999przypadek testowy. Nie jestem pewien, czy jest poprawka w Javie, wciąż zachowując jej równomierną losowość. Będę musiał się nad tym zastanowić. Na razie dokonam edycji, aby określić limit czasu.
Kevin Cruijssen
Jeśli n-s<1możesz zadzwonić f(n,n-s)i przerzucić każdy numer 1/2(tj. Zastąpić xgo 1-x), tak jak zrobił to L4m2. To może rozwiązać problem dla liczb, które ssą blisko n.
soktinpk
@soktinpk Dzięki za wskazówkę. Właściwie to s+s>nzamiast n-s<1, ale kiedy spojrzałem na inne odpowiedzi JavaScript, rzeczywiście miało to sens. Wszystko jest teraz naprawione, w tym kolejny błąd, który był nadal obecny. Bajty trochę wzrosły, ale teraz każdy działa. Będzie działać odliczanie bajtów stąd. :)
Kevin Cruijssen
Nie znam ogólnego dowodu, ale wierzę, że ten algorytm działa, ponieważ N-wymiarową hipersześcianę można pociąć na N-wymiarowe hiperpiramidy.
Neil,
3

C ++ 11, 284 267 bajtów

-17 bajtów dzięki
losowej bibliotece Zacharý Uses C ++, wyjście na standardowe wyjście

#include<iostream>
#include<random>
typedef float z;template<int N>void g(z s){z a[N],d=s/N;int i=N;for(;i;)a[--i]=d;std::uniform_real_distribution<z>u(.0,d<.5?d:1-d);std::default_random_engine e;for(;i<N;){z c=u(e);a[i]+=c;a[++i]-=c;}for(;i;)std::cout<<a[--i]<<' ';}

Aby zadzwonić, musisz po prostu to zrobić:

g<2>(0.0);

Gdzie parametrem szablonu (tutaj 2) jest N, a rzeczywistym parametrem (tutaj 0,0) jest S

HatsuPointerKun
źródło
Myślę, że możesz usunąć odstęp między <z>iu
Zacharý
Dostałem ją dalej: typedef float z;template<int N>void g(z s){z a[N],d=s/N;int i=N;for(;i;)a[--i]=d;std::uniform_real_distribution<z>u(.0,d<.5?d:1-d);std::default_random_engine e;for(;i<N;){z c=u(e);a[i]+=c;a[++i]-=c;}for(;i;)std::cout<<a[--i]<<' ';}. Nowa linia nie musi być separatorem między przedmiotami
Zacharý
1
Zaproponuj pozbyć się dcałkowicie, zmieniając d=s/Nna s/=NSugeruj przerobienie drugiej pętli for(z c;i<N;a[++i%N]-=c)a[i]+=c=u(e);zamiast for(;i<N;){z c=u(e);a[i]+=c;a[++i]-=c;}(zwróć uwagę na dodane %N, aby program poprawnie obliczył pierwszą liczbę)
Max Yekhlakov
2

Czysty , 221 201 bajtów

Czyste, golfowe lub losowe liczby. Wybierz dwa.

import StdEnv,Math.Random,System._Unsafe,System.Time
g l n s#k=toReal n
|s/k>0.5=[s/k-e\\e<-g l n(k-s)]
#r=take n l
#r=[e*s/sum r\\e<-r]
|all((>)1.0)r=r=g(tl l)n s

g(genRandReal(toInt(accUnsafe time)))

Wypróbuj online!

Literał funkcji częściowej :: (Int Real -> [Real]). Będzie generować nowe wyniki tylko raz na sekundę.
Dokładność do co najmniej 10 miejsc po przecinku.

Obrzydliwe
źródło
2

R , 99 bajtów (z gtoolspakietem)

f=function(n,s){if(s>n/2)return(1-f(n,n-s))
while(any(T>=1)){T=gtools::rdirichlet(1,rep(1,n))*s}
T}

Wypróbuj online!

ZA~={w1,,wn:ja,0<wja<1;wja=s}. Podzielę wszystkiewja przez s i zamiast tego próbkuj z ZA={w1,,wn:ja,0<wja<1s;wja=1}.

Jeśli s=1, to proste: odpowiada próbkowaniu z rejarjadohlmit(1,1,,1) dystrybucja (która jest jednolita w stosunku do simpleksu). W ogólnym przypadkus1, używamy próbkowania odrzucenia: próbka z rozkładu Dirichleta, dopóki wszystkie wpisy nie będą <1/s, a następnie pomnóż przez s.

Sposób na wykonanie kopii lustrzanej kiedy s>n/2)(co myślę, że L4m2 jako pierwszy wymyślił ) jest niezbędne. Zanim to zobaczyłem, liczba iteracji w próbniku odrzucenia eksplodowała w ostatnim przypadku testowym, więc spędziłem dużo czasu próbując efektywnie próbkować z dobrze wybranych skróconych dystrybucji Beta, ale w końcu nie jest to konieczne.

Robin Ryder
źródło
2

C, 132 127 125 118 110 107 bajtów

-2 bajty dzięki @ceilingcat

i;f(s,n,o,d)float*o,s,d;{for(i=n;i;o[--i]=d=s/n);for(;i<n;o[++i%n]-=s)o[i]+=s=(d<.5?d:1-d)*rand()/(1<<31);}

Wypróbuj online!

OverclockedSanic
źródło
Niestety, ta odpowiedź nie spełnia specyfikacji wyzwania. Wyjściowe liczby losowe nie są ograniczone [0,1], a ich łączny rozkład nie jest jednolity.
Nitrodon
@Nitrodon hej, czy możesz podać dane wejściowe, dla których wyjście nie jest ograniczone do [0,1]? Wypróbowałem kilka różnych przykładów i wszystkie wydawały się poprawne, chyba że źle zrozumiałem cel.
OverclockedSanic
Przy stanie RNG na TIO i utrzymywaniu n=4wartości s=3.23oraz wartości s=0.89wyjściowych poza zakresem. Co więcej, dystrybucja X-s/npowinna zależeć s, ale tak nie jest.
Nitrodon
@Nitrodon Ups, mój zły. Przekształciłem niektóre części powyższej odpowiedzi w C ++ i zapomniałem coś dodać. To powinno być teraz naprawione? Grał też kilka bajtów.
OverclockedSanic
1

Haskell , 122 217 208 bajtów

import System.Random
r p=randomR p
(n#s)g|n<1=[]|(x,q)<-r(max 0$s-n+1,min 1 s)g=x:((n-1)#(s-x)$q)
g![]=[]
g!a|(i,q)<-r(0,length a-1)g=a!!i:q![x|(j,x)<-zip[0..]a,i/=j]
n%s=uncurry(!).(n#s<$>).split<$>newStdGen

Wypróbuj online!

Czasami odpowiedzi są nieco nieaktualne z powodu, jak sądzę, błędu zmiennoprzecinkowego. Jeśli to problem, mogę to naprawić kosztem 1 bajtu. Nie jestem też pewien, czy jest to jednolite (całkiem pewne, że jest w porządku, ale nie jestem aż tak dobry w tego typu sprawach), więc opiszę mój algorytm.

Podstawową ideą jest wygenerowanie liczby, xa następnie odjęcie jej si powtarzanie do momentu, aż będziemy mieli nelementy, a następnie przetasujemy je. Generuję xz górną granicą 1 lub s(w zależności od tego, która wartość jest mniejsza) i dolną granicą s-n+1lub 0 (w zależności od tego, która wartość jest większa). Ta dolna granica istnieje, więc przy następnej iteracji snadal będzie mniejsza lub równa n(wyprowadzenie: s-x<=n-1-> s<=n-1+x-> s-(n-1)<=x-> s-n+1<=x).

EDYCJA: Dzięki @ michi7x7 za wskazanie wady w mojej jednolitości. Myślę, że naprawiłem to przez tasowanie, ale daj mi znać, jeśli jest inny problem

EDYCJA 2: Poprawiona liczba bajtów plus ustalone ograniczenie typu

użytkownik 1472751
źródło
3
Łączenie jednolitych próbek nigdy nie doprowadzi do równomiernego rozkładu (ostatnia współrzędna jest prawie zawsze większa niż 0,99 w twoim przykładzie)
michi7x7
@ michi7x7 Rozumiem twój punkt widzenia. Co się stanie, jeśli po wygenerowaniu przetasuję kolejność listy? Powinienem był wziąć więcej klas statystyk
1472751
Liczby nie wyglądają bardzo jednolicie. Tutaj 8 wyników to> 0,99, 1 to 0,96, a ostatni to 0,8. Tak to wygląda.
Stewie Griffin,
@ user1472751 jest kilka dobrych odpowiedzi tutaj: stackoverflow.com/q/8064629/6774250
michi7x7
1
Jednorodność nadal ma pewien problem, patrz tutaj - wygenerowano zbyt wiele zer (wykres posortowanych wartości od 1000% 500)
Angs
1

Haskell , 188 bajtów

import System.Random
import Data.List
n!s|s>n/2=map(1-)<$>n!(n-s)|1>0=(zipWith(-)=<<tail).sort.map(*s).(++[0,1::Double])<$>mapM(\a->randomIO)[2..n]>>= \a->if all(<=1)a then pure a else n!s

Nie golfowany:

n!s
 |s>n/2       = map (1-) <$> n!(n-s)       --If total more than half the # of numbers, mirror calculation 
 |otherwise   = (zipWith(-)=<<tail)        --Calculate interval lengths between consecutive numbers
              . sort                       --Sort
              . map(*s)                    --Scale
              . (++[0,1::Double])          --Add endpoints
              <$> mapM(\a->randomIO)[2..n] --Calculate n-1 random numbers
              >>= \a->if all(<=1)a then pure a else n!s   --Retry if a number was too large

Wypróbuj online!

Angs
źródło