列表中项目的随机分布以及确切的出现次数 [英] Random distribution of items in list with exact number of occurences

问题描述

以下问题:随机分配列表中的项目数量最多不超过

我有一个包含x个项目的项目列表.

I have a List of items containing x items.

我想根据条件将这些物品随机分配到其他列表中:

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

• 每个列表的最大大小为y个(y = 4)
• 每个物品必须使用准确的z次(z = 5)
• 每个项目在特定列表中只能出现一次

• 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个项目也是可以的.

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

我正在寻找这种方法的Java(从1.6到1.8)实现.

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

到目前为止，多亏了 Jamie Cockburn ，我有一种方法可以按以下方式在其他列表中随机分配项目使用它们0 to z次.我需要准确地使用它们z次.他的方法还允许在单个列表中多次使用项目.

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.

编辑

现在，我设法在列表中准确使用项目z次.但是，如果列表已经包含相同的Item，我该怎么办:

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 :

这是我的职能:

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

基本上:

• 创建一个包含items次重复z次的大列表
• 随机播放列表
• 将其切成大小为y
的块
• 使每个列表唯一

• 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:

• 不修改原始列表
• 更快(16.5秒，而执行1,000,000次则为18.8秒)
• 更简单！

这篇关于列表中项目的随机分布以及确切的出现次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！