如何实现随机迭代器？求指导返回随机顺序元素的迭代器开发

Hey there! Let's figure out how to build that random-order iterator you're working on—using StdRandom.uniform() is the right call, so let's break down exactly where to plug that in and why.

The most efficient and reliable way to create a random-order iterator is to shuffle the element indices upfront (when the iterator is initialized) using the Fisher-Yates shuffle algorithm. This is where StdRandom.uniform() will do the heavy lifting—generating the random indices needed for the shuffle.

Step-by-Step Implementation (Java Example) #

Since StdRandom is commonly used in Princeton's CS curriculum (Java-based), here's a concrete implementation of an iterator that returns elements in random order:

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class RandomOrderIterator<T> implements Iterator<T> {
    private final List<T> sourceElements;
    private final int[] shuffledIndices;
    private int currentPosition;

    // Constructor: Shuffle happens HERE when the iterator is created
    public RandomOrderIterator(List<T> elements) {
        this.sourceElements = elements;
        this.shuffledIndices = new int[elements.size()];
        
        // Initialize index array with 0, 1, 2, ..., n-1
        for (int i = 0; i < elements.size(); i++) {
            shuffledIndices[i] = i;
        }

        // Fisher-Yates Shuffle: Use StdRandom.uniform() to pick random indices
        for (int i = elements.size() - 1; i > 0; i--) {
            // Generate a random integer between 0 and i (inclusive)
            int randomIdx = StdRandom.uniform(i + 1);
            // Swap current index with the random index
            int temp = shuffledIndices[i];
            shuffledIndices[i] = shuffledIndices[randomIdx];
            shuffledIndices[randomIdx] = temp;
        }

        this.currentPosition = 0;
    }

    @Override
    public boolean hasNext() {
        return currentPosition < shuffledIndices.length;
    }

    @Override
    public T next() {
        if (!hasNext()) {
            throw new NoSuchElementException("No more elements to iterate");
        }
        // Get the element at the shuffled index
        T nextElement = sourceElements.get(shuffledIndices[currentPosition]);
        currentPosition++;
        return nextElement;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Remove operation isn't supported by this iterator");
    }
}

Key Details About StdRandom.uniform() Placement #

• Why in the constructor? Shuffling upfront ensures each iteration of the iterator will produce a unique random order, and it's efficient (O(n) time for the shuffle, then O(1) per next() call). This is ideal for large collections, as it avoids repeated overhead during iteration.
• How StdRandom.uniform(i+1) works: It returns a random integer between 0 and i (inclusive), which is exactly what we need for the Fisher-Yates shuffle—this ensures every possible permutation of elements has an equal probability.

Alternative: Pick Random Elements On-the-Fly #

If you're working with a small collection and don't mind slightly lower efficiency, you can skip pre-shuffling and instead pick a random remaining element each time you call next(). Here's how that looks:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class OnTheFlyRandomIterator<T> implements Iterator<T> {
    private final List<T> remainingElements;

    public OnTheFlyRandomIterator(List<T> elements) {
        this.remainingElements = new ArrayList<>(elements);
    }

    @Override
    public boolean hasNext() {
        return !remainingElements.isEmpty();
    }

    @Override
    public T next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        // Use StdRandom.uniform() to pick a random index from remaining elements
        int randomIdx = StdRandom.uniform(remainingElements.size());
        return remainingElements.remove(randomIdx);
    }
}

This is simpler, but note that remove() on an ArrayList is O(n) per call, so it's not great for large datasets.

Usage Example #

To test either iterator, just pass in a list and iterate as usual:

public static void main(String[] args) {
    List<String> fruits = List.of("Apple", "Banana", "Cherry", "Date");
    RandomOrderIterator<String> randomIterator = new RandomOrderIterator<>(fruits);
    
    while (randomIterator.hasNext()) {
        System.out.println(randomIterator.next());
    }
}

Each run will print the fruits in a different random order!

内容的提问来源于stack exchange，提问作者rama96x