data structures - picking without replacement in java -

i often* find myself in need of data structure has following properties:

• can initialized array of n objects in o(n).
• one can obtain random element in o(1), after operation picked element removed structure. (without replacement)
• one can undo p 'picking without replacement' operations in o(p)
• one can remove specific object (eg id) structure in o(log(n))
• one can obtain array of objects in structure in o(n).

the complexity (or possibility) of other actions (eg insert) not matter. besides complexity should efficient small numbers of n.

can give me guidelines on implementing such structure? implemented structure having above properties, except picking of element takes o(d) d number of past picks (since explicitly check whether 'not yet picked'). can figure out structures allowing picking in o(1), these have higher complexities on @ least 1 of other operations.

btw: note o(1) above implies complexity independent #earlier picked elements , independent total #elements.

*in monte carlo algorithms (iterative picks of p random elements 'set' of n elements).

ok, same answer 0verbose simple fix o(1) random lookup. create array stores same n objects. now, in hashmap, store pairs . example, objects (strings simplicity) are:

{"abc" , "def", "ghi"} 

create

list<string> array = arraylist<string>("abc","def","ghi") 

create hashmap map following values:

for (int = 0; < array.size(); i++)  {     map.put(array[i],i); } 

o(1) random lookup achieved picking index in array. complication arises when delete object. that, do:

1. find object in map. array index. lets call index i (map.get(i)) - o(1)

2. swap array[i] array[size of array - 1] (the last element in array). reduce size of array 1 (since there 1 less number now) - o(1)

3. update index of new object in position i of array in map (map.put(array[i], i)) - o(1)

i apologize mix of java , cpp notation, hope helps