Взвешенный рандомизированный порядок

Кажется, это работает нормально:

// Can do a weighted sort on weighted items.
public interface Weighted {
    int getWeight();
}

/**
 * Weighted sort of an array - orders them at random but the weight of each
 * item makes it more likely to be earlier.
 *
 * @param values
 */
public static void weightedSort(Weighted[] values) {
    // Build a list containing as many of each item to make up the full weight.
    List<Weighted> full = new ArrayList<>();
    for (Weighted v : values) {
        // Add a v weight times.
        for (int i = 0; i < v.getWeight(); i++) {
            full.add(v);
        }
    }
    // Shuffle it.
    Collections.shuffle(full);
    // Roll them out in the order required.
    int i = 0;
    do {
        // Get the first one in the shuffled list.
        Weighted next = full.get(0);
        // Put it back into the array.
        values[i++] = next;
        // Remove all occurrences of that one from the list.
        full.remove(next);
    } while (!full.isEmpty());
}

// A bunch of weighted items.
enum Heavies implements Weighted {

    Rare(1),
    Few(3),
    Common(6);
    final int weight;

    Heavies(int weight) {
        this.weight = weight;
    }

    @Override
    public int getWeight() {
        return weight;
    }
}

public void test() {
    Weighted[] w = Heavies.values();
    for (int i = 0; i < 10; i++) {
        // Sort it weighted.
        weightedSort(w);
        // What did we get.
        System.out.println(Arrays.toString(w));
    }
}

По сути, для каждого элемента, который нужно отсортировать, я добавляю его столько раз, сколько необходимо, в новый список. Затем я перемешиваю список, вытаскиваю верхний и удаляю все его вхождения из оставшихся.

Последний тестовый запуск дал:

[Rare, Common, Few]
[Common, Rare, Few]
[Few, Common, Rare]
[Common, Few, Rare]
[Common, Rare, Few]
[Few, Rare, Common]

что кажется правильным.

NB — этот алгоритм не сработает, по крайней мере, при следующих условиях:

1. В исходном массиве один и тот же объект содержится более одного раза.
2. Вес предметов безумно велик.
3. Нулевые или отрицательные веса почти наверняка испортят результаты.

Добавлен

Это реализует идею Россума - пожалуйста, не забудьте отдать ему должное за алгоритм.

public static void weightedSort2(Weighted[] values) {
    // Calculate the total weight.
    int total = 0;
    for (Weighted v : values) {
        total += v.getWeight();
    }
    // Start with all of them.
    List<Weighted> remaining = new ArrayList(Arrays.asList(values));
    // Take each at random - weighted by it's weight.
    int which = 0;
    do {
        // Pick a random point.
        int random = (int) (Math.random() * total);
        // Pick one from the list.
        Weighted picked = null;
        int pos = 0;
        for (Weighted v : remaining) {
            // Pick this ne?
            if (pos + v.getWeight() > random) {
                picked = v;
                break;
            }
            // Move forward by that much.
            pos += v.getWeight();
        }
        // Removed picked from the remaining.
        remaining.remove(picked);
        // Reduce total.
        total -= picked.getWeight();
        // Record picked.
        values[which++] = picked;
    } while (!remaining.isEmpty());
}

У вас есть предметы с весами:

• Деталь А, вес 42
• Деталь Б, вес 5
• Изделие С, вес 96
• Деталь D, вес 33

Сначала сложите все веса: 42 + 5 + 96 + 33 = 176.

Теперь выберите случайное число r от 0 до суммы весов: 0 ‹= r ‹ 176. Я использовал целые числа, но при необходимости вы можете использовать вещественные числа.

Сравните r с диапазонами, определяемыми весами:

• 0 ‹= r ‹ 42: выберите пункт A.
• 42 ‹= r ‹ 47 (= 42 + 5): выберите пункт B.
• 47 ‹= r ‹ 143 (= 47 + 96): выберите пункт C.
• 143 ‹= r ‹ 176 (= 143 + 33): выберите пункт D.

Когда вы выбрали первый предмет, повторите процесс с тремя оставшимися предметами и уменьшенной суммой всех весов. Продолжайте повторять, пока не останется предметов для выбора.

public class RandomPriorityQueue {

    private TreeMap<Integer, List<WeightedElement>> tree = new TreeMap();
    private Random random = new Random();

    public void add(WeightedElement e) {
        int priority = random.nextInt(e.getWeight());
        if (tree.containsKey(priority)) {
            List<WeightedElement> list = new LinkedList();
            list.add(e);
            tree.put(priority, list);
        } else {
            List<WeightedElement> list = tree.get(priority);
            list.add(random.nextInt(list.size()), e);
        }
    }

    public WeightedElement poll() {
        Map.Entry<Integer, List<WeightedElement>> entry = tree.lastEntry();
        if (entry == null){
            return null;
        }
        List<WeightedElement> list = entry.getValue();
        if (list.size() == 1){
            tree.remove(entry.getKey());
        }
        return list.remove(0);
    }
}

Конечно, у нас была бы лучшая производительность, если бы мы переписали TreeMap, чтобы мы могли добавлять ключи дублирования, у нас была бы лучшая производительность.

В любом случае, для N элементов вам понадобится N-1 случайных чисел (как минимум). Затем давайте подумаем об эффективном способе выбора элемента по случайному номеру.

Если элементов не слишком много, я бы использовал итеративный метод, аналогичный вашему рекурсивному подходу. Я бы добавил логический флаг к элементам для пропуска выбранных в предыдущих итерациях. Когда я выбираю один из них в текущей итерации, я устанавливаю его флаг в значение true, и в следующий раз я пропускаю его из вычислений. Вычтите его вес из суммы и перейдите к следующей итерации.

Если предметов много и один и тот же набор будет использоваться много раз, то лучше использовать другой подход. Составьте из них отсортированный список и используйте копию этого списка в своем рекурсивном подходе. И на каждом шаге рекурсии - бинарный поиск в нем, потом удаление выбранного элемента.

Собственно, последнее тоже можно делать итеративно.