Случайная и полная итерация, которая масштабируема?

Question

Предположим, у меня есть список списков, например:

• [[a, b, c, d, e],
• [f, g, h],
• [i, j, k, l]]

Таким образом, внешний список имеет размер 3, а внутренние списки имеют размеры 5, 3 и 4.

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

• генерирует случайное число между 0 и totalListsSize (5 + 3 + 4) = 12, например, randomIndex 7
• , перебирает все списки и вычитает их размер, если этобольше их размера, например randomIndex 7 - firstListSize 5 = newRandomIndex 2
• возвращает элемент в следующем списке, randomIndex 2 in secondList = element g.

Проблема заключается в том, что последовательный выбор должен быть полным и исчерпывающим: После 12 последовательных выборов в приведенном выше примере я должен был выбрать каждый элемент один раз.

Есть ли способ сделать это масштабируемым?

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

Answer 1

Почему бы вам не сгенерировать перестановку всех возможных индексов (другими словами, вы перемешиваете последовательность [0,12)). Тогда вы знаете, что ударите по всем элементам ровно один раз и в случайном порядке.

Для эффективного поиска вы можете сохранить промежуточную сумму длин массива. В вашем примере: 0, 5, 8, 12. Таким образом, вы можете выполнить двоичный поиск, чтобы найти любой массив по «общему индексу».

Answer 2

Ну, вы можете создать набор возможных индексов, случайным образом выбрать один из них, удалить выбранный и получить доступ к соответствующему объекту.

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

Оба подхода потребуют некоторой инициализации, но вам все равно придется вести бухгалтерский учет.

Другой подход может заключаться в том, чтобы сохранить выбранные индексы в наборе, и после создания нового случайного индекса вы можете проверить, есть ли новый уже в «используемом» наборе. Однако, если вы хотите выбрать высокий процент от всего пула, этот подход будет все медленнее и медленнее, поскольку вы будете чаще использовать уже используемые индексы. Для выбора только нескольких из большого списка этот подход может быть лучше, так как он не требует такой большой инициализации и памяти.

Answer 3

Используйте следующий класс:

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}

Answer 4

Я бы предложил следующее:

• Сохранить список списков целых чисел mark, который запоминает выбранные элементы в списке

• Затем, чтобы определить, какой элементсоответствует вашему randomIndex do:

  List<List<Integer>> mark    = // ... one mark list for each array
  E[][] lists = // ... the lists you want to select random elements from
  
  void selectAllElementsOnce( int totalElementCount ){
      Random r = new Random();
      for(int selected = 0; selected < totalElementCount; selected++){
          E element = this.elementForRandomIndex(r.nextInt(totalElementCount - selected));
          // do something with this element
      }
  }
  
  E elementForRandomIndex( int randomIndex ) {
      for(int i = 0; i < lists.length; i++ ) {
          if(randomIndex < lists[i].length - mark.get( i ).size()) {
              int j = 0;
              while(mark.get( i ).size() > j && mark.get( i ).get( j ) <= randomIndex) {
                  randomIndex++ ;
                  j++ ;
              }
              mark.get( i ).add( j, randomIndex );
              return lists[i][randomIndex];
          } else {
              randomIndex -= lists[i].length - mark.get( i ).size();
          }
      }
      throw new IndexOutOfBoundsException();
  }
  

Сложность этого решения в O (numberOfLists + MaximumListSize) для реализации списков меток, которые обеспечивают доступ к элементу в постоянное время(например, ArrayList).Обратите внимание, что он не является произведением обоих терминов, поскольку повторяется только один список.

Answer 5

Можно ли удалять элементы из списков, когда вы «выталкиваете» их?

Если это так, вы можете просто сделать это: просто удалите элемент из списка при его выборе, а затем вычтите один изобщий размер до расчета следующего индекса и повторите при необходимости.