1

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.LinkedHashSet;
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  {
        Set<Integer> unique = new LinkedHashSet<Integer>();
        Set<String> UNIQUE_TILE_SET_01 = new LinkedHashSet<String>();
        Set<String> UNIQUE_TILE_SET_02 = new LinkedHashSet<String>();
        Set<String> UNIQUE_TILE_SET_03 = new LinkedHashSet<String>();
        Set<String> UNIQUE_TILE_SET_04 = new LinkedHashSet<String>();
        Set<String> UNIQUE_TILE_SET_05 = new LinkedHashSet<String>();
        Set<String> UNIQUE_TILE_SET_06 = new LinkedHashSet<String>();
        Set<String> UNIQUE_TILE_SET_07 = new LinkedHashSet<String>();
            
        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();
                                    unique.add(one);
                                    unique.add(two);
                                    unique.add(three);
                                    unique.add(four);
                                    unique.add(five);
                                    unique.add(six);
                                    unique.add(seven);

                                    String result = "";
                                    for(Integer value : unique) {
                                        result += value;
                                    }
                                
                                    if(unique.size() == 1) {UNIQUE_TILE_SET_01.add(result);}
                                    else if(unique.size() == 2) {UNIQUE_TILE_SET_02.add(result);}
                                    else if(unique.size() == 3) {UNIQUE_TILE_SET_03.add(result);}
                                    else if(unique.size() == 4) {UNIQUE_TILE_SET_04.add(result);}
                                    else if(unique.size() == 5) {UNIQUE_TILE_SET_05.add(result);}
                                    else if(unique.size() == 6) {UNIQUE_TILE_SET_06.add(result);}
                                    else if(unique.size() == 7) {UNIQUE_TILE_SET_07.add(result);}
                                    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) {
            list.add(new TileCombination(tokens));
        }
    }
}

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

3
  • 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
4

Start with generating all combinations of k elements out of n, where you let k loop from one to n. For each combination, you then generate all the permutations of those k elements. If you are looking for code in Java, google for "algorithm Java combinations", or "algorithm Java permutations", I am sure you will find plenty of links.

There is also some room here for optimization when there are several tiles showing the same letter on the rack.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.