O serii

Po pierwsze, możesz potraktować to jak każde inne wyzwanie związane z golfem i odpowiedzieć na nie, nie martwiąc się serią. Istnieje jednak tabela wyników dla wszystkich wyzwań. Możesz znaleźć tabelę liderów wraz z kilkoma więcej informacji o serii w pierwszym poście .

Chociaż mam szereg pomysłów w szeregu, przyszłe wyzwania nie są jeszcze ustalone. Jeśli masz jakieś sugestie, daj mi znać w odpowiednim poście z piaskownicą .

Dziura 3: partycje całkowite

Czas trochę zwiększyć trudność.

Partycja o dodatnia njest zdefiniowany jako MultiSet liczb całkowitych, które sumują się do pozytywnych n. Na przykład, jeśli n = 5istnieją następujące partycje:

{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}

Należy pamiętać, że są to multisets, więc nie ma celu nich {3,1,1}, {1,3,1}i {1,1,3}są uważane za identyczne.

Twoim zadaniem jest nwygenerowanie losowej partycji n. Oto szczegółowe zasady:

• Rozkład produkowanych przegród musi być jednolity . Oznacza to, że w powyższym przykładzie każda partycja powinna zostać zwrócona z prawdopodobieństwem 1/7.

  Oczywiście, ze względu na ograniczenia techniczne PRNG, idealna jednolitość będzie niemożliwa. W celu oceny jednolitości przesłanych danych następujące operacje zostaną uznane za zapewniające idealnie jednolite rozkłady:

  • Uzyskiwanie numeru z PRNG (w dowolnym zakresie), który jest udokumentowany jako (w przybliżeniu) jednolity.
  • Mapowanie równomiernego rozkładu większego zbioru liczb na mniejszy zbiór poprzez modulo lub mnożenie (lub inną operację, która równomiernie rozprowadza wartości). Większy zestaw musi zawierać co najmniej 1024 razy więcej możliwych wartości niż mniejszy zestaw.

• Ponieważ partycje są wielosektorowe, możesz zwracać je w dowolnej kolejności, a ta kolejność nie musi być spójna. Jednak dla celów losowego rozkładu kolejność jest ignorowana. Oznacza to, że w powyższym przykładzie {3,1,1}, {1,3,1}a {1,1,3} razem muszą mieć prawdopodobieństwo 1/7 zwracane.

• Twój algorytm musi mieć deterministyczne środowisko wykonawcze. W szczególności nie można generować losowych multiset i odrzucać ich, jeśli się nie sumują n.
• Złożoność czasowa algorytmu musi być wielomianowa n. W szczególności nie można po prostu wygenerować wszystkich partycji i wybrać losowej (ponieważ liczba partycji rośnie wykładniczo n). Możesz założyć, że używany PRNG może zwracać równomiernie rozłożone wartości w O (1) na wartość.
• Nie wolno używać żadnej wbudowanej funkcji, która rozwiązuje to zadanie.

Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN lub najbliższej alternatywy, argumentu wiersza poleceń lub argumentu funkcji i wygenerować wynik poprzez wartość zwracaną lub drukując do STDOUT (lub najbliższej alternatywy).

Możesz założyć, że n ≤ 65(tak, że liczba partycji jest mniejsza niż 2 ²¹ ). Dane wyjściowe mogą być w dowolnym dogodnym, jednoznacznym formacie listy lub ciągu.

Jeśli przesyłasz funkcję, zastanów się nad zapewnieniem małego programu testowego, który wywołuje tę funkcję wiele razy i drukuje wyniki. Nie ma potrzeby modyfikowania parametrów w kodzie. Ma to na celu sprawdzenie, czy rozwiązanie jest w przybliżeniu jednolite.

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach). I oczywiście najkrótsze zgłoszenie na użytkownika wejdzie również do ogólnej tabeli liderów serii.

Tabela liderów

Pierwszy post z serii generuje tabelę wyników.

Aby upewnić się, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).

Python 2, 179 bajtów

