列表中项目的随机分布，具有确切的出现次数
Random distribution of items in list with exact number of occurences
关注这个问题：
我有一个包含 x 个项目的项目列表。
我想在其他列表中随机分发这些项目，条件是：
- 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
如果 x 不能同时被 y 和 z 整除，则可以包含少于 y 个项目的列表。
我正在寻找这种方法的 Java（从 1.6 到 1.8）实现。
到目前为止，多亏了Jamie Cockburn，我有了一种方法，可以通过使用它们0 to z次，在其他列表中随机分配项目。我需要准确地使用它们 z 次。他的方法还允许在单个列表中多次使用项目。
编辑
现在我设法在我的列表中恰好使用项目 z 次。但是如果列表已经包含相同的项目，我不知道该怎么办：
这是我的函数：
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;
}
编辑：
总体思路是，创建输入列表的副本，并从中创建临时列表，同时从复制列表中删除选取的项目。如果 copyList 为空，则重新填充。这会强制所有项目在另一个被拾取两次之前被拾取一次。如果 list.size() 可除以 y，则结果是均匀分布的，如果不是，我不确定。
我把Item改成Integer来测试找错了。现在它可以正常运行（我希望能满足您的需求）
雷内克
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;
}
}
我删除了我的另一个答案，因为它完全是错误的！然后我想到了一个更简单的方法：
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;
}
基本上：
- 创建一个包含
items 重复 z 次 的大列表
- 随机打乱列表
- 将其切成
y 大小的块
- 使每个列表都独一无二
与公认的解决方案相比，这具有以下优势：
- 不修改原始列表
- 更快（16.5 秒对 1,000,000 次执行的 18.8 秒）
- 更简单！
关注这个问题：
我有一个包含 x 个项目的项目列表。
我想在其他列表中随机分发这些项目，条件是：
- 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
如果 x 不能同时被 y 和 z 整除，则可以包含少于 y 个项目的列表。
我正在寻找这种方法的 Java（从 1.6 到 1.8）实现。
到目前为止，多亏了Jamie Cockburn，我有了一种方法，可以通过使用它们0 to z次，在其他列表中随机分配项目。我需要准确地使用它们 z 次。他的方法还允许在单个列表中多次使用项目。
编辑
现在我设法在我的列表中恰好使用项目 z 次。但是如果列表已经包含相同的项目，我不知道该怎么办：
这是我的函数：
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;
}
编辑：
总体思路是，创建输入列表的副本，并从中创建临时列表，同时从复制列表中删除选取的项目。如果 copyList 为空，则重新填充。这会强制所有项目在另一个被拾取两次之前被拾取一次。如果 list.size() 可除以 y，则结果是均匀分布的，如果不是，我不确定。
我把Item改成Integer来测试找错了。现在它可以正常运行（我希望能满足您的需求）
雷内克
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;
}
}
我删除了我的另一个答案，因为它完全是错误的！然后我想到了一个更简单的方法：
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;
}
基本上：
- 创建一个包含
items重复z次 的大列表
- 随机打乱列表
- 将其切成
y 大小的块
- 使每个列表都独一无二
与公认的解决方案相比，这具有以下优势：
- 不修改原始列表
- 更快（16.5 秒对 1,000,000 次执行的 18.8 秒）
- 更简单！