Как выбрать пару случайным образом из Arraylist Java

java arraylist

135 просмотра

2 ответа

24 Репутация автора

Пример у меня есть этот ArrayList объекта:

clusterData: [{BitSet: [1, 1], Entropy: 0.0}, {BitSet: [1, 0], Entropy: 1.0}, {BitSet: [0, 0], Entropy: 0.0}, {BitSet: [0, 0], Entropy: 0.0}, {BitSet: [0, 0], Entropy: 0.0}]  

и те с подобными значениями BitSet и Entropy станут возможной парой, и в этом случае это произведет:
Пара # 2 С Пара # 3
Пара # 2 С Пара # 4
Пара # 3 С Пара # 4

Итак, из трех произведенных пар, как я могу выбрать одну случайную из трех возможных пар и сохранить в другом ArrayList?

Это мой код:

System.out.println("clusterData: " + clusterData);

    for (int i = 0; i < clusterData.size()-1; i++){
        for (int j = i+1; j < clusterData.size(); j++){
            if (clusterData.get(i).getBitSet().equals(clusterData.get(j).getBitSet()) && clusterData.get(i).getEntropy() == clusterData.get(j).getEntropy()){
                System.out.println("Pair #" + i + " WITH Pair #" + j);


            }
        }

    }    

Пожалуйста помоги.

Автор: mina_mz Источник Размещён: 18.07.2016 08:24

Ответы (2)


0 плюса

40912 Репутация автора

Возьмите первый случайным образом из всего набора. Возьмите следующий из набора, который на один меньше (чтобы показать, что вы не хотите, чтобы оба числа были одинаковыми). Если второй соответствует или превышает первый, добавьте один. Затем назначьте iи jтак, чтобы i < j.

// pick a from set [0..n)
// pick b from set [0..n-1)
//     which can also be represented as two sets
//           [0..a)[a..n-1)
// add one when b >= a, meaning b is in the sets:
//           [0..a)(a..n)

Random r;
int a = r.nextInt(clusterData.size());
int b = r.nextInt(clusterData.size()-1);
if (b >= a)
  b++;
if (a < b) {
  i = a;
  j = b;
} else {
  i = b;
  j = a;
}
Автор: weston Размещён: 18.07.2016 08:34

0 плюса

59085 Репутация автора

Вы можете просто добавить все возможные пары в a Listи выбрать один из его элементов случайным образом.

Этот код будет выполняться O(N²)там, где Nразмер входных данных.


Более эффективным способом было бы сгруппировать данные кластера по классам эквивалентности (при условии, что отношение подобия является отношением эквивалентности, что, по-видимому, имеет место в данном случае [для этого подхода важна транзитивность)).

Я буду использовать в ClusterDataкачестве имени типа для типа элемента здесь.

Override equalsи hashCodeот ClusterDataдо возвращения true/ тот же хэш - код , если данные кластера похожи.

Затем создайте Map<ClusterData, List<Integer>>отображение различных ClusterDataзначений в список индексов элементов в clusterDataсписке.

Map<ClusterData, List<Integer>> equivalenceClasses = IntStream.range(0, clusterData.size()).boxed()
                                                              .collect(Collectors.groupingBy(clusterData::get)); 

На следующем шаге посчитайте количество возможных пар:

public static int choose2(int elements) {
    return elements * (elements - 1) / 2;
}
int pairCount = equivalenceClasses.values().stream().mapToInt(lst -> choose2(lst.size())).sum();

Выберите один из классов эквивалентности, где каждый класс эквивалентности имеет вероятность, пропорциональную количеству пар, которые он может предоставить:

if (pairCount == 0) {
    throw new IllegalArgumentException("No valid combinations");
}

Random random = ...

int choice = random.nextInt(pairCount);

List<Integer> classIndices = null;

for (List<Integer> indices : equivalenceClasses.values()) {
    choice -= choose2(indices.size());
    if (choice < 0) {
        classIndices = indices;
        break;
    }
}

И, наконец, выберите комбинацию из класса эквивалентности:

int first = random.nextInt(classIndices.size());
int second = random.nextInt(classIndices.size()-1);
if (second >= first) {
    second++;
}
int firstIndex = classIndices.get(first);
int secondIndex = classIndices.get(second);

// TODO: swap indices, if firstIndex needs to be smaller than secondIndex
//       and it's not already the case

System.out.println("Chosen combination: Pair #" + firstIndex + " WITH Pair #" + secondIndex);

Это должно работать O(N)и улучшить производительность для больших входных данных.

Автор: fabian Размещён: 18.07.2016 11:27
Вопросы из категории :
32x32