from random import*
m=r=input();i=q=r+1;h=[1]+[0]*q*q;exec"h[i]=h[i+~q]+h[i-i%q*q];i+=1;"*r*q
while r:
 x=random()*sum(h[r*q:r*q-~m]);m=0
 while x>0:m+=1;x-=h[r*q+m]
 print m;r-=m

Użyłem wzoru (39) z tego wyciągu Knuth , który podaje liczbę partycji, nktóre mają dokładnie mczęści. Zdarza się to równać liczbie partycji, nktóre mają mjako maksymalny element, co jest interpretacją, której używam. Elementy partycji są generowane od największej do najmniejszej. Na każdym etapie formuła jest ponownie wykorzystywana z bieżącą resztą ni maksymalnym dozwolonym elementem.

Dyalog APL, 67 59 51 bajtów

p←{⍵,⊂1,⍨+/¨⌽⍵↑¨⍨⌽⍳⍴⍵}⍣⎕⊢⍬⋄f←{⍵=0:⍬⋄a,a∇⍵-a←{1++/(?+/⍵)>+\⍵}⍺↑⍵⊃p}⍨ (67 bajtów)

pjest wektorem wektorów, w którym p[n][k]jest liczba partycji nna ksumy, lub równoważnie: liczba partycji o największym summand k. Budujemy p, zaczynając od pustego wektora ⍬, czytając n(dane ⎕wejściowe do odczytu) i powtarzając następujące czynności:

{⍵,⊂1,⍨+/¨⌽⍵↑¨⍨⌽⍳⍴⍵}
                 ⍴⍵   ⍝ the current length, initially 0
                ⍳⍴⍵   ⍝ 1 2 ... length
               ⌽⍳⍴⍵   ⍝ length ... 2 1
           ⍵↑¨⍨       ⍝ take length elements from p[1], length-1 from p[2], etc
                      ⍝ padded with 0-s, e.g. if p was (,1)(1 1)(1 1 1)(1 2 1 1)(1 2 2 1 1):
                      ⍝ we get:     (1 0 0 0 0)(1 1 0 0)(1 1 1)(1 2)(,1)
          ⌽           ⍝ reverse it: (,1)(1 2)(1 1 1)(1 1 0 0)(1 0 0 0 0)
       +/¨            ⍝ sum each:   1 3 3 2 1
    1,⍨               ⍝ append 1:   1 3 3 2 1 1
 ⍵,⊂                  ⍝ append the above to the vector of vectors

Po naplikacji ( ⍣⎕) zbudowaliśmy p.

fwybiera losową partycję. n f kjest losową partycją co najwyżej k summands. f njest n f n.

{⍵=0:⍬⋄a,a∇⍵-a←{1++/(?+/⍵)>+\⍵}⍺↑⍵⊃p}⍨
                                     ⍨ ⍝ "selfie" -- use n as k if no k is provided
 ⍵=0:⍬                                 ⍝ if n=0 return empty
                                 ⍵⊃p   ⍝ pick the n-th element of p
                               ⍺↑      ⍝ take k elements from that
               {1++/(?+/⍵)>+\⍵}        ⍝ use them as weights to pick a random number 1...k
               {           +\⍵}        ⍝   partial sums of weights
               {    (?+/⍵)    }        ⍝   a random number 1...sum of weights
               {    (?+/⍵)>+\⍵}        ⍝   which partial sums is it greater than?
               {  +/          }        ⍝   count how many "greater than"-s
               {1+            }        ⍝   we're off by one
             a←                        ⍝ this will be the greatest number in our partition
         a∇⍵-a                         ⍝ recur with n1=n-a and k1=a
       a,                              ⍝ prepend a

Niektóre ulepszenia:

• wbudowany pkosztem nieco gorszej (ale wciąż wystarczająco dobrej) wydajności

• w obliczeniach zmiany pkolejności ⌽i 1,zapisania postaci

• zamień {1++/(?+/⍵)>+\⍵}się w pociąg z 1+przodu:1+(+/(?+/)>+\)

• wykonać fanonimową funkcję i podać ⎕(ewaluowane dane wejściowe) jako argument do uzyskania kompletnego programu

{⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨⎕ (59 bajtów)

Testuj przy n = 5

Test przy n = 65

A poniższy link działa n = 5 tysięcy razy i zbiera statystyki dotyczące częstotliwości każdej partycji: ⎕rl←0 ⋄ {⍺,⍴⍵}⌸ {⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨ ¨10000⍴5

Więcej ulepszeń, z pomocą Roger Hui :

• wymienić {⍵=0:A⋄B}z {×⍵:B⋄A}. Signum ( ×⍵) zwraca true ⍵>0i false dla ⍵=0.

• wymienić (+/(?+/)>+\)z +/b<?⊃⌽b←+\, zapisuje znak

• użycie matrycy zamiast wektora wektorów do obliczania pzamienić ⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬się ⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1.

{×⍵:a,a∇⍵-a←1++/b<?⊃⌽b←+\⍺↑⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1⋄⍬}⍨ (51 bajtów)

test n = 5 ; test n = 65 ; statystyki freq

GolfScript, 90 bajtów

~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`

Demo online

Jest to adaptacja mojego (prostszego) kodu zliczania partycji, który zamiast śledzić liczbę śledzi zarówno liczbę, jak i jednolicie wybrany jeden z elementów zliczanych.

Bezpośrednie porównanie tych dwóch:

~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`
 [[ 1  ]]\({..[[{          1$,1$,-=}%  0 @0=+     ]zip{{+}*                }:^%]\+}*0=^

Różnice:

• Inicjał ~wynika z tego, że jest to program, a nie fragment kodu.
• Do [1.]zastąpienia 1odpowiada zmianie o co śledzone.
• Dodatkowe {(\{)}%+}%zwiększa każdy element w tej partycji i {1+}%dodaje 1do partycji.
• 0staje się [0](grał w golfa 1,) w ramach zmiany tego, co jest śledzone, ale ponieważ musi pozostać tablicą, gdy zostanie dodana do innej, potrzebuje dodatkowych [ ].
• Prosta suma {+}*staje się ważonym wyborem z partycji w połączeniu z sumowaniem ich liczby.
• (;`Usuwa liczyć od wyjścia i stawia partycji w formacie miły.

Ramy testowe

;7000,{;
  '5'

  ~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`

}%
:RESULTS
.&${
  RESULTS.[2$]--,' '\n
}/

Dostosuj początkową 7000, jeśli chcesz uruchomić inną liczbę prób. Zauważ, że jest to zdecydowanie zbyt wolne, aby można było obejrzeć demo online.

Java, 285 267 bajtów

int[][]p;void p(int n){p=new int[n+1][n+1];int a=n,b=k(n,a),c,d;for(b*=Math.random();n>0;System.out.print(c+" "),n-=a=c)for(c=0;c++<(a<n?a:n)&b>=(d=k(n-c,c));b-=d);}int k(int n,int k){if(p[n][k]<1)for(int a=0,b=0;b<k&b++<n;p[n][k]=a)a+=k(n-b,b);return n>0?p[n][k]:1;}

Jest to ta sama metoda, co odpowiedź TheBestOne, ale używa prostej tablicy zamiast mapy. Ponadto zamiast zwracać losową partycję jako a List, drukuje ją na konsoli.

Poniżej znajduje się program testowy, który uruchamia go 100 000 razy. Na przykład n=5, wszystkie zestawy znajdowały się w granicach 0,64% idealnej 1/7 w ostatnim biegu.

public class Partition {
    public static void main(String[] args) {
        Partition p = new Partition();
        for(int i=0;i<100000;i++){
            p.p(5);
            System.out.println();
        }
    }

    int[][]p;

    void p(int n){
        p=new int[n+1][n+1];
        int a=n,b=k(n,a),c,d;
        for(b*=Math.random();n>0;System.out.print(c+" "),n-=a=c)
            for(c=0;c++<(a<n?a:n)&b>=(d=k(n-c,c));b-=d);
    }

    int k(int n,int k){
        if(p[n][k]<1)
            for(int a=0,b=0;b<k&b++<n;p[n][k]=a)
                a+=k(n-b,b);
        return n>0?p[n][k]:1;
    }

}

CJam, 64 56 bajtów

ri_L{_0>{\,f{)_@1$-j+}{)@)2$+:Umr@<@@?U+}*}{!a\;}?}2j);p

Możesz to przetestować za pomocą tego skryptu:

ria100*{_L{_0>{\,f{)_@1$-j+}{)@)2$+:Umr@<@@?U+}*}{!a\;}?}2j);}%__|\f{_,\2$a-,-}2/p

Wyjaśnienie

ri_                  " Read an integer and duplicate. ";
L{                   " Create a memoized function of the maximum and the sum, which returns
                       a random partition, and the total number of partitions as the last item. ";
    _0>              " If sum > 0: ";
    {
        \,f{         " For I in 0..max-1: ";
            )_@1$-   " Stack: I+1 I+1 sum-I-1 ";
            j+       " Recursively call with the two parameters, and prepend I+1. ";
        }
        {            " Reduce on the results: ";
            )@)2$+   " Stack: partition1 total1 partition2 total1+total2 ";
            :Umr     " U = total1+total2, then generate a random number smaller than that. ";
            @<@@?    " If it is <total1, choose partition1, else choose partition2. ";
            U+       " Append the total back to the array. ";
        }*
    }
    {!a\;}?          " Else return [0] if negative, or [1] if zero. ";
}2j
);p                  " Discard the total and print. ";

Pyth, 64 bajty

Używa /programming//a/2163753/4230423, z wyjątkiem tego, że a) Brak pamięci podręcznej, ponieważ Pyth automatycznie zapamiętuje, b) Drukuje każdą zamiast dołączania do listy, i c) jest tłumaczone na Pyth.

M?smg-Gddr1hhS,GHG1Akd,QOgQQWQFNr1hhS,QkKg-QNNI<dKB-=dK)N=kN-=QN

Wyjaśnię to, kiedy będę miał czas, ale oto odpowiedni kod python:

g=lambda G,H: sum(map(lambda d:g(G-d, d), range(1, (H if H<G else G) + 1))) if G else 1
Q=input()
k,d = Q,random.randrange(g(Q, Q))
while Q:
    for N in range(1, min(k, Q) + 1):
        K = g(Q-N, N)
        if d < K:
            break
        d -= K
    print N
    k=N
    Q -= N

Edycja: W końcu zacząłem wyjaśniać:

M                Lambda g(G,H)
 ?         G     If G truthy
  s              Sum
   m             Map
    g            Recursive call
     -Gdd        G-d,d
    r            Range
     1           1 to
     h           +1
      hS         First element of sorted (does min)
       ,GH       From G and H
   1             Else 1
A                Double assign
 kd              Vars k and d
 ,               To vals
  Q              Q (evaled input)
  O              Randrange 0 till val
   gQQ           Call g(Q, Q)
WQ               While Q is truthy
 FN              For N in
  r              Range
   1             From one
   h             Till +1
    hS,QK        Min(Q,K)
  Kg             K=g(
   -QN           Q-N
   N             N
  I<dK           If d<k
   B             Break (implicit close paren)
  -=dk           Subtracts d-=k
 )               Close out for loop
 N               Prints N
 =kN             Set k=N
 -=QN            Subtracts Q-=N

Oktawa, 200

function r=c(m)r=[];a=eye(m);a(:,1)=1;for(i=3:m)for(j=2:i-1)a(i,j)=a(i-1,j-1)+a(i-j,j);end;end;p=randi(sum(a(m,:)));while(m>0)b=a(m,:);c=cumsum(b);x=min(find(c>=p));r=[r x];p=p-c(x)+b(x);m=m-x;end;end

Nie golfowany:

function r=c(m)
  r=[];
  a=eye(m);
  a(:,1)=1;
  for(i=3:m)
    for(j=2:i-1)
      a(i,j)=a(i-1,j-1)+a(i-j,j);
    end;
  end;
  p=randi(sum(a(m,:)));
  while(m>0)
    b=a(m,:);
    c=cumsum(b);
    x=min(find(cumsum(b)>=p));
    r=[r x];
    p=p-c(x)+b(x);
    m=m-x;
  end
