Smartly building pair elements in different lists

Question

I am building a mind game, it's hard to explain so I put an example.

I have a list of words (it can be infinite):

String myList[] = {"chair", "house", "ocean", "plane", "dog", "TV", "grass", "money" etc....}

Now the tricky part, I need to build 4 lists of pair index/word (every list has the same size) randomly but that fit these rule: if I chose a number, the word that match this number only appears in 2 lists.

for example this would be correct:

List1:
1/chair
2/house
3/plane
4/grass

List2
1/chair
2/dog
3/plane
4/TV

List3:
1/ocean
2/house
3/money
4/TV

List4
1/ocean
2/dog
3/money
4/grass

For example:

If I pick number 3, then list 3 and list 4 match the word 'money', list 1 and 2 match the word 'plane'. There always must be 2 matching lists (never less, never more). They should be build from a huge array of words randomly, so you can't guess which list will be matching when you pick a number.

I tried to do it with a nice simple recursive algorithm. But I badly failed.

Answer 1

Something like this should do the trick (you can change the provided words and the respective listSize accordingly). The number of words should be dividable by the listSize in order to fill up all lists.

public static void main(String[] args) {
    String[] words = new String[] { "chair", "house", "ocean", "plane",
            "dog", "TV", "grass", "money" };
    // valid list sizes for 8 words: 1, 2, 4, 8
    int listSize = 4;
    List<String[]> result = distributeRandomly(words, listSize);
    for (String[] resultList : result) {
        for (int index = 0; index < listSize; index++) {
            System.out.println((index + 1) + "/" + resultList[index]);
        }
        System.out.println();
    }
}

private static List<String[]> distributeRandomly(String[] words, int listSize) {
    // each word goes into 2 lists, so how many lists do we need?
    int listCount = words.length * 2 / listSize;
    if (listCount * listSize != words.length * 2) {
        throw new IllegalArgumentException("Number of words"
                + " must be a multiple of the size of the individual lists!");
    }
    // initialize result lists (here arrays) in fitting size
    List<String[]> listsToFill = new ArrayList<String[]>(listCount);
    for (int index = 0; index < listCount; index++) {
        listsToFill.add(new String[listSize]);
    }
    // be sure to randomly pick the given words by shuffling them
    List<String> shuffledWords = new ArrayList<String>(Arrays.asList(words));
    Collections.shuffle(shuffledWords);

    List<String[]> result = new ArrayList<String[]>(listCount);
    int maxWordPosition = listSize - 1;
    // distribute words
    for (String word : shuffledWords) {
        // word is supposed to be inserted in two lists at the same index
        int wordPosition = -1;
        // iterate result lists
        Iterator<String[]> listIterator = listsToFill.iterator();
        while (listIterator.hasNext()) {
            String[] list = listIterator.next();
            if (wordPosition == -1) {
                // look out for the first list with an empty slot
                for (int index = 0; index < listSize; index++) {
                    if (list[index] == null) {
                        // found empty slot at this index
                        wordPosition = index;
                        // insert word here (first list)
                        list[wordPosition] = word;
                        if (wordPosition == maxWordPosition) {
                            // the list is full, no more empty slots here
                            listIterator.remove();
                            result.add(list);
                        }
                        break;
                    }
                }
            } else if (list[wordPosition] == null) {
                // found second list with an empty slot at the same index
                list[wordPosition] = word;
                if (wordPosition == maxWordPosition) {
                    // the list is full, no more empty slots here
                    listIterator.remove();
                    result.add(list);
                }
                // we are done with this word
                break;
            }
        }
        // shuffle result lists again, to ensure randomness
        Collections.shuffle(listsToFill);
    }
    return result;
}

This produces (for example) the following output:

1/grass
2/TV
3/plane
4/ocean

1/grass
2/dog
3/money
4/chair

1/house
2/dog
3/money
4/ocean

1/house
2/TV
3/plane
4/chair

Answer 2

My initial approach to this problem would be to

1. Select a random word in the universe
2. Assign the selected word to two lists that
   • are different and
   • are not full
3. Store the random word in a set of closed words in case it is selected again
4. Rinse and repeat until all lists are full