Как раскидать элементы максимально рандомно согласно условию?

Question

[Pragma Games]

Всем привет. Есть x стопок, каждая может вместить в себе разное количество блоков y (для каждой стопки y свой). Дается z блоков ( z меньше либо равно суммы блоков в стопке (y1 + y2 + y3 ... yn)). Нужно рандомно разместить данные блоки (z) по стопкам так что бы не осталось лишних блоков. Не обязательно это делать за один проход, но чем меньше тем лучше. Так же допускается что в одной из стопок после размещения не окажется блоков.

Answer 1

[Alexandroppolus]

на JS, переделать в C# нетрудно

function randomSets(boxSizes, z) {
    const arr = [];
    const result = [];
    for (let i = 0; i < boxSizes.length; ++i) {
        result.push([]);
        const y = boxSizes[i];
        for (let j = 0; j < y; ++j) {
            arr.push(i);
        }
    }
    let len = arr.length;
    for (let i = 0; i < z && len > 0; ++i) {
        const pos = Math.floor(Math.random() * len);
        result[arr[pos]].push(i);
        arr[pos] = arr[--len];
    }

    return result;
}

const fill = randomSets([1, 2, 2], 5); // в качестве блоков - номера от 0 до z-1

пример результата:

[
  [1], // содержимое 0 стопки
  [0, 4], // содержимое 1 стопки
  [2, 3] // содержимое 2 стопки
]

Comments

[Alexandroppolus]

вообще говоря, у этого варианта есть проблемка. Например, в случае randomSets([1, 2, 20], 2) , то есть когда есть маленькие и большие стопки и мало блоков, почти всегда блоки будут уходить в большие стопки.

вариант ниже выравнивает "шансы на получание блоков" между стопками. Случайная перестановка массива блоков нужна, без неё при большом z маленькие стопки заполняются очень быстро и почти не имеют шансов на блоки, стоящие в конце массива.

function randomSets(boxSizes, z) {
    const blocks = [];
    for (let i = 0; i < z; ++i) {
        blocks.push(i);
    }

    // random shaffle
    for (let i = blocks.length - 1; i > 0; --i) {
        const pos = Math.floor(Math.random() * (i + 1));
        const t = blocks[pos];
        blocks[pos] = blocks[i];
        blocks[i] = t;
    }
    
    const arr = [];
    const counts = [];
    const result = [];
    let count = 0
    for (let i = 0; i < boxSizes.length; ++i) {
        result.push([]);
        const y = boxSizes[i];
        arr.push(i);
        counts.push(y);
        count += y;
    }
    let len = arr.length;
    for (let i = 0; i < z && count > 0; ++i, --count) {
        const pos = Math.floor(Math.random() * len);
        result[arr[pos]].push(blocks[i]);
        if (--counts[pos] < 1) {
            --len;
            arr[pos] = arr[len];
            counts[pos] = counts[len];
        }
    }

    return result;
}

Answer 2

[Wataru]

Надо чтобы все возможные варинаты были равновероятны или возможны перекосы?

Если возможны перекосы, то есть простой алгоритм.
Сначала за один проход подсчитайте частичные суммы s1=y1, s2=y1+y2, s3=y1+y2+y3...

Потом идем с конца. В последнюю стопку можно положить от max(0, z-s(n-1)) до yn блоков. Все оставшиеся блоки гарантированно влезают в предыдущие стопки. Уменьшайте z на сгенерированное случайное число блоков и повторяйте дальше.

Если надо все равновернятно, то все сложно. Надо динамическим программированем уметь считать, сколько вариантов разместить k блоков на первых i стопках. Потом сгенерировать случайный номер среди всевозможного количества размещений и считать, а сколько бывает вариантов при последней стопке с 0, 1, ... yn блоках и так можно понять, сколько блоков надо поставить в последнюю стопку, чтобы накрыть нужный вариант в лексикографическом порядке. Для этого используйте подсчитанные динмическим программированием значения.