Dany:

• Liczbą naturalną S .
• Lista N racjonalnych wag W, które sumują się do 1.

Zwraca listę L N liczb całkowitych nieujemnych, takich jak:

(1) sum(L) = S
(2) sum((S⋅W_i - L_i)^2) is minimal

Innymi słowy, przybliżaj S⋅W_is liczbami całkowitymi tak dokładnie, jak to możliwe.

Przykłady:

1 [0.4 0.3 0.3] = [1 0 0]
3 [0 1 0] = [0 3 0]
4 [0.3 0.4 0.3] = [1 2 1]
5 [0.3 0.4 0.3] = [2 2 1] or [1 2 2] but not [1 3 1]
21 [0.3 0.2 0.5] = [6 4 11]
5 [0.1 0.2 0.3 0.4] = [1 1 1 2] or [0 1 2 2]
4 [0.11 0.3 0.59] = [1 1 2]
10 [0.47 0.47 0.06] = [5 5 0]
10 [0.43 0.43 0.14] = [4 4 2]
11 [0.43 0.43 0.14] = [5 5 1]

Zasady:

• Możesz w ogóle użyć dowolnego formatu wejściowego lub po prostu podać funkcję, która akceptuje dane wejściowe jako argumenty.

Tło:

Ten problem pojawia się, gdy wyświetla się S różnych rodzajów elementów w różnych proporcjach W _i w odniesieniu do typów.

Innym przykładem tego problemu jest proporcjonalna reprezentacja polityczna, patrz paradoks podziału . Dwa ostatnie przypadki testowe znane są jako paradoks Alabama.

Jako statystyk rozpoznałem ten problem jako równoważny z problemem napotkanym przy identyfikacji wielkości próby podczas przeprowadzania próby warstwowej. W tej sytuacji chcemy, aby proporcja każdej warstwy w próbie była równa proporcji każdej warstwy w populacji. - @tomi

APL, 21

{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}

To jest tłumaczenie z 37 bajtowej odpowiedzi CJam aditsu .

Przetestuj online .

Wyjaśnienie

 {      ⍵-⍺}            ⍝ Right argument - left argument.
 {  1=⍋⍋⍵-⍺}            ⍝ Make one of the smallest number 1, others 0.
 {⍵+1=⍋⍋⍵-⍺}            ⍝ Add the result and the right argument together.
 {⍵+1=⍋⍋⍵-⍺}⍣⍺          ⍝ Repeat that S times. The result of each iteration is the new right argument.
                  ⊂⍵    ⍝ Return enclosed W, which is taken as one unit in APL.
               ⍺0×⊂⍵    ⍝ Return S*W and 0*W.
{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}   ⍝ Make S*W the left argument, 0*W the right argument in the first iteration.

Python 2, 95 83 132 125 143

Mój pierwszy (i drugi) (i trzeci) algorytm miał problemy, więc po (innym!) Przepisaniu i kolejnych testach, oto (mam nadzieję) prawidłowe i szybkie rozwiązanie:

def a(b,h):
 g=h;c=[];d=[]
 for w in b:f=int(w*h);d+=[f];c+=[h*w-f];g-=f
 if g:
  for e in sorted(c)[-g:]:i=c.index(e);c[i]=2;d[i]+=1
 return d

Źródło przed minifikatorem wygląda teraz:

# minified 143 bytes
def golfalloc(weights, num):
    # Tiny seq alloc for golfing
    gap = num;
    errors = [];
    counts = []
    for w in weights :
        count = int(w*num);
        counts += [count];
        errors += [num*w - count];
        gap -= count
    if gap:
        for e in sorted(errors)[-gap:] :
            i = errors.index(e);
            errors[i] = 2;
            counts[i] += 1
    return counts

Testy zwracają:

Pass                    Shape    N               Result Error                        AbsErrSum
ok            [0.4, 0.3, 0.3]    1            [1, 0, 0] -0.60,+0.30,+0.30                 1.20
ok                  [0, 1, 0]    3            [0, 3, 0] +0.00,+0.00,+0.00                 0.00
ok            [0.3, 0.4, 0.3]    4            [1, 2, 1] +0.20,-0.40,+0.20                 0.80
ok            [0.3, 0.4, 0.3]    5            [2, 2, 1] -0.50,+0.00,+0.50                 1.00
ok            [0.3, 0.2, 0.5]   21           [6, 4, 11] +0.30,+0.20,-0.50                 1.00
ok       [0.1, 0.2, 0.3, 0.4]    5         [1, 1, 1, 2] -0.50,+0.00,+0.50,+0.00           1.00
ok          [0.11, 0.3, 0.59]    4            [1, 1, 2] -0.56,+0.20,+0.36                 1.12
ok         [0.47, 0.47, 0.06]   10            [5, 5, 0] -0.30,-0.30,+0.60                 1.20
ok         [0.43, 0.43, 0.14]   10            [4, 4, 2] +0.30,+0.30,-0.60                 1.20
ok         [0.43, 0.43, 0.14]   11            [5, 5, 1] -0.27,-0.27,+0.54                 1.08

