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());
}
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;}
else
{
first.next = oldfirst;
oldfirst.previous = first;
}
N++;
}
public Item removeLast(){
if (last == null) throw new RuntimeException();
Item item = last.item;
if (first == last)
{
first=null;
last=null;
}
else{
last =last.previous;
last.next = null;
}
N--;
return item;
}
, , RandomCollection n . , 1-N, int [] , .
private static int getNumberOfCallsForComprehensiveCallout(RandomCollection<Integer> test, int n){
int calltimes =0;
int flag = 1;
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;
calltimes++;
}
return calltimes;
}