Uniform random access to the collection

I want to implement evenly random access to a specific collection with N numbers, as each item in the collection will be available evenly with 1 / N chances. I put all the items in the modified double linked list. then a circular offset at random time, delete the last element, and then add it as the first. finally select the first item. I used it to check the number of calls that would be needed to cover the entire item without moving the item from the list. The total number of mines needed is less than expected. I wonder if the implementation is really uniformly random? do you think my implementation is really random? I have been debugging this for quite some time, but still don't know.

public Item callout(){
       for (int j=0; j<StdRandom.uniform(N); j++)
        {
            this.addFirst(this.removeLast()); 
// circular shift the queue by StdRandom.uniform(N)times, always return the first item;
        }
       return first.item;
   } 

public void addFirst(Item item){
   Node<Item> oldfirst = first;
   first = new Node<Item>();
   first.item = item;
   first.previous = null;

if (last == null) 
       {last = first;  first.next = null;} //if it the first element added.   if last.next = null == last = null;!!!! 
   else 
   {
       first.next = oldfirst;
       oldfirst.previous = first;
   }
    N++;
 }

public Item removeLast(){
 if (last == null) throw new RuntimeException();
 Item item = last.item;


 // if right now only one element exists in the container
  if (first == last)
 {
   first=null;
   last=null;
 }

 else{
 last =last.previous;
 last.next = null;   
 // old first becomes first;    optional operation, easy way to tell if it the header.
 }
   N--;

 return item;
 }

, , RandomCollection n . , 1-N, int [] , .

private static int getNumberOfCallsForComprehensiveCallout(RandomCollection<Integer> test, int n){
    // create an array of the same number of items in collection, each with a Flag indicating whether it has beeen called
    int calltimes =0;     // calltimes stands for the numofcalls needed to reach a comprehensive call
    int flag = 1;     // flag used to indicate if this item has been called
    int [] c = new int [n];
      Arrays.fill(c, flag);
      int NumberOfFlags = n;


    while(NumberOfFlags != 0){
        int numbercalled = test.callout();
        if (c[numbercalled-1]==1) {NumberOfFlags--; c[numbercalled-1]=0;}
        else;   // indicate this item has been called earlier.
        calltimes++;
    //  System.out.println(calltimes);

    }
    return calltimes;   // return the number of calls for comprehensive callout each time this method is called.
}
+3
1

, -

-, ( ) , . Infact .

-, callout() StdRandom.uniform(N) . -

public Item callout(){
    int randomRotate = StdRandom.uniform(N);
    for (int j = 0; j < randomRotate; j++)
    {
        this.addFirst(this.removeLast()); 
    }

    return first.item;
}

, , StdRandom.uniform(N) for. 10 -

   0    1    2    3    4    5    6    7    8    9 
1001 1813 2074 2043 1528  902  454  144   37    4  
+1

All Articles