使用 java 随机选择哈希集的一个元素

Question

我有一个函数，我必须 randomly 从 HashSet 中选择一个元素，然后测试该元素是否满足条件。如果条件为真，则 return 所选元素，否则我们必须随机选择另一个元素。

我尝试了以下代码：

private  Number[] findClosest( int remCapacity, HashSet<Integer> remainingNodes, VrpProblem problem) {
    int[] demands = problem.getDemands();
    int bestNodeId = -1;
    Iterator<Integer> iter =  remainingNodes.iterator();
            
    Random random = new Random();
               
    while (iter.hasNext()) {
        int nodeId = random.nextInt(remainingNodes.size());
                  
        if (demands[nodeId] > remCapacity) {
            continue;
        }    
        bestNodeId = nodeId;              
     }     
     return new Number[] {new Integer(bestNodeId)}  ;  
}

但是没有用。

Answer 1

您目前没有从 remainingNodes 集合中读取任何值。根据您的解决方案的成本，您可以使用以下方法：

在 List<Integer> 个实例中加载所有 Set<Integer> 值。
随机播放列表。
遍历列表并进行检查。

所以源代码可以是这样的：

List<Integer> list = new ArrayList<Integer>(remainingNodes);
Collections.shuffle(list);
for (Integer value : list) {
    if (yourCheckTestHereWith_value_andOtherVariables) {
        return value;
    }
}

请注意，在某些情况下，Set 中可能没有任何值符合您的条件。您必须在 for 循环之后定义一个后备案例来处理这种情况（抛出异常、return null 等）。

Answer 2

一个解决方案是提供一种方法，该方法 return 是 randomIterator 来迭代设置的内容。这就像一个普通的迭代器一样工作，除了元素是 returned 随机顺序没有重复。它的工作原理如下：

该方法首先将集合放入列表中。这是必要的，以便可以检索单个元素。
使用类似于 Fischer-Yates 的算法开始重新排列列表。当调用 next() 时，随机播放算法继续进行，一次一个元素。迭代器在 O(n) 时间内工作，其中 n 是集合中元素的数量。

Set<Integer> remainingNodes = 
Iterator<Integer> iter = randomIterator(remainingNodes);
    
while (iter.hasNext()) {
    int item = iter.next();
    // do the test
}

return迭代器的方法。

public static <T> Iterator<T>
        randomIterator(Collection<T> collection) {
    
    return new Iterator<T>() {
        List<T> copy = new ArrayList<>(collection);
        int nItems = copy.size();
        
        public boolean hasNext() {
            return nItems != 0;
        }
        
        public T next() {
            int k = (int) (Math.random() * nItems);
            T returnVal = copy.get(k);
            copy.set(k, copy.get(--nItems));
            return returnVal;
        }
    };
}

使用 java 随机选择哈希集的一个元素

Randomly choose an element of a hashset using java

java

hashset