Ponder These
- How good does a card shark have to be at cutting and riffle shuffling to have an advantage at cards?
- How many distinct permutations are possible when n cards are perfectly riffle shuffled repeatedly?
Java Program
public class CardShark
{
public static void main(String[] args)
{
List list = new List();
for (int i = 0; i < 10000; i++)
{
args = RiffleShuffler.shuffle(args);
list.update(args);
}
for (Node i = list.head; i != null; i = i.next)
{
System.out.println(i.value + ": " + i.tally);
}
}
}
class RiffleShuffler
{
public static double cutSkill = 1;
public static double riffleSkill = 1;
private static int cut(int n)
{
int m = n / 2;
while (m > 0 && Math.random() > cutSkill)
m--;
while (m < n && Math.random() > cutSkill)
m++;
return m;
}
public static String[] shuffle(String[] a)
{
int n = a.length;
int m = cut(n);
String[] shuffled = new String[n];
int i = 0, j = m, k = 0;
while (i < m || j < n)
{
if (i < m && (Math.random() < riffleSkill || j == n))
{
shuffled[k++] = a[i++];
}
if (j < n && (Math.random() < riffleSkill || i == m))
{
shuffled[k++] = a[j++];
}
}
return shuffled;
}
}
class KnuthShuffler
{
public static String[] shuffle(String[] a)
{
int last = a.length - 1;
for (int i = 0; i < last; i++)
{
int r = Util.random(i, last);
Util.swap(a, i, r);
}
return a;
}
}
class Util
{
public static int random(int i, int j)
{
if (j < i)
{
return random(j, i);
}
double r = Math.random(); // 0 <= r < 1
r *= (1 + j - i); // stretch r
r += i; // shift r
return (int) r; // drop fractional part
}
public static void swap(String[] a, int i, int j)
{
String tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
class List
{
Node head = null;
public void update(String[] a)
{
String s = "";
for (String each : a)
{
s += each;
}
for (Node i = head; i != null; i = i.next)
{
if (s.equals(i.value))
{
i.tally++;
return;
}
}
head = new Node(s, head);
}
}
class Node
{
Node next;
String value;
int tally = 1;
public Node(String s, Node n)
{
value = s;
next = n;
}
}
See Also
