Wejście

Macierz Mreprezentowana jako dwie oddzielone spacjami linie liczb całkowitych. Każda linia będzie miała tę samą liczbę liczb całkowitych, a każda liczba całkowita będzie wynosić -1 lub 1. Liczba liczb całkowitych w wierszu będzie wynosić co najwyżej 20. Mbędzie zatem 2, ngdzie njest liczba liczb całkowitych w każdej z dwóch linii.

Twój kod powinien być kompletnym programem. i zaakceptuj dane wejściowe w standardowym pliku lub z pliku (to twój wybór). Możesz zaakceptować dane wejściowe ze standardowego wejścia, pliku lub po prostu jako parametr. Jeśli jednak zrobisz to drugie, podaj wyraźny przykład działania kodu i pamiętaj, że musi to być kompletny program i jak macierz Mbędzie reprezentowana na wejściu. Innymi słowy, prawdopodobnie będziesz musiał parsować.

Wynik

Binarny Shannon entropia rozkładu M*x, gdzie elementy xsą równomiernie i są niezależnie wybrane z {-1,1}. xto nwymiarowy wektor kolumny.

Entropia dyskretnego rozkładu prawdopodobieństwa jest

- sum p_i log_2(p_i)

W tym przypadku p_iprawdopodobieństwo itego unikalnego jest możliwe M*x.

Przykład i pomocne wskazówki

Jako sprawdzony przykład niech Mbędzie macierz

-1 1
-1 -1

Teraz spójrz na wszystkie 2^2możliwe wektory x. Dla każdego obliczamy M*xi umieszczamy wszystkie wyniki w tablicy (4-elementowa tablica 2-komponentowych wektorów). Chociaż dla każdego z 4 wektorów istnieje prawdopodobieństwo jego wystąpienia 1/2^2 = 1/4, interesuje nas tylko liczba przypadków, w których wystąpi każdy unikalny wektor wynikowy M*x, dlatego podsumowujemy indywidualne prawdopodobieństwa konfiguracji prowadzących do tych samych unikalnych wektorów. Innymi słowy, możliwe unikalne M*xwektory opisują wyniki rozkładu, który badamy, i musimy określić prawdopodobieństwo każdego z tych wyników (które z założenia zawsze będą całkowitą wielokrotnością 1/2^2lub 1/2^nogólnie) do obliczyć entropię.

W ogólnym nprzypadku, w zależności od Mmożliwych wyników M*xmoże wahać się od „wszystkie różne” (w tym przypadku mamy nwartości iin p_i, i każda p_ijest równa 1/2^n), do „wszystkie takie same” (w tym przypadku jest jedna możliwa wynik i p_1 = 1).

W szczególności dla powyższej 2x2macierzy Mmożemy przekonać się, mnożąc ją przez cztery możliwe konfiguracje ( [+-1; +-1]), że każdy powstały wektor jest inny. Zatem w tym przypadku są cztery wyniki, a w konsekwencji p_1 = p_2 = p_3 = p_4 = 1/2^2 = 1/4. Przypominając, że log_2(1/4) = -2mamy:

- sum p_i log_2(p_i) = -(4*(-2)/4) = 2

Zatem końcowy wynik dla tej macierzy wynosi 2.

Przypadki testowe

Wejście:

-1 -1 
-1 -1

Wynik:

1.5

Wejście:

-1 -1 -1 -1
-1 -1 -1 -1

Wynik:

2.03063906223

Wejście:

-1  -1  -1  1
1  -1  -1  -1

Wynik:

3

Mathematica, 48 68 bajtów

Edycja: Dodano proces wstępny do akceptowania ciągu jako parametru.

Przy pomocy Tuplesi Entropywdrożenie jest zarówno zwięzłe, jak i czytelne.

Entropy[2,{-1,1}~Tuples~Length@#.#]&@Thread@ImportString[#,"Table"]&

gdzie Tuples[{-1,1},n]daje wszystkie możliwe nliczby z {-1,1}i Entropy[2,list]daje entropię informacji base-2.

Jedną z fajnych rzeczy jest to, że Mathematica faktycznie zwróci dokładne wyrażenie:

%["-1 -1 \n -1 -1"]
(* 3/2 *)

Przybliżony wynik można uzyskać za pomocą dodatkowego .dodanego ( Entropy[2., ...).

Perl, 160 159 141 bajtów

zawiera +1 dla -paktualizacji od 141 bajtów

@y=(@z=/\S+/g)x 2**@z;@{$.}=map{evals/.1/"+".$&*pop@y/egr}glob"{-1,+1}"x@z}{$H{$_.$2[$i++]}++for@1;$\-=$_*log($_/=1<<@z)/log 2 for values%H;

Dane wejściowe są oczekiwane STDINjako 2 linie składające się z oddzielonych spacjami 1lub -1.
Uruchom jako perl -p 140.pl < inputfile.

Nie wygra żadnych nagród, ale pomyślałem, że podzielę się swoim wysiłkiem.
Wyjaśniono:

    @y=                             # @y is (@z) x (1<<$n)
       (@z = /\S+/g)                # construct a matrix row from non-WS
       x 2**@z;                     # repeat @z 2^$n times
    @{$.} = map {                   # $.=$INPUT_LINE_NUMBER: set @1 or @2
      eval s/.1/"+".$&*pop@y/egr    # multiply matrix row with vector
    } glob "{-1,+1}" x @z           # produce all possible vectors

}{                                  # `-p` trick: end `while(<>)`, reset `$_`

$H{ $_ . $2[$i++] }++               # count unique M*x columns
    for @1;

$\ -= $_ * log($_/=1<<@z) / log 2   # sum entropy distribution
        for values %H;

DANE

• aktualizacja 159: zapisz 1, eliminując (), używając **zamiast <<.
• aktualizacja 141: zapisz 18, używając $.i -p.

Pyth, 37 bajtów

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8

Zestaw testowy

Jest to nieco trudniejsze, gdy trzeba ręcznie zaimplementować mnożenie macierzy.

Wyjaśnienie:

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8
       JrR7.z                            Parse input into matrix, assign to J.
  _B1                                    [1, -1]
K^   lhJ                                 All +-1 vectors of length n, assign to K.
                           m       K     Map over K
                            m     J      Map over the rows of J
                             s*Vdk       Sum of vector product of vector and row.
                          S              Sort
                         r          8    Run length encode.
                       hM                Take just occurrence counts.
                   cRlK                  Divide by len(K) to get probabilities.
               *Lld                      Multiply each probabiliity by its log.
              s                          Sum.
             _                           Negate. Print implicitly.

MATLAB, 196 194 187 184 126 154 bajtów

(Dodatkowe 28 bajtów od 126 do 154 wynika z parsowania danych wejściowych: teraz kod akceptuje dane wejściowe jako dwa wiersze liczb oddzielonych spacjami.)

f=@()str2num(input('','s'));M=[f();f()];n=size(M,2);x=(dec2bin(0:n^2-1,n)-48.5)*2*M';[~,~,c]=unique(x,'rows');p=accumarray(c,1)/2^n;disp(-sum(p.*log2(p)))

Wersja bez golfa:

f=@()str2num(input('','s'));        % shorthand for "read a line as vector"
M=[f();f()];                        % read matrix
n=size(M,2);                        % get lenght of vectors

x=(dec2bin(0:n^2-1,n)-48.5)*2*M';   % generate every configuration
                                    %    using binary encoding
[~,~,c]=unique(x,'rows');           % get unique rows of (Mx)^T
p=accumarray(c,1)/2^n;              % count multiplicities and normalize
disp(-sum(p.*log2(p)))              % use definition of entropy

Mógłbym pozbyć się 6 bajtów, gdyby ans = ...dozwolony był typ wyjściowy, nigdy nie jestem tego pewien.

Z przykrością stwierdzam, że moje oryginalne i na pewno dowcipne rozwiązanie było zdecydowanie zbyt wolne od mojego obecnego rozwiązania. To także pierwszy raz, kiedy używam accumarray. Aplikacja z sześcioma parametrami wejściowymi musi jednak jeszcze poczekać :)

Wyjścia (następujące format long):

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
   1.500000000000000

[-1 -1 -1 -1
-1 -1 -1 -1]
   2.030639062229566

[-1  -1  -1  1
1  -1  -1  -1]
     3

Dane wyjściowe z wartością domyślną format short g:

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
          1.5

[-1 -1 -1 -1
-1 -1 -1 -1]
       2.0306

[-1  -1  -1  1
1  -1  -1  -1]
     3