Как найти случайный индекс

В этой статье мы рассмотрим, как случайным образом выбирать элементы из списка в Python. Мы рассмотрим извлечение случайных элементов, а также извлечение нескольких элементов — с повторением и без.

Введение

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

Выбор случайного элемента из списка

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

Для реализации этого подхода рассмотрим некоторые методы генерации случайных чисел в Python: random.randint() и random.randrange(). Дополнительно мы можем использовать random.choice() и поставлять итерабельное число — в результате чего случайный элемент из этого итерабельного числа возвращается обратно.

Использование функции random.randint()

random.randint(a, b) возвращает случайное целое число между a и b включительно.

Нам понадобится случайный индекс в диапазоне от 0 до len(list) — 1, чтобы получить случайный индекс элемента в списке:

import random

test_list = ["1", "2", "3", "4", "5", "6"]
random_index = random.randint(0, len(test_list) - 1)

print(test_list[random_index])

Использование функции random.randrange()

random.randrange(a) — это другой метод, который возвращает случайное число n, равное 0 <= n < a:

import random

test_list = ["1", "2", "3", "4", "5", "6"]
random_index = random.randrange(len(test_list))

print(test_list[random_index])

Так как random.randrange(len(test_list)) возвращает случайно сгенерированное число в диапазоне от 0 до len(test_list) — 1, мы используем его для доступа к элементу в случайном порядке в буквах, как мы делали это в предыдущем подходе.

Этот подход немного проще, чем предыдущий просто потому, что мы не указываем начальную точку, которая по умолчанию равна 0.

Использовании функции random.choice()

Еще лучшим решением, чем последнее было бы использование функции random.choice(), так как это именно та функция, которая предназначена для решения такой задачи:

import random

test_list = ["1", "2", "3", "4", "5", "6"]

print(random.choice(test_list))

Выбор нескольких случайных элементов из списка

Без повторения элементов

Первый метод, который мы можем использовать для случайного выделения более чем одного элемента — random.sample(). Он производит выборку, основываясь на том, сколько выборок мы хотим получить:

import random

test_list = ["1", "2", "3", "4", "5", "6"]

print(random.sample(test_list, 3))

Этот метод выбирает элементы без замены т.е. выбирает без дубликатов и повторений.

С повторением элементов

Как и предыдущая функция, функция random.choices() возвращает список случайно выбранных элементов из заданного итерабельного списка. Однако, она не отслеживает выбранные элементы, поэтому можно получить и дублирующие элементы:

import random

test_list = ["1", "2", "3", "4", "5", "6"]

print(random.choices(test_list, k=3))

Заключение

В этой статье мы рассмотрели несколько способов получения одного или нескольких случайно выбранных элементов из списка на Python.

Мы получили доступ к списку по случайному индексу с помощью randint() и randrange(), а также получили случайные элементы с помощью choices() и sample().

When you want to work with Array elements and their indices, enumerated() can be a good tool:

var a = [0, 1, 8, 3, 10, 6, 2]
var b = [1, 2]
var possibleIndices = a.enumerated()
    .filter{!b.contains($0.element)}
    .map{$0.offset}
print(possibleIndices)
//->[0, 2, 3, 4, 5]

(When b can be large, better make it a Set.)

And then:

(When we can assume b never holds all contents of a.)

var randomIndexToPossibleIndices = Int(arc4random_uniform(UInt32(possibleIndices.count)))
var randomIndex = possibleIndices[randomIndexToPossibleIndices]

If the assumption above cannot be satisfied, possibleIndices can be empty. So you’d better make randomIndex Optional:

var randomIndex: Int? = nil
if !possibleIndices.isEmpty {
    var randomIndexToPossibleIndices = Int(arc4random_uniform(UInt32(possibleIndices.count)))
    randomIndex = possibleIndices[randomIndexToPossibleIndices]
}

Thanks for Martin R.

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

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

#if os(Linux)
    let j = Int(random() % ((count-1)))
#else
    let j = Int(Int(arc4random()) % ((count-1)))
#endif

Даст вам правильный индекс

Если вы затем используете этот индекс и элемент для поиска оригинального элемента в вашем массиве, вы получите свой результат.

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

