Created
September 26, 2012 20:57
-
-
Save joriki/3790542 to your computer and use it in GitHub Desktop.
Compute the fraction of combinations of Set cards that contain a Set; see http://math.stackexchange.com/questions/202862
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Question202862 { | |
final static int nfeatures = 4; | |
final static int nvalues = 3; | |
final static int ncards = (int) Math.pow (nvalues,nfeatures); | |
static int thirdFeature (int f1,int f2) { | |
return f1 == f2 ? f1 : 3 - (f1 + f2); | |
} | |
static int thirdCard (int c1,int c2) { | |
int thirdCard = 0; | |
for (int i = 0,pow = 1;i < nfeatures;i++,pow *= nvalues) | |
thirdCard += pow * thirdFeature ((c1 / pow) % nvalues,(c2 / pow) % nvalues); | |
return thirdCard; | |
} | |
static int [] nvetos = new int [ncards]; | |
final static int ndealt = 9; | |
static int [] dealt = new int [ndealt + 1]; | |
static void add (int i,int sign) { | |
for (int j = 0;j < ndealt;j++) | |
if (j != i) | |
nvetos [thirdCard (dealt [i],dealt [j])] += sign; | |
} | |
static void change (int i,int value) { | |
add (i,-1); | |
dealt [i] = value; | |
add (i,1); | |
} | |
public static void main (String [] args) { | |
dealt [ndealt] = ncards; // sentinel | |
for (int i = 0;i < ndealt;i++) | |
dealt [i] = i; | |
for (int i = 1;i < ndealt;i++) | |
for (int j = 0;j < i;j++) | |
nvetos [thirdCard (dealt [i],dealt [j])]++; | |
long count = 0; | |
long total = 0; | |
outer: | |
for (;;) { | |
// check this combination for a set | |
for (int i = 0;i < ndealt;i++) | |
if (nvetos [dealt [i]] != 0) { | |
count++; | |
break; | |
} | |
total++; | |
// move to the next combination | |
for (int i = ndealt;;i--) { | |
if (i == 2) | |
break outer; | |
if (dealt [i - 1] != dealt [i] - 1) { | |
change (i - 1,dealt [i - 1] + 1); | |
while (i < ndealt) { | |
change (i,dealt [i - 1] + 1); | |
i++; | |
} | |
break; | |
} | |
} | |
} | |
System.out.println (count + " / " + total + " = " + count / (double) total); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment