Yeah I think if you number the permutations in order from smallest to largest (ie all 0 to all 99999999) then you can update as new numbers come in by keeping t

Yeah I think if you number the permutations in order from smallest to largest (ie all 0 to all 99999999) then you can update as new numbers come in by keeping track of the number (N) you've already seen and assume the other (million - N) are 0. So you just have your 10^6 bit number representing the sorted list of numbers and an 27bit integer representing the number of samples seen. The update function might be a bit ugly though :) It's probably actually a question of whether the update function could be done in the remaining memory - it certainly couldn't unpack the whole representation.