Get random values without replacement given a probability distribution

Given a probability distribution – a mapping of objects to their probability – I want an algorithm that selects random objects from the map and is without replacement (the probability distribution is updated per selection). However, the algorithm must have an O(1) space complexity and have high quality randomness. I tried searching for implementations, but none of them seemed to have both of these properties.