A program to select a random subset of a set uniformly at random

RandomSubsetSimulation.java

/**
 * Problem: Print the statistics of RandomSubset algorithm when the experiment
 * of choosing a subset at random is done the specified number of times.
 */
import java.util.*;
class RandomSubsetSimulation {
  static final Random r = new Random(System.currentTimeMillis()); //fix for the bug in the SO thread (see below)
  public static void main(String[] args) { 
    // arg[0] = the max number n in the set: {1, 2, 3, ... n}
    // arg[1] = the number of times the experiment is to be done
    printStats(arrayToN(Integer.valueOf(args[0])), Integer.valueOf(args[1]));
  }
  static void printStats(int[] set, int nexp) {
    Map<List<Integer>, Integer> freq = new HashMap<>();
    for (int i = 1; i <= nexp; i++) {
      List<Integer> subset = ranSub(set);
      Integer f = freq.get(subset);
      if (f == null)
        freq.put(subset, 1);
      else
        freq.put(subset, f+1);
    }
    System.out.println("Frequencies of chosen subsets ....");
    int total = 0, ns = 0;
    int exact = nexp / (1 << set.length);
    for (Map.Entry<List<Integer>, Integer> entry : freq.entrySet()) {
      int v = entry.getValue();
      int diff = exact - v; 
      System.out.printf("%20s : %10d, %10d, %.2f\n", entry.getKey(), v, diff, ((double)v*100)/nexp);
      total += v;
      ns += 1;
    }
    System.out.println("Total: " + total + ", number of subsets with a frequency > 0: " + ns);
    System.out.println("Total # of subsets possible: " + (1L<<set.length));
    assert nexp == total : "bug: nexp and total don't match :-( " + nexp + ", " + total;
  }
  static List<Integer> ranSub(int[] s) {
    int n = ranInt(s.length); // captures the required probability
    Integer[] ss = new Integer[Integer.bitCount(n)];
    int i = 0, j = 0;
    while (n > 0) {
      if ((n & 1) == 1) {
        ss[j] = s[i];
        j += 1;
      }
      i += 1;
      n >>>= 1;
    }
    return Arrays.asList(ss);
  }
  static int ranInt(int nbits) {
//    Random r = new Random(System.currentTimeMillis()); //the bug as found in http://stackoverflow.com/questions/26048509/generating-a-subset-uniformly-at-random -- fixed by moving this to a static variable
    int n = 0; // start with all bits unset
    int p2 = 1; // powers of 2
    for (int i = 0; i < nbits; i++) {
      if (r.nextDouble() < 0.5)
        n |= p2;
      p2 <<= 1;
    }
    return n; //doesn't matter if it's negative value, only bits are of interest
  }
  ///////////////////////////// HELPERS ///////////////
  static int[] arrayToN(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = i + 1;
    return a;
  }
  static int[] toSortedIntArray(String[] ss) {
    int[] ints = new int[ss.length];
    int i = 0;
    for (String s : ss) {
      ints[i++] = Integer.valueOf(s);
    }
    Arrays.sort(ints);
    printArray(ints);
    return ints;
  }
  static void printArray(int[] p) {
    System.out.print("[");
    for (int i = 0; i < p.length - 1; i++) {
      System.out.print(p[i]);
      System.out.print(", ");
    }
    if (p.length != 0)
      System.out.print(p[p.length - 1]);
    System.out.println("]");
  }
}