Sampling without replacement from an unknow set

I have to extract uniformly DFAs (deterministic finite automata) from a set of DFA that I call S. It seems a simple problem, but I haven't the set S. S contains all the DFA of dimension n , thus I know dimension of S, I can build S but I can't bacause is very large. I know also the dimension of sets Sm where for example S3 is a subset of S and S3 contains all the DFA with 3 states, Sm contain all the DFA with m states where m < n .

I have not the set S and thus I have to simulate a uniformly sampling. Furthemore I have to do sampling without replacement. I create a set D={1,2,3........n} and for each value,that I call i, in D I associate the value |Si|/|S| where | | indicates the number of elements in the set that is the argument. Namely I created a distribution. Now I can extract a value from D according to this distribution. In this way I found the set from which extract a single DFA. For example if from D I extract 4 then I have to extract uniformly a DFA from S4.

But my question is, how can I sampling a DFA from Si (S4 in the example above) without replacement? Namely if I have already extracted previously a specific DFA, in the next sampling I must avoid that specific DFA. Remark that a DFA is a matrix, a table (a bidimensional array). Remark also that extract a specif DFA means uniformly extract for each cell of the above mentioned table a value in {1,.....,k} where k is the number of the elements of the alphabet (you have to extract also for each state if is accepting or rejecting).

(I have to implement in C++11 but this is pretty irrilevant)