end

Zbuduj kwadratową macierz, w której każda komórka (m, n) odzwierciedla liczbę partycji, mktórych największa liczba jest n, zgodnie z uprzejmym cytowaniem wyciągu Knuth @feersum. Na przykład 5,2daje nam 2, ponieważ istnieją dwie prawidłowe partycje 2,2,1i 2,1,1,1. 6,3daje nam do 3 3,1,1,1, 3,2,1a 3,3.

Teraz możemy deterministycznie znaleźć piąty rozdział. Tutaj generujemy pjako liczbę losową, ale możesz nieco zmienić skrypt, więc pjest parametr:

function r=c(m,p)
  r=[];
  a=eye(m);
  a(:,1)=1;
  for(i=3:m)
    for(j=2:i-1)
      a(i,j)=a(i-1,j-1)+a(i-j,j);
    end;
  end;
  while(m>0)
    b=a(m,1:m);
    c=cumsum(b);
    x=min(find(c>=p));
    r=[r x];
    p=p-c(x)+b(x);
    m=m-x;
  end
end

Możemy teraz deterministycznie pokazać, że każdy wynik zależy wyłącznie od p:

octave:99> for(i=1:7)
> c(5,i)
> end
ans =

   1   1   1   1   1

ans =

   2   1   1   1

ans =

   2   2   1

ans =

   3   1   1

ans =

   3   2

ans =

   4   1

ans =  5

Wracając do oryginału, w którym p jest generowane losowo, możemy być pewni, że każdy wynik jest jednakowo prawdopodobny.

R 198 bajtów

function(m){r=c();a=diag(m);a[,1]=1;for(i in 3:m)for(j in 2:(i-1))a[i,j]=a[i-1,j-1]+a[i-j,j];p=sample(sum(a[m,]),1);while(m>0){b=a[m,];c=cumsum(b);x=min(which(c>=p));r=c(r,x);p=p-c[x]+b[x];m=m-x};r}

Nie golfowany:

f <- function(m) {
    r <- c()
    a <- diag(m)
    a[, 1] <- 1
    for (i in 3:m)
        for (j in 2:(i-1))
            a[i, j] <- a[i-1, j-1] + a[i-j, j]
    p <- sample(sum(a[m, ]), 1)
    while (m > 0) {
        b <- a[m, ]
        c <- cumsum(b)
        x <- min(which(c >= p))
        r <- c(r, x)
        p <- p - c[x] + b[x]
        m <- m - x
    }
    return(r)
}

Ma tę samą strukturę, co świetne rozwiązanie @ dcsohl w Octave , a zatem opiera się również na wyciągu Knuth opublikowanym przez @feersum.

Przeredaguję to później, jeśli uda mi się wymyślić bardziej kreatywne rozwiązanie w R. W międzyczasie wszelkie uwagi są oczywiście mile widziane.

Java, 392 bajty

import java.util.*;Map a=new HashMap();List a(int b){List c=new ArrayList();int d=b,e=b(b,d),f=(int)(Math.random()*e),g,i;while(b>0){for(g=0;g++<Math.min(d, b);f-=i){i=b(b-g,g);if(f<i)break;}c.add(g);d=g;b-=g;}return c;}int b(int b,int c){if(b<1)return 1;List d=Arrays.asList(b,c);if(a.containsKey(d))return(int)a.get(d);int e,f;for(e=f=0;f++<Math.min(c, b);)e+=b(b-f,f);a.put(d,e);return e;}

Zadzwoń z a(n). Zwraca a Listz Integers

Zębaty:

import java.util.*;

Map a=new HashMap();

List a(int b){
    List c=new ArrayList();
    int d=b,e=b(b,d),f=(int)(Math.random()*e),g,i;
    while(b>0){
        for(g=0;g++<Math.min(d, b);f-=i){
            i=b(b-g,g);
            if(f<i)
                break;
        }
        c.add(g);
        d=g;
        b-=g;
    }
    return c;
}

