# Clean algorithm for generating Scrabble tile sequences

I am trying to come up with an algorithm that generates every possible combination of Scrabble tile sequence on a player’s rack. I want the sequence to be comprised of n number of indices depending on the number of tiles on a player’s rack.

So for example, in Scrabble, a player MUST have at least 1 tile on his rack but no more than 7.

Therefore, there are 7 possible scenarios to consider:

``````Player has 1 tile on his rack (minimum)
Player has 2 tiles on his rack
Player has 3 tiles on his rack
Player has 4 tiles on his rack
Player has 5 tiles on his rack
Player has 6 tiles on his rack
Player has 7 tiles on his rack (maximum)
``````

In the case where the player only has 1 tile, this is easy since we only have a single index to worry about. The answer is:

``````1: [0] - This means the tile on index 0 on the rack can not be repositioned any further.
``````

In the case where the player only has 2 tiles, this too is easy since we only have 2 combinations. The answer is:

``````1: [0][1] – First tile on the rack remains in position 0
Second tile on the rack remains in position 1
2: [1][0] - First tile on the rack swaps to position 1
- Second tile on the rack swaps to position 0
``````

In the case where the player has exactly 3 tiles on his rack, there are even more combinations: The answer is:

``````1: [0][1][2]
2: [0][2][1]
3: [1][0][2]
4: [1][2][0]
5: [2][0][1]
6: [2][1][0]
``````

Of course, in the 3 examples above, the answers represent those situations where the player has managed to play ALL his tiles on a single play.

In Scrabble, however, a player can play any number of tiles on his rack or even none at all. Ignoring the situation where no tiles are played, we need sets to encompass any type of play.

Let’s revisit a rack with 1 tile. We have no more extra sets to create; the answer is still:

``````1: [0]
``````

For 2 tile racks, the answer is now:

``````1: [0][1] – All 2 tiles are played
2: [1][0] – All 2 tiles are played
3: [0] – Only 1st tile is played, other stays on rack
4: [1] – Only 2nd tile is played, other stays on rack
``````

For 3 tile racks, the answer is:

`````` 1: [0][1][2] - All 3 tiles played
2: [0][2][1] - All 3 tiles played
3: [1][0][2] - All 3 tiles played
4: [1][2][0] - All 3 tiles played
5: [2][0][1] - All 3 tiles played
6: [2][1][0] - All 3 tiles played
7: [0][1] - Only 2 of 3 tiles played
8: [0][2] - Only 2 of 3 tiles played
9: [1][0] - Only 2 of 3 tiles played
10: [1][2] - Only 2 of 3 tiles played
11: [2][0] - Only 2 of 3 tiles played
12: [2][1] - Only 2 of 3 tiles played
13: [0] – A single tile played
14: [1] – A single tile played
15: [2] – A single tile played
``````

The number of combinations grows dramatically when we start looking at racks with 4, 5, 6 and 7 tiles but can we use a clean reusable algorithm that will work in all cases?

I did come up with a solution but it is not very clean as I needed to create 7 separate classes, one for each possible tile count for a given rack.

For example, here is the java class for generating all combinations for a 7 tile rack but I am looking for something that can be expressed more elegantly.

``````import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class TileCombinationSet07 {

private static final int NUM_TILES = 7;
private static final List<TileCombination> TILE_01_COMBOS = new ArrayList<TileCombination>();
private static final List<TileCombination> TILE_02_COMBOS = new ArrayList<TileCombination>();
private static final List<TileCombination> TILE_03_COMBOS = new ArrayList<TileCombination>();
private static final List<TileCombination> TILE_04_COMBOS = new ArrayList<TileCombination>();
private static final List<TileCombination> TILE_05_COMBOS = new ArrayList<TileCombination>();
private static final List<TileCombination> TILE_06_COMBOS = new ArrayList<TileCombination>();
private static final List<TileCombination> TILE_07_COMBOS = new ArrayList<TileCombination>();

static  {

for(int one = 0; one < NUM_TILES; one++) {
for(int two = 0; two < NUM_TILES; two++) {
for(int three = 0; three < NUM_TILES; three++) {
for(int four = 0; four < NUM_TILES; four++) {
for(int five = 0; five < NUM_TILES; five++) {
for(int six = 0; six < NUM_TILES; six++) {
for(int seven = 0; seven < NUM_TILES; seven++) {
unique.clear();

String result = "";
for(Integer value : unique) {
result += value;
}

else {
throw new IllegalStateException("FATAL: Set size is wrong");
}
}
}
}
}
}
}
}

initTileCombinationList(UNIQUE_TILE_SET_01, TILE_01_COMBOS);
initTileCombinationList(UNIQUE_TILE_SET_02, TILE_02_COMBOS);
initTileCombinationList(UNIQUE_TILE_SET_03, TILE_03_COMBOS);
initTileCombinationList(UNIQUE_TILE_SET_04, TILE_04_COMBOS);
initTileCombinationList(UNIQUE_TILE_SET_05, TILE_05_COMBOS);
initTileCombinationList(UNIQUE_TILE_SET_06, TILE_06_COMBOS);
initTileCombinationList(UNIQUE_TILE_SET_07, TILE_07_COMBOS);
}

public static final List<TileCombination> tileCombinations(int tilesToPlay) {
if(tilesToPlay == 1) {return TILE_01_COMBOS;}
if(tilesToPlay == 2) {return TILE_02_COMBOS;}
if(tilesToPlay == 3) {return TILE_03_COMBOS;}
if(tilesToPlay == 4) {return TILE_04_COMBOS;}
if(tilesToPlay == 5) {return TILE_05_COMBOS;}
if(tilesToPlay == 6) {return TILE_06_COMBOS;}
if(tilesToPlay == 7) {return TILE_07_COMBOS;}
throw new IllegalArgumentException("FATAL: tilesToPlay is wrong");
}

private static final void initTileCombinationList(
Set<String> unique,
List<TileCombination> list) {

for(String tokens : unique) {
}
}
}
``````

A simple pseudocode or suggestion on a more elegant algorithm would be appreciated. Thanks!

• are you sure you dont want to generate all the words the player can make? – Ewan Apr 8 at 8:59
• @Ewan: that's the next step after generating tile sequences, and it would involve using the tiles which are already at the board, as well as a dictionary of valid words. – Doc Brown Apr 8 at 20:40
• If you have the dictionary of allowed words, reorder the letters alphabetically and add an index. then you can look up matching words very quickly without working out the permutations and combinations of tiles – Ewan 2 days ago