Ten algorytm jest podobny do innych odpowiedzi tutaj. Jest to O (1) dla num, więc ma ten sam czas działania dla liczb całkowitych 10 i 1000000. Teoretycznie jest to O (nlogn) dla liczby wag (z powodu sortowania). Jeśli to wytrzyma wszystkie inne trudne wejścia, zastąpi poniższy algorytm w moim zestawie narzędzi do programowania.

Nie używaj tego algorytmu do niczego, co nie jest golfem. Zrobiłem kompromis w szybkości, aby zminimalizować rozmiar źródła. Poniższy kod wykorzystuje tę samą logikę, ale jest znacznie szybszy i bardziej użyteczny:

def seqalloc(anyweights, num):
    # Distribute integer num depending on weights.
    # weights may be non-negative integers, longs, or floats.
    totalbias = float(sum(anyweights))
    weights = [bias/totalbias for bias in anyweights]
    counts = [int(w*num) for w in weights]
    gap = num - sum(counts)
    if gap:
        errors = [num*w - q for w,q in zip(weights, counts)]
        ordered = sorted(range(len(errors)), key=errors.__getitem__)
        for i in ordered[-gap:]:
            counts[i] += 1
    return counts

Wartość num nie wpływa znacząco na prędkość. Przetestowałem to z wartościami od 1 do 10 ^ 19. Czas wykonania zmienia się liniowo wraz z liczbą wag. Na moim komputerze zajmuje to 0,15 sekundy przy obciążeniu 10 ^ 5 i 15 sekund przy obciążeniu 10 ^ 7. Zauważ, że wagi nie są ograniczone do ułamków, które sumują się do jednego. Zastosowana tutaj technika sortowania jest około dwa razy szybsza niż tradycyjny sorted((v,i) for i,v in enumerate...)styl.

Oryginalny algorytm

To była funkcja w moim zestawie narzędzi, nieco zmodyfikowana dla golfa. Pochodzi z odpowiedzi SO . I to jest złe.

def seqalloc(seq, num):
    outseq = []
    totalw = float(sum(seq))
    for weight in seq:
        share = int(round(num * weight / totalw)) if weight else 0
        outseq.append(share)
        totalw -= weight
        num -= share
    return outseq

Podaje przybliżenie, ale nie zawsze jest poprawne, chociaż suma (outseq) == num jest zachowana. Szybki, ale niezalecany.

Dzięki @alephalpha i @ user23013 za wykrycie błędów.

EDYCJA: Ustaw totalw (d) na 1, ponieważ OP określa, że ​​suma wag zawsze będzie wynosić 1. Teraz 83 bajty.

EDYCJA 2: Naprawiono błąd znaleziony dla [0.4, 0.3, 0.3], 1.

EDYCJA 3: Opuszczony wadliwy algorytm. Dodano lepszy.

EDIT4: To staje się śmieszne. Zastąpiony prawidłowym (tak naprawdę mam nadzieję) algorytmem.

EDYCJA 5: Dodano kod inny niż golfy dla innych, którzy mogą chcieć korzystać z tego algorytmu.

Mathematica, 67 50 46 45 znaków