int b(int b,int c){
    if(b<1)
        return 1;
    List d=Arrays.asList(b,c);
    if(a.containsKey(d))
        return(int)a.get(d);
    int e,f;
    for(e=f=0;f++<Math.min(c, b);)
        e+=b(b-f,f);
    a.put(d,e);
    return e;
}

Zaadaptowano z /programming//a/2163753/4230423 i grał w golfa

Jak to działa: Możemy obliczyć, ile partycji liczby całkowitej n istnieje w czasie O ( n ² ). Jako efekt uboczny tworzy to tabelę o rozmiarze O ( n ² ), którą możemy następnie wykorzystać do wygenerowania k- tego podziału n dla dowolnej liczby całkowitej k , w czasie O ( n ).

Niech więc total = liczba partycji. Wybierz losową liczbę k od 0 do całości - 1. Wygeneruj k- tą partycję.

Jak zwykle sugestie są mile widziane :)

Python 2, 173 bajtów

from random import*
N,M=input__
R=67;d=[(0,[])]*R*R
for k in range(R*R):p,P=d[k+~R];q,Q=d[k-k%R*R];d[k]=p+q+0**k,[[x+1 for x in Q],[1]+P][random()*(p+q)<p]
print d[N*R+M][1]

Rekurencyjnie tworzy słownik d, z kluczami kreprezentującymi parę (n,m)według k=67*n+m(przy użyciu gwarantowanej n<=65). Wpis jest krotką liczby podziałów nna mczęści i losową taką partycją. Liczby są obliczane według rekurencyjnej formuły (dzięki feersum za wskazanie tego)

f(n,m) = f(n-1,m-1) + f(n,n-m),

a losowa partycja jest aktualizowana poprzez wybranie jednej z dwóch jej gałęzi z prawdopodobieństwem proporcjonalnym do jej liczby. Aktualizacja odbywa się przez dodanie, poprzez dodanie 1dla pierwszego oddziału i zwiększenie każdego elementu dla drugiego.

Miałem dużo problemów z wydostaniem się poza granice mi nzliczaniem zera. Najpierw użyłem słownika, który domyślnie ma wartość 0 i pustą listę. Tutaj używam listy i uzupełniam ją tym domyślnym wpisem. Wskaźniki ujemne powodują, że lista jest odczytywana od końca, co daje domyślny wpis, że nic nie jest blisko końca, jak do tej pory osiągnięto, a obejścia dotykają tylko regionu, w którym m>n.

Kod maszynowy 80386, 105 bajtów

Hexdump kodu:

60 8b fa 81 ec 00 41 00 00 33 c0 8b f4 33 d2 42
89 14 06 42 33 ed 8b d8 03 2c 1e 2a fa 73 f9 83
c6 04 89 2c 06 42 3b d1 76 ea fe c4 3a e1 76 db
33 d2 0f c7 f0 f7 f5 86 e9 85 d2 74 1b 33 c0 8d
34 0c 39 14 86 77 03 40 eb f8 2b 54 86 fc 40 89
07 83 c7 04 2a e8 77 e1 42 89 17 83 c7 04 fe cd
7f f7 4a b6 41 03 e2 61 c3

Jako funkcja c: void random_partition(int n, int result[]);. Zwraca wynik jako listę liczb w dostarczonym buforze; nie oznacza w żaden sposób końca listy, ale użytkownik może odkryć koniec, kumulując liczby - lista kończy się, gdy suma jest równa n.

Jak korzystać (w Visual Studio):

#include <stdio.h>

