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;
}
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!
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;
}
}
