title: Algorithm for sampling without replacement?
body: <p>I am trying to test the likelihood that a particular clustering of data has occurred by chance.  A robust way to do this is Monte Carlo simulation, in which the associations between data and groups are randomly reassigned a large number of times (e.g. 10,000), and a metric of clustering is used to compare the actual data with the simulations to determine a p value.</p>
  
  <p>I've got most of this working, with pointers mapping the grouping to the data elements, so I plan to randomly reassign pointers to data.  THE QUESTION: what is a fast way to sample without replacement, so that every pointer is randomly reassigned in the replicate data sets?</p>
  
  <p>For example (these data are just a simplified example):</p>
  
  <blockquote>
    <p>Data (n=12 values) - Group A: 0.1, 0.2, 0.4 / Group B: 0.5, 0.6, 0.8 / Group C: 0.4, 0.5 / Group D: 0.2, 0.2, 0.3, 0.5</p>
  </blockquote>
  
  <p>For each replicate data set, I would have the same cluster sizes (A=3, B=3, C=2, D=4) and data values, but would reassign the values to the clusters.</p>
  
  <p>To do this, I could generate random numbers in the range 1-12, assign the first element of group A, then generate random numbers in the range 1-11 and assign the second element in group A, and so on.  The pointer reassignment is fast, and I will have pre-allocated all data structures, but the sampling without replacement seems like a problem that might have been solved many times before.</p>
  
  <p>Logic or pseudocode preferred.</p>