f=(b=⌊1##⌋;b[[#~Ordering~-Tr@#&[b-##]]]++;b)&

Nie golfowany:

f[s_, w_] := Module[{a = s*w, b, c, d},
  b = Floor[a];
  c = b - a;
  d = Ordering[c, -Total[c]];
  b[[d]] += 1;
  b]

Przykład:

f[5,{0.1,0.2,0.3,0.4}]

{1, 1, 1, 2}

CJam - 37

q~:W,0a*\:S{[_SWf*]z::-_:e<#_2$=)t}*p

Wypróbuj online

Wyjaśnienie:

q~             read and evaluate the input
               (pushing the number and the array on the stack)
:W,            save the array in variable W and calculate its length (N)
0a*            make an array of N zeros (the initial "L")
\:S            swap it with the number and save the number in S
{…}*           execute the block S times
    [_SWf*]    make a matrix with 2 rows: "L" and S*W
    z          transpose the matrix, obtaining rows of [L_i S*W_i]
    ::-_       convert to array of L_i-S*W_i and duplicate
    :e<        get the smallest element
    #          find its index in the unsorted array,
               i.e. the "i" with the largest S*W_i-L_i
    _2$=)t     increment L_i
p              print the result nicely

Uwagi:

• Złożoność dotyczy O (S * N), więc staje się bardzo wolna dla dużych S
• CJam bardzo brakuje operatorów arytmetycznych dla 2 tablic, co planuję wdrożyć później

Inny pomysł - 46

q~:Sf*_:m[_:+S\-@[1f%_,,]z{0=W*}$<{1=_2$=)t}/p

Wypróbuj online

Jest to o wiele prostsze i wydajniejsze, ale niestety, nieco dłuższe. Chodzi o to, aby zacząć od L_i = floor (S * W_i), ustalić różnicę (powiedzmy D) między S i ich sumą, znaleźć wskaźniki D z największą ułamkową częścią S * W_i (sortując i biorąc górne D) i przyrost L_i dla tych wskaźników. Złożoność O (N * log (N)).

JavaScript (ES6) 126 130 104 115 156 162 194

Po wszystkich komentarzach i testach w odpowiedzi @ CarpetPython wróć do mojego pierwszego algorytmu. Niestety, inteligentne rozwiązanie nie działa. Wdrożenie zostało nieco skrócone, wciąż wypróbowuje wszystkie możliwe rozwiązania, oblicza kwadrat do kwadratu i utrzymuje minimum.

Edycja Dla każdego elementu wyjściowego o masie w „wszystkie” możliwe wartości to tylko 2: trunc (w * s) i trunc (w * s) +1, więc są tylko (2 ** elemensts) możliwe rozwiązania do wypróbowania.

Q=(s,w)=>
  (n=>{
    for(i=0;
        r=q=s,(y=i++)<1<<w.length;
        q|r>n||(n=r,o=t))
      t=w.map(w=>(f=w*s,q-=d=0|f+(y&1),y/=2,f-=d,r+=f*f,d));
  })()||o

Przetestuj w konsoli Firefox / FireBug

;[[ 1,  [0.4, 0.3, 0.3]      ]
, [ 3,  [0, 1, 0]            ]
, [ 4,  [0.3, 0.4, 0.3]      ]
, [ 5,  [0.3, 0.4, 0.3]      ]
, [ 21, [0.3, 0.2, 0.5]      ]
, [ 5,  [0.1, 0.2, 0.3, 0.4] ]
, [ 4,  [0.11, 0.3, 0.59]    ]
, [ 10, [0.47, 0.47, 0.06]   ]
, [ 10, [0.43, 0.43, 0.14]   ]
, [ 11, [0.43, 0.43, 0.14]   ]]
.forEach(v=>console.log(v[0],v[1],Q(v[0],v[1])))

Wynik

1 [0.4, 0.3, 0.3] [1, 0, 0]
3 [0, 1, 0] [0, 3, 0]
4 [0.3, 0.4, 0.3] [1, 2, 1]
5 [0.3, 0.4, 0.3] [1, 2, 2]
21 [0.3, 0.2, 0.5] [6, 4, 11]
5 [0.1, 0.2, 0.3, 0.4] [0, 1, 2, 2]
4 [0.11, 0.3, 0.59] [1, 1, 2]
10 [0.47, 0.47, 0.06] [5, 5, 0]
10 [0.43, 0.43, 0.14] [4, 4, 2]
11 [0.43, 0.43, 0.14] [5, 5, 1]

To mądrzejsze rozwiązanie. Pojedynczy przebieg na tablicy wagowej.
Dla każdego przejścia znajduję aktualną maksymalną wartość w. Zmieniam tę wartość w miejscu za pomocą ważonej wartości całkowitej (zaokrąglonej w górę), więc jeśli s == 21 i w = 0,4, otrzymamy 0,5 * 21 -> 10,5 -> 11. Przechowuję tę wartość zanegowaną, więc nie może znajdować się jako maksimum w następnej pętli. Następnie odpowiednio zmniejszam sumę całkowitą (s = s-11), a także zmniejszam sumę wag w zmiennej f.
Pętla kończy się, gdy nie można znaleźć maks. Powyżej 0 (wszystkie wartości! = 0 zostały zarządzane).
W końcu zwracam wartości zmienione ponownie na dodatnie. Ostrzeżenie: ten kod modyfikuje tablicę wag na miejscu, dlatego należy ją wywołać z kopią oryginalnej tablicy

F=(s,w)=>
 (f=>{
  for(;j=w.indexOf(z=Math.max(...w)),z>0;f-=z)
    s+=w[j]=-Math.ceil(z*s/f);
 })(1)||w.map(x=>0-x)

Moja pierwsza próba

Nie takie inteligentne rozwiązanie. Dla każdego możliwego wyniku ocenia różnicę i utrzymuje minimum.

F=(s,w,t=w.map(_=>0),n=NaN)=>
  (p=>{
    for(;p<w.length;)
      ++t[p]>s?t[p++]=0
      :t.map(b=>r+=b,r=p=0)&&r-s||
        t.map((b,i)=>r+=(z=s*w[i]-b)*z)&&r>n||(n=r,o=[...t])
  })(0)||o

Niegolfowany i wyjaśniony

F=(s, w) =>
{
  var t=w.map(_ => 0), // 0 filled array, same size as w
      n=NaN, // initial minumum NaN, as "NaN > value"  is false for any value
      p, r
  // For loop enumerating from [1,0,0,...0] to [s,s,s...s]
  for(p=0; p<w.length;)
  {
    ++t[p]; // increment current cell
    if (t[p] > s)
    {
      // overflow, restart at 0 and point to next cell
      t[p] = 0;
      ++p;
    }
    else
    {
      // increment ok, current cell is the firts one
      p = 0;
      r = 0;
      t.map(b => r += b) // evaluate the cells sum (must be s)
      if (r==s)
      {
        // if sum of cells is s
        // evaluate the total squared distance (always offset by s, that does not matter)
        t.map((b,i) => r += (z=s*w[i]-b)*z) 
        if (!(r > n))
        {
          // if less than current mininum, keep this result
          n=r
          o=[...t] // copy of t goes in o
        }
      }
    }
  }
  return o
}

CJam, 48 bajtów

Proste rozwiązanie problemu.

q~:Sf*:L,S),a*{m*{(+}%}*{1bS=},{L]z::-Yf#:+}$0=p

Wejście idzie jak

[0.3 0.4 0.3] 4

Wyjaśnienie:

q~:S                                 "Read and parse the input, store sum in S";
    f*:L                             "Do S.W, store the dot product in L";
         S),                         "Get array of 0 to S";
        ,   a*                       "Create an array with N copies of the above array";
              {m*{(+}%}*             "Get all possible N length combinations of 0 to S ints";
                        {1bS=},      "Filter to get only those which sum up to S";
{L]z::-Yf#:+}$                       "Sort them based on (S.W_i - L_i)^2 value";
 L                                   "Put the dot product after the sum combination";
  ]z                                 "Wrap in an array and transpose";
    ::-                              "For each row, get difference, i.e. S.W_i - L_i";
       Yf#                           "Square every element";
          :+                         "Take sum";
              0=p                    "After sorting on sum((S.W_i - L_i)^2), take the";
                                     "first element, i.e. smallest sum and print it";

