Prawdopodobieństwo pary kart

9

Biorąc pod uwagę talię składającą się z N kopii kart o wartościach całkowitych [ 1 , M ] dla łącznie N * M kart, oblicz prawdopodobieństwo, że karta o wartości 1 przylega do karty o wartości 2 .

Twoje rozwiązanie może być dokładne lub przybliżone i nie musi być takie samo dla każdego przebiegu przy tych samych danych wejściowych. Podana odpowiedź powinna mieścić się w granicach +/- 5% prawdziwego rozwiązania (z wyjątkiem naprawdę rzadkich szans, że RNG nie jest na twoją korzyść). Twój program powinien udzielić odpowiedzi w rozsądnym czasie (powiedzmy mniej niż 10 minut na dowolnym sprzęcie). Możesz założyć, że M i N są rozsądnie małe i sprawdzanie błędów nie jest wymagane.

Talia nie jest cykliczna, więc jeśli pierwsza karta to 1, a ostatnia karta to 2 , nie spełnia to wymagań sąsiednich.

W przypadku testowym dla N = 4 i M = 13 (standardowa talia 52 kart) oczekiwane rozwiązanie wynosi ~ 48,6%.

Oto przykład implementacji bez golfa w Pythonie + NumPy przy użyciu losowych losowań:

from __future__ import division
from numpy import *

def adjacent(N, M):
    deck = array([i for i in range(1, M+1)]*N)
    trials = 100000
    count = 0
    for i in range(trials):
        random.shuffle(deck)
        ores = (deck == 1)
        tres = (deck == 2)
        if(any(logical_and(ores[1:], tres[:-1])) or
           any(logical_and(ores[:-1], tres[1:]))):
            count += 1
    return count/trials

Dane wyjściowe mogą być w dowolnej dogodnej dla ciebie formie (wartość zwracana przez funkcję, wyjście terminala, plik itp.), A dane wejściowe mogą być w dowolnej dogodnej dla ciebie formie (parametr funkcji, wejście terminala, argument linii poleceń itp.)

Obowiązują standardowe otwory przelotowe.

To jest kod golfowy, wygrywa najkrótszy kod (w bajtach).

Tabela liderów

Pokaż fragment kodu

code-golf  probability-theory  simulation 
— helloworld922
źródło
1
sąsiedztwo, które nie owija się wokół, jest zwodniczo skomplikowanym zwrotem akcji
— Sparr
@Sparr Dałeś mi pomysł! :-)
— Luis Mendo

Odpowiedzi:

2

Pyth, 23 22 bajtów

csm}1sM.:.S*vzUQ2J^T4J

Uruchamia 10000 iteracji. Liczbę można zmienić bez kosztu bajtu. Wejście jest oddzielone znakiem nowej linii. Na moim komputerze trwa około 9 sekund.

Demonstracja

csm}1sM.:.S*vzUQ2J^T4J
                 J^T4     J = 10000
  m              J        Do the following J times.
           *vzUQ          Set up the deck. (0 .. n-1, repeated m times.)
         .S               Shuffle the deck.
       .:       2         Find all 2 elment substrings.
     sM                   Add them up.
   }1                     Check if any pairs add to 1 ([0, 1] or [1, 0])
 s                        Add up the results (True = 1, False = 0)
c                     J   Divide by J.
— isaacg
źródło
2

MATL , 44 46 bajtów

Używa wersji 3.1.0 języka, która jest wcześniejsza niż to wyzwanie.

Obliczenia wykonuje się za pomocą pętli, która rysuje 1000 losowych realizacji. Uruchomienie zajmuje kilka sekund. Można to zrobić szybciej w wektorowy sposób. Dane wejściowe mają formę [N M].

Stara wersja : generuje losową talię kart i sprawdza ją dwukrotnie: najpierw do przodu, a następnie do tyłu.

itpw1)1e3:"2$twZ@w/Y]t1HhXfnwH1hXfn|bb]xxN$hYm

Nowa wersja : generuje losową talię kart, a następnie dołącza jej odwróconą wersję z pośrodkiem 0. W ten sposób sprawdzenie można wykonać tylko raz, w kierunku do przodu. To oszczędza dwa bajty.

itpw1)1e3:"2$twZ@w/Y]tP0whh1HhXfngbb]xxN$hYm

Przykład

>> matl itpw1)1e3:"2$twZ@w/Y]tP0whh1HhXfngbb]xxN$hYm
> [4 13]
0.469

Wyjaśnienie