Посмотрите на функциональное программирование коллекций в swift здесь: Swift Руководство по уменьшению фильтра карт

Например, вы можете использовать фильтр следующим образом (и я не знаю, является ли это лучшим способом):

collection.filter {
  var found = false;
  for element in bCollection {
      if element == $0 {
          found = true;
      }
  }
  return !found; // Might be better to turn true/false thing around in the above code to slightly improve performance.
}

Название Описание

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

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

Образец вопроса

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick (3) должен вернуть индекс 2, 3 или 4. Вероятность возврата каждого индекса должна быть равна.
solution.pick(3);

// pick (1) должен вернуть 0. Потому что только nums [0] равен 1.
solution.pick(1);

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

Решение 1. Используйте промежуточный набор

Сначала мы просматриваем массив от начала до конца, сохраняем индекс элемента, равный цели, в списке промежуточной коллекции и, наконец, возвращаем индекс случайного элемента из промежуточной коллекции.

1. Код решения проблем:

class Solution {

    private int[] nums;

    public Solution(int[] nums) {
        this.nums = nums;
    }


    public int pick(int target) {
        // Открыть промежуточную коллекцию
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            // найти элемент, равный target
            if (nums[i] == target) {
                list.add(i);
            }
        }

        // Если есть только один, возвращаем напрямую
        if (list.size() == 1) return list.get(0);
        // Если их больше двух, случайным образом выбираем один
        return getRandomIndex(list);
    }


    /**
           * Случайно давать подписки
     *
           * @param list индексный набор данного элемента
     * @return
     */
    public int getRandomIndex(List<Integer> list) {
        return list.get(new Random().nextInt(list.size()));
    }
}

Анализ сложности

сложность времени: Необходимо пройти массив один раз, поэтому сложность по времени составляет O (N)

Пространство сложности: Используется ArrayList. Размер ArrayList связан с массивом, поэтому сложность пространства равна O (N)

Решение 2: Алгоритм отбора проб резервуара

Это решение, которое я видел в leetcode. Алгоритм отбора проб пласта кажется профессиональным. Что касается деталей алгоритма, пожалуйста, обратитесь к Baidu. Я не слишком ясен. Здесь я кратко опишу:Учитывая поток данных, длина потока данных очень велика, и N невозможно узнать до тех пор, пока все данные не будут обработаны. Как я могу случайным образом выбрать m неповторений, когда выполняется только обход данных (O (N))? Данные, В соответствии со смыслом нашего вопроса, здесь я прямо дам код для решения проблемы. Специфика не очень ясна, но разве это не означает расширить ваше мышление?

1. Код решения проблем

class Solution {

    private int[] nums;

    public Solution(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        // вернуть индекс, вернуть -1, если не найден
        int index = -1;
        // Записать найденный номер
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
                // Случайный возврат, новый Random (). NextInt ()% count == 0 в качестве вероятности
                if (new Random().nextInt() % count == 0) index = i;
            }
        }

        return index;
    }

}

Анализ сложности

сложность времени: Необходимо пройти массив один раз, поэтому сложность по времени составляет O (N)

Пространство сложности: Новый набор не используется, поэтому сложность пространства равна O (1)

Наконец

Добро пожаловать, чтобы отсканировать QR-код, чтобы следовать общедоступной учетной записи WeChat: «Технический блог Pingtou Ge», Pingtou Ge будет учиться вместе и добиваться прогресса вместе.

Во-первых, вам нужно создать разницу между двумя массивами (если только они не являются очень большими, и случайное выполнение рекурсивно может привести к повышению производительности).

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

#if os(Linux)
    let j = Int(random() % ((count-1)))
#else
    let j = Int(Int(arc4random()) % ((count-1)))
#endif

Дает вам правильный индекс

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

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

Посмотрите на часть функционального программирования коллекций в swift: Swift.

Например, вы можете использовать фильтр следующим образом (и я не знаю, является ли это лучшим способом):

collection.filter {
  var found = false;
  for element in bCollection {
      if element == $0 {
          found = true;
      }
  }
  return !found; // Might be better to turn true/false thing around in the above code to slightly improve performance.
}