Card pair probability

Question

Given a deck consisting of N copies of cards with integer values [1,M] for a total of N*M cards, compute the probability that a card with the value of 1 is adjacent to a card with the value of 2.

Your solution may be exact or approximated, and it does not need to be the same for every run given the same inputs. The given answer should be within +/-5% of the true solution (barring really rare chances the RNG is not in your favor). Your program should give the answer in a reasonable amount of time (say, less than 10 minutes on whatever hardware you have). You may assume that M and N are reasonable small and error checking is not required.

The deck is not cyclical, so if the first card is a 1 and the last card is a 2, this does not meet the adjacency requirements.

As a test case, for N=4 and M=13 (a standard 52-card deck) the expected solution is ~48.6%.

Here is an example un-golfed implementation in Python+NumPy using random shuffles:

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

The output may be in any form you find convenient (function return value, terminal output, file, etc.), and input may be in any form you find convenient (function parameter, terminal input, command line arg, etc.)

Standard loop-holes apply.

This is code golf, the shortest code (in bytes) wins.

Leaderboard

var QUESTION_ID=67431,OVERRIDE_USER=31729;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

MATL, 44 46 bytes

This uses release 3.1.0 of the language, which is earlier than this challenge.

The computation is done with a loop that draws 1000 random realizations. It takes a couple of seconds to run. It could be done faster in a vectorized way. Input is of the form [N M].

Old version: generates a random deck of cards and checks it twice: first in the forward and then in the backward direction.

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

New version: generates a random deck of cards and then appends a flipped version of it with a 0 in between. That way checking can be done just once, in the forward direction. This saves two bytes.

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

Example

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

Explanation

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

Answer 2

Pyth, 23 22 bytes

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

Runs 10000 iterations. The number can be changed at no byte cost. Input is newline separated. Takes about 9 seconds on my computer.

Demonstration

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.

Answer 3

LabVIEW, 58 LabVIEW Primitives

creats card arrays then shuffles them. Search for 1s then check adjacent cards for 2s.

Answer 4

MATL, 44 38 bytes

This also uses MATL version 3.1.0, which is earlier than this challenge.

New version, thanks to Luis Mendo for saving 4 bytes!

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

Old version (44 bytes):

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

Explanation

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

For example,

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

Note (21/5/16): As of MATL release 18.0.0, X+ has been removed, but Y+ can be used in its place. The changes from MATL version 3.1.0 to 18.0.0 mean that this answer can now be written in just 31 bytes, *xO1e4:"2:Gtb*Z@w\TT2&Y+1=ah]Ym.

Answer 5

Pyth, 16 bytes

JE?>J1-1^-1c2JQZ

Demonstration.

This follows the

• make an educated guess,
• check that it's close enough,
• repeat

strategy of programming. The winning educated guess in this case is

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

which roughly says that there are N chances to fall into buckets, and fraction of valid buckets is 2 / M. The buckets being slots places next to 0s, and the chances being 1s.

The error never seems to go above 3% (surprisingly), and seems to converge to 0% as the parameters get larger (as I would expect).

Input is newline separated.

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

You can save a character if you accept the plainly obvious fact that False == 0, and do JE&>J1-1^-1c2JQ instead.

Answer 6

Mathematica, 93 92 91 bytes

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

Still looking for a closed form...