Some List
examples. All of these examples require:
import java.util.List; import java.util.ArrayList;
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:
Sum | Frequency |
---|---|
0 | 0 |
1 | 0 |
2 | |
3 | |
... | |
11 | |
12 |
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.
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:
# Heads | Frequency |
---|---|
0 | |
1 | |
2 | |
... | |
... | |
N |
heads
of length N + 1.
heads
with all zeros
n
1
to element at index n
in heads
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.
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).
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 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
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 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
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.