List Example: Rolling Dice

If you roll two dice what are the odds of rolling a given number?

Solution: try all 6x6 = 36 possible rolls and compute the sum for each roll. Store the result in a table like this:

List Example: Rolling Dice

final int SIZE = 13;
List<Integer> roll = new ArrayList<Integer>(SIZE);

// initialize all elements to 0
for (int i = 0; i < SIZE; i++)
{
   roll.add(0);
}

final int MIN = 1;
final int MAX = 6;

for (int dice1 = MIN; dice1 <= MAX; dice1++)
{
   for (int dice2 = MIN; dice2 <= MAX; dice2++)
   {
      int sum = dice1 + dice2;
      int oldSum = roll.get(sum);
      roll.set(sum, oldSum + 1);
   }
}

See Dice.java.

List Example: Coin-flipping

If you flip a fair coin N times how many heads do you expect to see? How often do you expect to see N / 4 heads?

You could solve the problem using statistics (google "binomial distribution"), or you could write a simulation.

Solution: simulate flipping a coin N times, repeat M times, and store the results in a table like this:

Coin-flipping Simulation

1. Create a list heads of length N + 1.
2. Fill heads with all zeros
3. Repeat the following M times:
   1. Repeat the following N times:
      1. Generate a random boolean (true : heads, false : tails); keep track of the number of heads n
   2. Add 1 to element at index n in heads

Coin-flipping Simulation

final int M = 100000;
final int N = 20;

List<Integer> heads = new ArrayList<Integer>();
for (int i = 0; i <= N; i++)
{
   heads.add(0);
}

Random rng = new Random();
for (int trial = 0; trial < M; trial++)
{
   int count = 0;
   for (int flip = 0; flip < N; flip++)
   {
      if (rng.nextBoolean())
      {
         count++;
      }
   }
   int index = count;
   int oldCount = heads.get(index);
   heads.set(index, oldCount + 1);
}

See CoinFlip.java.

Check if a List is Sorted

Sorted lists are very useful; how can you tell if an existing list is already sorted in ascending order (from smallest to largest)?

A list is sorted if:
element (i) is less than or equal to element (i + 1) for i = 0, 1, ..., (size - 2).

Check if a List is Sorted

In this case, you cannot correctly use <= with object references, but you can use compareTo.

// t is a List<E> where E implements Comparable<E>

boolean isSorted = true;
for (int i = 0; i < t.size() - 1; i++)
{
   isSorted = isSorted &&
              t.get(i).compareTo(t.get(i + 1)) <= 0; 
}

or perhaps more pragmatically:

// t is a List<E> where E implements Comparable<E>

boolean isSorted = true;
for (int i = 0; i < t.size() - 1; i++)
{
   if (t.get(i).compareTo(t.get(i + 1)) > 0)
   {
      isSorted = false;
      break;
   }
}

Bogosort

Bogosort is a perversely awful sorting algorithm; its complexity is O(N ⋅ N!).

while the list is not sorted
   randomly shuffle the elements in the list

Bogosort

Unfortunately, this algorithm is easy to implement in Java using Collections.shuffle.

boolean isSorted = false;
while (!isSorted)
{
   Collections.shuffle(t);
   
   // this part checks for sorted order
   isSorted = true;
   for (int i = 0; i < t.size() - 1; i++)
   {
      isSorted = isSorted &&
                 t.get(i).compareTo(t.get(i + 1)) <= 0; 
   }
}

See BogoSort.java.

Bozosort

Bozosort is another perversely awful sorting algorithm; its complexity is O(N!).

while the list is not sorted
   pick two elements at random and swap them

Bozosort

Like bogosort, bozosort is easy to implement in Java.

// t is a List<Integer>

Random rng = new Random();

boolean isSorted = false;
while (!isSorted)
{
   int index1 = rng.nextInt(t.size());
   int index2 = rng.nextInt(t.size());

   Integer tmp = t.get(index1);
   t.set(index1, t.get(index2));
   t.set(index2, tmp);
   
   // this part checks for sorted order
   isSorted = true;
   for (int i = 0; i < t.size() - 1; i++)
   {
      isSorted = isSorted &&
                 t.get(i).compareTo(t.get(i + 1)) <= 0; 
   }
}

See BozoSort.java.