Random distribution of items in list with exact nu

Question

Following this question : Random distribution of items in list up to a maximum count

I have a List of items containing x items.

I want to distribute these items randomly in other Lists with the conditions :

• Each List has a maximum size of y item (with y = 4)
• Each Item must be used exactly z times (with z = 5)
• Each Item must only appear once in a particular List

If x isn't divisible by both y and z, it's okay to have Lists containing less than y items.

I'm looking for a Java (from 1.6 to 1.8) implementation of such a method.

---

So far, thanks to Jamie Cockburn, I have a method that can distribute items randomly in other Lists by using them 0 to z times. I need to use them exactly z times. His method also allow items be used more than once in a single List.

EDIT

Now I manage to use items exactly z times in my Lists. But I'm stuck with what to do if the List already contains the same Item :

Here's my function :

public static List<List<Item>> distribute(List<Item> list, int y, int z) {
    int x = list.size();
    int nLists = (int) Math.ceil((double)(x*z)/y);

    // Create result lists
    List<List<Item>> result = new ArrayList<>();
    for (int j = 0; j < nLists; j++)
        result.add(new ArrayList<Item>());
    List<List<Item>> outputLists = new ArrayList<>(result);

    // Create item count store
    Map<Item, Integer> itemCounts = new HashMap<>();
    for (Item item : list)
        itemCounts.put(item, 0);

    // Populate results
    Random random = new Random();
    for (int i = 0; i < (x*z); i++) {
        // Add a random item (from the remaining eligible items)
        // to a random list (from the remaining eligible lists)
        Item item = list.get(random.nextInt(list.size()));
        List<Item> outputList = outputLists.get(random.nextInt(outputLists.size()));
        if (outputList.contains(item)) {
            // What do I do here ?
        } else {
            outputList.add(item);

            // Manage eligible output lists
            if (outputList.size() >= y)
                outputLists.remove(outputList);

            // Manage eligible items
            int itemCount = itemCounts.get(item).intValue() + 1;
            if (itemCount >= z)
                list.remove(item);
            else
                itemCounts.put(item, itemCount);
        }
    }

    return result;
}

Answer 1

I deleted my other answer because it was simply wrong! Then it occurred to me that there is a much simpler method:

public static List<List<Item>> distribute(List<Item> items, int y, int z) {
    // Create list of items * z
    List<Item> allItems = new ArrayList<>();
    for (int i = 0; i < z; i++)
        allItems.addAll(items);
    Collections.shuffle(allItems);

    // Randomly shuffle list
    List<List<Item>> result = new ArrayList<>();
    int totalItems = items.size()*z;
    for (int i = 0; i < totalItems; i += y)
        result.add(new ArrayList<Item>(allItems.subList(i, Math.min(totalItems, i+y))));

    // Swap items in lists until lists are unique
    for (List<Item> resultList : result) {
        // Find duplicates
        List<Item> duplicates = new ArrayList<>(resultList);
        for (Item item : new HashSet<Item>(resultList))
            duplicates.remove(item);

        for (Item duplicate : duplicates) {
             // Swap duplicate for item in another list
            for (List<Item> swapCandidate : result) {
                if (swapCandidate.contains(duplicate))
                    continue;
                List<Item> candidateReplacements = new ArrayList<>(swapCandidate);
                candidateReplacements.removeAll(resultList);
                if (candidateReplacements.size() > 0) {
                    Item replacement = candidateReplacements.get(0);
                    resultList.add(resultList.indexOf(duplicate), replacement);
                    resultList.remove(duplicate);
                    swapCandidate.add(swapCandidate.indexOf(replacement), duplicate);
                    swapCandidate.remove(replacement);
                    break;
                }
            }
        }
    }

    return result;
}

Basically:

• Create a big list containing items repeated z times
• Shuffle that list randomly
• Slice it up into chunks of size y
• Make each list unique

This has the following benefits over the accepted solution:

• Doesn't modify original list
• Faster (16.5 seconds vs 18.8 seconds for 1,000,000 executions)
• Simpler!

Answer 2

EDIT:

The general idea is, to create a copy of the input list, and create tempLists out of it, while removing the picked items from the copylist. If the copyList is emptied, it is refilled. This forces all items to be picked once before another is picked twice. If list.size() is devidable by y, the result is qually distributed, if its not, im not sure about.

I changed the Item to Integer to be tested and to find the mistake. Now it operates correctly (I hope, correct for your needs)

reineke

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.*;

public class javatest{
public static void main(String args[]){
    List<Integer> test=new ArrayList<Integer>();
    test.add(1);
    test.add(2);
    test.add(3);
    test.add(4);
    test.add(5);
    test.add(6);
    test.add(7);
    System.out.println("Found1");
    List<List<Integer>> temp=distribute(test,3,4);
    for (List<Integer> i:temp){
        System.out.println(i);
    }
}
public static List<List<Integer>> distribute(List<Integer> list, int y, int z) {
    int x = list.size();
    int nLists = (int) Math.ceil((double)(x*z)/y);

    // Create result lists
    List<List<Integer>> result = new ArrayList<>();


    // Create item count store
    Map<Integer, Integer> itemCounts = new HashMap<>();
    for (Integer item : list){
        itemCounts.put(item, 0);
    }
    System.out.println("Found2");
    // Populate results
    Random random = new Random();
    ArrayList<Integer> copyList=new ArrayList<Integer>(); //create a copy of the List of Items. 
    for (int i = 0; i < nLists; i++) {
        System.out.println("Found:"+i);
        System.out.println("listSize: "+list.size());

        //the copyList is reduced for each Item i pick out of it, so i can assure, that no item is used twice in a result, and several item arent picked 5 times and other 0 times, to prevent a error in the end.
        ArrayList<Integer> tempList=new ArrayList<Integer>();
        //if there are less items in the copyList, than fitting in the resultlist, refill it
        if (copyList.size()<y && list.size()>1){
            for (Integer item : list){
                if (!copyList.contains(item)) copyList.add(item);
                else {
                    tempList.add(item);
                    int itemCount = itemCounts.get(item).intValue()+1;
                    if (itemCount >= z) {
                        list.remove(item);
                        copyList.remove(item);
                    }
                    else
                        itemCounts.put(item, itemCount);
                }
            }
        }
        // as long als the tempList isnt filled and there are items in the list to assign, add Items to the tempList
        while (tempList.size()<y && list.size()>0) {
            random=new Random();
            Integer item = copyList.get(random.nextInt(copyList.size()));
            if (!tempList.contains(item)){
                tempList.add(item);
                copyList.remove(item);
                int itemCount = itemCounts.get(item).intValue()+1;
                if (itemCount >= z)
                    list.remove(item);
                else
                    itemCounts.put(item, itemCount);
            }
        }
        result.add(tempList);
    }
    return result;
}
}