Wypróbuj online tutaj

Pyth: 40 bajtów

Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUH

Definiuje funkcję gz 2 parametrami. Możesz to tak nazwać Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUHg5 [0.1 0.2 0.3 0.4.

Wypróbuj online: Pyth Compiler / Executor

Wyjaśnienie:

mms+*G@Hb}bklHyUH     (G is S, H is the list of weights)
m             yUH    map each subset k of [0, 1, ..., len(H)-1] to:
 m          lH          map each element b of [0, 1, ..., len(H)-1] to: 
    *G@Hb                  G*H[b]
   +     }bk               + b in k
  s                       floor(_)

Stwarza to wszystkie możliwe rozwiązania L, gdzie L[i] = floor(S*W[i])lub L[i] = floor(S*W[i]+1). Na przykład dane wejściowe 4 [0.3 0.4 0.3tworzą [[1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 2]].

fqsTG...  
f    ... only use the solutions, where
 qsTG       sum(solution) == G

[[2, 1, 1], [1, 2, 1], [1, 1, 2]]Pozostań tylko .

Mhosm^-*Ghded2C,HN
  o                  order the solutions by
   s                   the sum of 
    m         C,HN       map each element d of zip(H, solution) to
     ^-*Ghded2           (G*d[0] - d[1])^2
 h                   use the first element (minimum)
M                    define a function g(G,H): return _

Mathematica 108

s_~f~w_:=Sort[{Tr[(s*w-#)^2],#}&/@ 
Flatten[Permutations/@IntegerPartitions[s,{Length@w},0~Range~s],1]][[1,2]]

f[3, {0, 1, 0}]
f[4, {0.3, 0.4, 0.3}]
f[5, {0.3, 0.4, 0.3}]
f[21, {0.3, 0.2, 0.5}]
f[5, {0.1, 0.2, 0.3, 0.4}]

{0, 3, 0}
{1, 2, 1}
{1, 2, 2}
{6, 4, 11}
{0, 1, 2, 2}

Wyjaśnienie

Nie golfił

f[s_,w_]:=
Module[{partitions},
partitions=Flatten[Permutations/@IntegerPartitions[s,{Length[w]},Range[0,s]],1];
Sort[{Tr[(s *w-#)^2],#}&/@partitions][[1,2]]]

IntegerPartitions[s,{Length@w},0~Range~s]Zwraca wszystkie przegrody całkowitoliczbowej s, przy użyciu elementów wykonanych z zestawu {0, 1, 2, ...s}z ograniczeniem, że sygnał wyjściowy powinien zawierać taką samą liczbę elementów, jak w zestawie wag, w.

Permutations podaje wszystkie uporządkowane układy każdej partycji całkowitej.

{Tr[(s *w-#)^2],#}zwraca listę uporządkowanych par {error, permutation} dla każdej permutacji.

Sort[...] sortuje listę {{error1, permutation1},{error2, permutation2}...according to the size of the error.

[[1,2]]]lub Part[<list>,{1,2}]zwraca drugi element pierwszego elementu z posortowanej listy {{error, permutation}...}. Innymi słowy, zwraca permutację z najmniejszym błędem.

R, 85 80 76

Używa metody Hare Quota.

Usunięto parę po zobaczeniu specyfikacji, że W wyniesie 1

function(a,b){s=floor(d<-b*a);s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s}

Testowe uruchomienie

> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(3,c(0,1,0))
[1] 0 3 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(1,c(0.4,0.3,0.3))
[1] 1 0 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(4,c(0.3, 0.4, 0.3))
[1] 1 2 1
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.3, 0.4, 0.3))
[1] 1 2 2
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(21,c(0.3, 0.2, 0.5))
[1]  6  4 11
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.1,0.2,0.3,0.4))
[1] 1 1 1 2
>

Python, 139 128 117 bajtów

def f(S,W):
 L=(S+1,0,[]),
 for n in W:L=[(x-i,y+(S*n-i)**2,z+[i])for x,y,z in L for i in range(x)]
 return min(L)[2]

Poprzednie rozwiązanie itertools, 139 bajtów

from itertools import*
f=lambda S,W:min((sum(x)!=S,sum((S*a-b)**2for a,b in zip(W,x)),list(x))for x in product(*tee(range(S+1),len(W))))[2]

Oktawa, 87 76

Gra w golfa:

function r=w(s,w)r=0*w;for(i=1:s)[m,x]=max(s*w-r);r(x)+=1;endfor endfunction

Nie golfowany:

function r=w(s,w)
  r=0*w;   # will be the output
  for(i=1:s)
    [m,x]=max(s*w-r);
    r(x)+=1;
  endfor
endfunction

(Przeklęte „endfor” i „endfunction”! Nigdy nie wygrywam, ale lubię grać w golfa w „prawdziwym” języku).

T-SQL, 167 265

Ponieważ lubię próbować wykonywać te wyzwania również w zapytaniu.

Zamieniono go w funkcję wbudowaną, aby lepiej pasowała do specyfikacji i utworzono typ danych tabeli. Trochę to kosztowało, ale to nigdy nie będzie rywalem. Każda instrukcja musi być uruchamiana osobno.

CREATE TYPE T AS TABLE(A INT IDENTITY, W NUMERIC(9,8))
CREATE FUNCTION W(@ int,@T T READONLY)RETURNS TABLE RETURN SELECT CASE WHEN i<=@-SUM(g)OVER(ORDER BY(SELECT\))THEN g+1 ELSE g END R,A FROM(SELECT A,ROW_NUMBER()OVER(ORDER BY (W*@)%1 DESC)i,FLOOR(W*@)g FROM @T)a

W użyciu

DECLARE @ INT = 21
DECLARE @T T
INSERT INTO @T(W)VALUES(0.3),(0.2),(0.5)
SELECT R FROM dbo.W(@,@T) ORDER BY A

R
---------------------------------------
6
4
11