Clean algorithm for generating Scrabble tile sequences

Question

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!

Answer 1

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.

Answer 2

Here was the solution based on Doc Brown's suggestion (I just printed out all combinations of 1 or 2 tiles to be played from a rack containing 1 to 7 tiles to see if this works and it seems to be working fine).

import java.util.Arrays;

public class TileComboDemo {

    public static void main(String[] args) {
        for(int numTiles = 1; numTiles <= 7; numTiles++) {          
            int[] arr = new int[numTiles];
            for(int index = 0; index < numTiles; index++) {
                arr[index] = index;
            }
            System.out.println("==================");
            System.out.println(Arrays.toString(arr));
            for(int play = 1;  play <= arr.length; play++) {
                System.out.println( "Tiles to play: " + (play));

                if(play <= 2) {
                    combinations2(arr, play, 0, new int[play]);
                }
            }
            System.out.println("==================");
        }
    }

    public static final void combinations2(int[] arr, int len, int startPosition, int[] result){
        if (len == 0) {
            heapPermutation(Arrays.copyOf(result, result.length), result.length, result.length);
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len - 1, i + 1, result);
        }
    }       

    private static final void printArr(int a[]) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    private static void heapPermutation(int a[], int size, int n) {
        if (size == 1) {
            printArr(a);
        }

        for (int i = 0; i < size; i++) {
            heapPermutation(a, size - 1, n);

            if (size % 2 == 1) {
                int temp = a[0];
                a[0] = a[size - 1];
                a[size - 1] = temp;
            }

            else {
                int temp = a[i];
                a[i] = a[size - 1];
                a[size - 1] = temp;
            }
        }
    }   
}

Output:

==================
[0]
Tiles to play: 1
0 
==================
==================
[0, 1]
Tiles to play: 1
0 
1 
Tiles to play: 2
0 1 
1 0 
==================
==================
[0, 1, 2]
Tiles to play: 1
0 
1 
2 
Tiles to play: 2
0 1 
1 0 
0 2 
2 0 
1 2 
2 1 
Tiles to play: 3
==================
==================
[0, 1, 2, 3]
Tiles to play: 1
0 
1 
2 
3 
Tiles to play: 2
0 1 
1 0 
0 2 
2 0 
0 3 
3 0 
1 2 
2 1 
1 3 
3 1 
2 3 
3 2 
Tiles to play: 3
Tiles to play: 4
==================
==================
[0, 1, 2, 3, 4]
Tiles to play: 1
0 
1 
2 
3 
4 
Tiles to play: 2
0 1 
1 0 
0 2 
2 0 
0 3 
3 0 
0 4 
4 0 
1 2 
2 1 
1 3 
3 1 
1 4 
4 1 
2 3 
3 2 
2 4 
4 2 
3 4 
4 3 
Tiles to play: 3
Tiles to play: 4
Tiles to play: 5
==================
==================
[0, 1, 2, 3, 4, 5]
Tiles to play: 1
0 
1 
2 
3 
4 
5 
Tiles to play: 2
0 1 
1 0 
0 2 
2 0 
0 3 
3 0 
0 4 
4 0 
0 5 
5 0 
1 2 
2 1 
1 3 
3 1 
1 4 
4 1 
1 5 
5 1 
2 3 
3 2 
2 4 
4 2 
2 5 
5 2 
3 4 
4 3 
3 5 
5 3 
4 5 
5 4 
Tiles to play: 3
Tiles to play: 4
Tiles to play: 5
Tiles to play: 6
==================
==================
[0, 1, 2, 3, 4, 5, 6]
Tiles to play: 1
0 
1 
2 
3 
4 
5 
6 
Tiles to play: 2
0 1 
1 0 
0 2 
2 0 
0 3 
3 0 
0 4 
4 0 
0 5 
5 0 
0 6 
6 0 
1 2 
2 1 
1 3 
3 1 
1 4 
4 1 
1 5 
5 1 
1 6 
6 1 
2 3 
3 2 
2 4 
4 2 
2 5 
5 2 
2 6 
6 2 
3 4 
4 3 
3 5 
5 3 
3 6 
6 3 
4 5 
5 4 
4 6 
6 4 
5 6 
6 5 
Tiles to play: 3
Tiles to play: 4
Tiles to play: 5
Tiles to play: 6
Tiles to play: 7
==================