java - 列表中项目的随机分布，具有确切的出现次数

Question

以下问题:Random distribution of items in list up to a maximum count

我有一个包含 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 到 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;
}

Answer 1

我删除了我的其他答案，因为它根本就是错误的!然后我想到还有一个更简单的方法:

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

基本上:

• 创建一个包含重复 z 次项目的大列表
• 随机排列该列表
• 将其切成y大小的 block
• 使每个列表都独一无二

与公认的解决方案相比，这具有以下优点:

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