i                 % input: [N M]
tpw1)             % produce N*M and N
1e3:"             % repeat 1000 times
  2$twZ@w/Y]      % produce random deck of cards from 1 to N*M
  tP0whh          % append 0 and then flipped version of deck
  1Hh             % vector [1 2]
  Xf              % find one string/vector within another                          
  ng              % was it found at least once?
  bb              % bubble up element in stack, twice                     
]                 % end                                                     
xx                % delete top of the stack, twice
N$h               % vector with all elements in stack
Ym                % mean value
— Luis Mendo
źródło
1

Pyth, 16 bajtów

JE?>J1-1^-1c2JQZ

Demonstracja.

To wynika z

  • zgadnij,
  • sprawdź, czy jest wystarczająco blisko,
  • powtarzać

strategia programowania. W tym przypadku zwycięską zgadywanką jest

1 - (1 - 2 / M) ** N

co z grubsza mówi, że są Nszanse, aby wpaść w segmenty, a odsetek prawidłowych segmentów to 2 / M. Wiadra są gniazdami umieszczonymi obok 0s, a szanse są 1s.

Błąd nigdy nie wydaje się przekraczać 3% (zaskakująco) i wydaje się zbliżać do 0%, gdy parametry stają się większe (jak bym się spodziewał).

Wejście jest oddzielone znakiem nowej linii.

              Q  Q = eval(input())
JE               J = eval(input())
  ?>J1           if J > 1
      -1^-1c2JQ  then 1 - (1 - 2 / J) ** Q
               Z else 0

Możesz uratować postać, jeśli zaakceptujesz oczywisty fakt, że False == 0to zrobisz, i JE&>J1-1^-1c2JQzamiast tego.

— Veedrac
źródło
To zdarza się po raz pierwszy w Pyth (i moja pierwsza odpowiedź), dlatego krytyka i pomoc są szczególnie mile widziane.
— Veedrac
1

MATL , 44 38 bajtów

To również używa MATL w wersji 3.1.0 , która jest wcześniejsza niż to wyzwanie.

Nowa wersja, dzięki Luisowi Mendo za zapisanie 4 bajtów!

iiXI*XJxO1e4XH:"JZ@I\TTo3X53$X+1=a+]H/

Stara wersja (44 bajty):

OiitXIx*XJx1e4XH:"JJZrI\[1 1]3X5,3$X+1=a+]H/

Wyjaśnienie

i               % take input for N
i               % take input for M
XI              % save M into clipboard I
*XJ             % multiply N and M and store in clipboard J
x               % clear the stack
O               % make a zero to initialise count of pairs
1e4XH:"         % 1e4=10000, XH saves into clipboard H, : makes the vector 1:1e4
                % which is used to index a for loop, started using "
    JZ@         % Use randperm to generate a random permutation of the vector 1:N*M
    I\          % take the result mod M, now each card has a value one less than before
    TTo3X53$X+  % convolve vector of card values with [1 1] to do pairwise summation
    1=a         % find if any sums equal 1, which means there is a [0 1] or [1 0]         
    +           % add the logical value to the count of pairs
]
H/              % divide the count by the number of deals to get the probability

Na przykład,

>> matl 'iiXI*XJxO1e4XH:"JZ@I\TTo3X53$X+1=a+]H/'
> 4
> 13
0.4861

Uwaga (21/5/16): Od wersji MATL 18.0.0 X+został usunięty, ale Y+można go użyć zamiast niego. Zmiany od wersji 3.1.0 Mátl do 18.0.0 oznaczać, że odpowiedź ta może być teraz pisane w ciągu zaledwie 31 bajtów *xO1e4:"2:Gtb*Z@w\TT2&Y+1=ah]Ym.

— David
źródło
Wiem, że jest już odpowiedź MATL, ale myślę, że metody są zupełnie inne, więc wciąż to opublikowałem.
— David
Uwielbiam splot!
— Luis Mendo
Można zaoszczędzić trochę zmienia [1 1]się TTo. Ponadto nie potrzebujesz przecinka
— Luis Mendo
@LuisMendo dzięki! Pomyślałem, że musi być lepszy sposób!
— David
Teraz widzę, jak działa tutaj splot. Używanie nazw kart opartych na 0 było bardzo sprytne!
— Luis Mendo
0

Mathematica, 93 92 91 bajtów

N@Count[RandomSample@Flatten[Range@#~Table~{#2}]~Table~{a=1*^5},{b=___,1,2,b}|{b,2,1,b}]/a&

Wciąż szukam zamkniętego formularza ...

— LegionMammal978
źródło
będzie obejmować zagnieżdżoną pętlę obliczeń permutacji.
— Sparr
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.