Weighted Randomized Ordering

Question

Problem:

I have items with weights. The higher the weight, the higher the likelihood that they will have an item. I need to have a simple and easy way to do this, based on the Java kernel (no third-party libraries, cans, etc.).

I did this for 2 elements, summing the scales, then randomly select a number using Math.random () in this range. Very simple. But for elements that are more than 2, I can either make more selections in the same skipped missing ranges, or I can recalculate the sum of the weights of the remaining items and select again (recursive approach). I think there may be something that can make it faster / cleaner. This code will be used again and again, so I'm looking for an effective solution.

In essence, this is like a randomized weight swap.

Some examples:

• Ahas a weight of 1, Bhas a weight of 99. If I ran a simulation with this, I would expect to get BA99% of the time and AB1% of the time.

• Ahas a weight of 10, Bhas a weight of 10, and Chas a weight of 80. If I were to run simulations with this, I would expect that there Cwill be the first item in the order 80% of the time, in these cases Athey Bwill have an equal chance of being the next character.

Any help or pointers in the right direction would be appreciated.

Additional information:

. 20 50 , , 1000. , , , , .

Answer 1

:

// 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 - , , :

• .
• .
• .

Rossum - , .

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

Answer 2

:

• , 42
• B, 5
• C, 96
• D, 33

: 42 + 5 + 96 + 33 = 176

, r, 0 : 0 <= r < 176. , reals.

r , :

• 0 <= r < 42: A.
• 42 <= r < 47 (= 42 + 5): B.
• 47 <= r < 143 (= 47 + 96): C.
• 143 <= r < 176 (= 143 + 33): D.

, . , .

Answer 3

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, , .

Answer 4

, N N-1 ( ). .

, , . , . , true, . .

, , . . - , .

, .