__declspec(naked) void __fastcall random_partiton(int n, int result[])
{
#define a(byte) __asm _emit 0x ## byte
a(60) a(8b) a(fa) a(81) a(ec) a(00) a(41) a(00) a(00) a(33) a(c0) a(8b) a(f4) a(33) a(d2) a(42)
a(89) a(14) a(06) a(42) a(33) a(ed) a(8b) a(d8) a(03) a(2c) a(1e) a(2a) a(fa) a(73) a(f9) a(83)
a(c6) a(04) a(89) a(2c) a(06) a(42) a(3b) a(d1) a(76) a(ea) a(fe) a(c4) a(3a) a(e1) a(76) a(db)
a(33) a(d2) a(0f) a(c7) a(f0) a(f7) a(f5) a(86) a(e9) a(85) a(d2) a(74) a(1b) a(33) a(c0) a(8d)
a(34) a(0c) a(39) a(14) a(86) a(77) a(03) a(40) a(eb) a(f8) a(2b) a(54) a(86) a(fc) a(40) a(89)
a(07) a(83) a(c7) a(04) a(2a) a(e8) a(77) a(e1) a(42) a(89) a(17) a(83) a(c7) a(04) a(fe) a(cd)
a(7f) a(f7) a(4a) a(b6) a(41) a(03) a(e2) a(61) a(c3)
}

void make_stack() // see explanations about stack below
{
    volatile int temp[65 * 64];
    temp[0] = 999;
}

int main()
{
    int result[100], j = 0, n = 64, counter = n;
    make_stack(); // see explanations about stack below

    random_partiton(n, result);

    while (counter > 0)
    {
        printf("%d ", result[j]);
        counter -= result[j];
        ++j;
    }
    putchar('\n');
}

Przykładowe dane wyjściowe (przy n = 64):

21 7 4 4 3 3 3 3 2 2 2 2 2 1 1 1 1 1 1

To wymaga wielu wyjaśnień ...

Oczywiście użyłem algorytmu, którego używali wszyscy inni; nie było wyboru z wymogiem złożoności. Więc nie muszę zbytnio wyjaśniać algorytmu. Tak czy siak:

Mam f(n, m)na myśli liczbę podziałów nelementów wykorzystujących części nie większe niż m. Przechowuję je w tablicy 2-D (zadeklarowanej w C jako f[65][64]), gdzie jest pierwszy indeks n, a drugi m-1. Uznałem, że wsparcie n=65to zbyt duży problem, więc porzuciłem to ...

Oto kod C, który oblicza tę tabelę:

#define MAX_M 64
int f[(MAX_M + 1) * MAX_M];
int* f2;
int c; // accumulates the numbers needed to calculate f(n, m)
int m;
int k; // f(k, m), for various values of k, are accumulated
int n1;

for (n1 = 0; n1 <= n; ++n1)
{
    f2 = f;
    f2[n1 * MAX_M] = 1;
    for (m = 2; m <= n; ++m)
    {
        c = 0;
        k = n1;
        while (k >= 0)
        {
            c += f2[k * MAX_M];
            k -= m;
        }
        ++f2;
        f2[n1 * MAX_M] = c;
    }
}

Ten kod ma nieco zaciemniony styl, dzięki czemu można go łatwo przekonwertować na język asemblera. Oblicza elementy do f(n, n), czyli liczby podziałów nelementów. Po zakończeniu tego kodu zmienna tymczasowa czawiera potrzebny numer, którego można użyć do wybrania losowego podziału na partycje:

int index = rand() % c;

Później indexjest on konwertowany do wymaganego formatu (listy liczb) za pomocą wygenerowanej tabeli.

do {
    if (index == 0)
        break;

    m = 0;
    f2 = &f[n * MAX_M];
    while (f2[m] <= index)
    {
        ++m;
    }

    index -= f2[m-1];
    ++m;
    *result++ = m;
    n -= m;
} while (n > 0);

do {
    *result++ = 1;
    --n;
} while (n > 0);

Ten kod jest również zoptymalizowany pod kątem konwersji na język asemblera. Istnieje mały „błąd”: jeśli partycjonowanie nie zawiera żadnej 1liczby na końcu, ostatnia pętla napotyka n = 0i generuje niepotrzebny 1element. Nie szkodzi to jednak, ponieważ kod drukujący śledzi sumę liczby i nie drukuje tej dodatkowej liczby.

Po przekonwertowaniu na zestaw wbudowany ten kod wygląda następująco:

