问题：
我有重量的物品。重量越高，他们拥有该物品的机会就越大。我需要一种基于核心Java（没有第三方库，jar等）的干净，简单的方法来进行此操作。
我已经完成了2项操作，通过对权重求和，然后使用Math.random()在该范围内随机选择一个数字。很简单。但是对于大于2的项目，我可以在相同范围内进行更多采样，从而降低未命中率，或者可以重新计算其余项目的权重之和，然后再次选择（递归方法）。我认为可能有些东西可以做到这一点更快/更清洁。该代码将反复使用，因此我正在寻找有效的解决方案。
本质上，它就像随机的权重排列。
某些示例：
A的权重为1，B的权重为99。如果我以此运行模拟，我希望获得BA的时间为99％，AB的时间为1％ 。
A的权重为10，B的权重为10，C的权重为80。如果我以此进行模拟，我希望C是第一项在80％的时间顺序中，在这些情况下，A和B将有相同的机会成为下一个字符。
额外详细信息：
对于我的特定问题，少数物品的重量可能很大。说20到50件物品，这些物品的重量以长条形式存储，其中最小重量至少为1000。物品的数量也可能会增加很多，因此，如果我们可以找到不需要的解决方案较小的物品，这将是首选。
这似乎很好用：
// 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]
这似乎是正确的。
注意-该算法至少在以下情况下会失败：
这实现了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'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 + 33 = 176
现在选择一个随机数r，从0到权重之和：0 <= r <176。我已经使用了整数，但是如果需要，可以使用实数。
将r与权重定义的范围进行比较：
选择了第一个项目后，对剩余的三个项目和所有权重的总和减少进行重复该过程。不断重复，直到没有更多选择。
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个随机数（至少）。然后，考虑通过随机数选择项目的有效方法。
如果项目不太多，我将使用迭代方法，类似于您的递归方法。我将为项目添加boolean标志，以跳过之前的迭代中选择的项目。在当前迭代中选择一个时，将其标志设置为true，下次将其从计算中跳过。从总和中减去其权重，然后进行下一次迭代。
如果项目数量很大，并且一次使用同一套项目，则采用不同的方法更好。创建它们的排序列表，并在递归方法中使用此列表的副本。在每个递归步骤中-在其中进行二进制搜索，然后删除所选项目。
实际上，最后一个也可以迭代完成。