java - Weighted Randomized Ordering -

the problem:

i have items have weights. higher weight, greater chance have item go first. need have clean, simple way of doing based on core java (no 3rd party libs, jars, etc.).

i've done 2 items, summing weights randomly pick number using math.random() within range. simple. items greater 2, can either more samples in same range chancing misses, or can recompute sum of weights of remaining items , select again (recursive approach). think there might out there can can faster/cleaner. code used on , over, i'm looking effective solution.

in essence, randomized weight permutations.

some examples:

1. a has weight of 1, b has weight of 99. if ran simulation this, expect ba 99% of time , ab 1% of time.

2. a has weight of 10, b has weight of 10, , c has weight of 80. if ran simulations this, expect c first item in ordering 80% of time, in cases, a , b have equal chance of being next character.

any or pointers in right direction appreciated.

extra details:

for particular problem, there small number of items potentially large weights. 20 50 items weights stored in form of long, minimum weight @ least 1000. number of items may increase quite bit too, if can find solution doesn't require items small, preferred.

this seems work fine:

// can weighted sort on weighted items. public interface weighted {     int getweight(); }  /**  * weighted sort of array - orders them @ random weight of each  * item makes more earlier.  *  * @param values  */ public static void weightedsort(weighted[] values) {     // build list containing many of each item make full weight.     list<weighted> full = new arraylist<>();     (weighted v : values) {         // add v weight times.         (int = 0; < v.getweight(); i++) {             full.add(v);         }     }     // shuffle it.     collections.shuffle(full);     // roll them out in order required.     int = 0;     {         // first 1 in shuffled list.         weighted next = full.get(0);         // put array.         values[i++] = next;         // remove occurrences of 1 list.         full.remove(next);     } while (!full.isempty()); }  // 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();     (int = 0; < 10; i++) {         // sort weighted.         weightedsort(w);         // did get.         system.out.println(arrays.tostring(w));     } } 

essentially each item sorted add many times needed new list. shuffle list , pull top 1 out , clar occurrences of remaining.

the last test run produced:

[rare, common, few] [common, rare, few] [few, common, rare] [common, few, rare] [common, rare, few] [few, rare, common] 

which seems right.

nb - algorithm fail under @ least following conditions:

1. the original array has same object in more once.
2. the weights of items insanely huge.
3. zero or negative weights mess results.

added

this implements rossum's idea - please sure give him credit algorithm.

public static void weightedsort2(weighted[] values) {     // calculate total weight.     int total = 0;     (weighted v : values) {         total += v.getweight();     }     // start of them.     list<weighted> remaining = new arraylist(arrays.aslist(values));     // take each @ random - weighted it's weight.     int = 0;     {         // pick random point.         int random = (int) (math.random() * total);         // pick 1 list.         weighted picked = null;         int pos = 0;         (weighted v : remaining) {             // pick ne?             if (pos + v.getweight() > random) {                 picked = v;                 break;             }             // move forward much.             pos += v.getweight();         }         // removed picked remaining.         remaining.remove(picked);         // reduce total.         total -= picked.getweight();         // record picked.         values[which++] = picked;     } while (!remaining.isempty()); }