package array;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import LeetCode.AddLinkList.ListNode;

public class ReservoirSampling {
    public ListNode sampling(ListNode head) {
	ListNode s = head;
	Random rand = new Random();
	int count = 1;
	while (head != null) {
	    int position = (int) (rand.nextInt(count) + 1);
	    count++;
	    if (position == 1)
		s = head;
	}
	return s;
    }

    // remember it
    public void reservoirSampling(int k) throws FileNotFoundException,
	    IOException {
	File f = new File("data.txt");
	// creating buffered reader object to read the file contains our data
	BufferedReader br = new BufferedReader(new FileReader(f));
	String currentLine;
	int reservoirSize = 10;
	// reservoirList is where our selected lines stored
	List<String> reservoirList = new ArrayList<String>(reservoirSize);
	// we will use this counter to count the current line numebr while
	// iterating
	int count = 0;
	Random ra = new Random();

	int randomNumber;
	// here we will iterate through the file till it ends
	while ((currentLine = br.readLine()) != null) {
	    // increase the line number
	    count++;
	    if (count <= k) {
		reservoirList.add(currentLine);
	    } else {
		randomNumber = (int) ra.nextInt(count);
		if (randomNumber < reservoirSize) {
		    reservoirList.set(randomNumber, currentLine);
		}
	    }
	}
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
	// TODO Auto-generated method stub

    }

}

@@ -624,956 +624,769 @@
 lic 
-void reservoirSampling(int k) throws FileNotFoundException,%0D%0A%09    IOException %7B%0D%0A%09File f = new File(%22data.txt%22);%0D%0A%09// creating buffered reader object to read the file contains our data%0D%0A%09BufferedReader br = new BufferedReader(new FileReader(f));%0D%0A%09String currentLine;%0D%0A%09int reservoirSize
+List%3CInteger%3E sample(List%3CInteger%3E list, int k) %7B%0D%0A        final List%3CInteger%3E samples = new ArrayList%3CInteger%3E(k);%0D%0A        int count
  = 
-1
 0;%0D%0A
-%09// reservoirList is where our selected lines stored%0D%0A%09List%3CString%3E reservoirList = new ArrayList%3CString%3E(reservoirSize);%0D%0A%09// we will use this counter to count the current line numebr while%0D%0A%09// iterating%0D%0A%09int count = 0;%0D%0A%09Random ra = new Random();%0D%0A%0D%0A%09int randomNumber;%0D%0A%09// here we will iterate through the file till it ends%0D%0A%09while ((currentLine = br.readLine()) != null) %7B%0D%0A%09    // increase the line number%0D%0A%09    count++;%0D%0A%09    if (count %3C= k) %7B%0D%0A%09%09reservoirList.add(currentLine);%0D%0A%09    %7D else %7B%0D%0A%09%09randomNumber = (int) ra.nextInt(count);%0D%0A%09%09if (randomNumber %3C reservoirSize) %7B%0D%0A%09%09    reservoirList.set(randomNumber, currentLine);%0D%0A%09%09%7D%0D%0A%09    %7D%0D%0A%09%7D
+        final Random random = new Random();%0D%0A        for (int item : list) %7B%0D%0A            if (count %3C k) %7B%0D%0A                samples.add(item);%0D%0A            %7D else %7B%0D%0A                // http://en.wikipedia.org/wiki/Reservoir_sampling%0D%0A                // In effect, for all i, the ith element of S is chosen to be included in the reservoir with probability%0D%0A                // k/i.%0D%0A                int randomPos = random.nextInt(count + 1);%0D%0A                if (randomPos %3C k) %7B%0D%0A                    samples.set(randomPos, item);%0D%0A                %7D%0D%0A            %7D%0D%0A            count++;%0D%0A        %7D%0D%0A        return samples;
 %0D%0A  

correct the algorithm