__declspec(naked) void _fastcall random_partition_asm(int n, int result[])
{
    _asm {
        pushad;

        // ecx = n
        // edx = m
        // bh = k; ebx = k * MAX_M * sizeof(int)
        // ah = n1; eax = n1 * MAX_M * sizeof(int)
        // esp = f
        // ebp = c
        // esi = f2
        // edi = result

        mov edi, edx;
        sub esp, (MAX_M + 1) * MAX_M * 4; // allocate space for table
        xor eax, eax;
    row_loop:
        mov esi, esp;
        xor edx, edx;
        inc edx;
        mov dword ptr [esi + eax], edx;
        inc edx;

    col_loop:
        xor ebp, ebp;
        mov ebx, eax;

    sum_loop:
        add ebp, [esi + ebx];
        sub bh, dl;
        jae sum_loop;

        add esi, 4;
        mov [esi + eax], ebp;
        inc edx;
        cmp edx, ecx;
        jbe col_loop;

        inc ah;
        cmp ah, cl;
        jbe row_loop;

        // Done calculating the table

        // ch = n; ecx = n * MAX_M * sizeof(int)
        // eax = m
        // ebx = 
        // edx = index
        // esp = f
        // esi = f2
        // ebp = c
        // edi = result

        xor edx, edx;
        rdrand eax; // generate a random number
        div ebp; // generate a random index in the needed range
        xchg ch, cl; // multiply by 256

    n_loop:
        test edx, edx;
        jz out_trailing;
        xor eax, eax;
        lea esi, [esp + ecx];

    m_loop:
        cmp [esi + eax * 4], edx;
        ja m_loop_done;
        inc eax;
        jmp m_loop;
    m_loop_done:

        sub edx, [esi + eax * 4 - 4];
        inc eax;
        mov [edi], eax;
        add edi, 4;
        sub ch, al;
        ja n_loop;

    out_trailing:
        inc edx;
    out_trailing_loop:
        mov dword ptr [edi], edx;
        add edi, 4;
        dec ch;
        jg out_trailing_loop;

        dec edx;
        mov dh, (MAX_M + 1) * MAX_M * 4 / 256;
        add esp, edx;
        popad;
        ret;
    }
}

Kilka ciekawych rzeczy do zapamiętania:

• Generowanie liczby losowej zajmuje zaledwie 3 bajty kodu maszynowego ( rdrandinstrukcja)
• Przez przypadek rozmiar tabeli wynosi 64, więc rozmiar jednego wiersza wynosi 256 bajtów. Używam tego do przechowywania indeksów wierszy w rejestrach „bajtowych” jak ah, co daje mi automatyczne mnożenie przez 256. Aby skorzystać z tego, poświęciłem wsparcie n = 65. Mam nadzieję, że mogę być usprawiedliwiony za ten grzech ...

• Przydział miejsca na stosie jest wykonywany przez odjęcie 0x4100 od rejestru wskaźnika stosu esp. To jest instrukcja 6-bajtowa! Dodając ponownie ten numer, udało mi się to zrobić w 5 bajtach:

      dec edx; // here edx = 1 from earlier calculations
      mov dh, (MAX_M + 1) * MAX_M * 4 / 256; // now edx = 0x4100
      add esp, edx; // this deallocates space on stack
  

• Podczas debugowania tej funkcji w MS Visual Studio dowiedziałem się, że ulega awarii, gdy zapisuje dane do miejsca przydzielonego na stosie! Po kilku kopaniach odkryłem pewien rodzaj ochrony przed przepełnieniem stosu: system operacyjny wydaje się przydzielać tylko bardzo ograniczony zakres adresów wirtualnych dla stosu; jeśli funkcja uzyskuje dostęp do adresu zbyt daleko, system operacyjny zakłada, że ​​jest przekroczony i zabija program. Jeśli jednak funkcja ma wiele zmiennych lokalnych, system operacyjny wykonuje dodatkową „magię”, aby działała. Więc muszę wywołać pustą funkcję, która ma dużą tablicę przydzieloną na stosie. Po powrocie tej funkcji przydzielane są dodatkowe strony maszyn wirtualnych i można z nich korzystać.

      void make_stack()
      {
          volatile int temp[65 * 64];
          temp[0] = 999; // have to "use" the array to prevent optimizing it out
      }