Блог

Не уверен, что это правильное место, но у меня есть вопрос, связанный с алгоритмом, и я не могу придумать эффективный алгоритм. Итак, я решил поделиться своей постановкой проблемы .. 🙂 Чтобы упростить то, что я пытаюсь объяснить, позвольте мне создать гипотетический пример.

Предположим, у меня есть список, содержащий объект, который содержит две вещи..

 lets say product id and price
  

Итак, это длинный-предлинный список .. что-то вроде инвентаря..
исходя из этого, я определил три ценовых сегмента.. низкая цена, средняя цена и высокая цена
и затем k1, k2, k3, где k1, k2 и k3 — соотношения.
Итак, теперь задача в том,, чтобы собрать товары из этого огромного инвентаря таким образом, чтобы было n1 товаров из диапазона низких цен, n2 товаров из диапазона средних цен и n3 товаров из диапазона высоких цен… где n1: n2:n3 == k1:k2:k3

Теперь, как мне эффективно достичь следующего. Я нацелен на низкую цену в 100 долларов, и мне нужно собрать 20 товаров из этого ассортимента.. средний ценовой диапазон, вероятно, составляет 500 долларов и так далее

Итак, я начинаю со 100 долларов .. и затем ищу элементы от 90 до 100, а также от 100 до 110, Допустим, я нашел 5 продуктов в интервале 1 low (90,100) и 2 продукта в интервале 1 high (100,110), затем я перехожу к следующему низкому интервалу и следующему высокому интервалу. Я продолжаю делать это, пока не получу количество продуктов в этом интервале.

Как мне это сделать?? Также может быть случай, когда количество продуктов в определенном ценовом диапазоне меньше, чем мне нужно.. (возможно, средний ценовой диапазон составляет 105 долларов …) .. итак, что мне делать в этом случае.. Пожалуйста, простите меня, если это не та платформа .. из вопроса вы можете понять, что это больше похоже на дискуссионный вопрос, а не на вопрос типа «Я получаю эту ошибку». Спасибо

Вероятно, вы ищете алгоритм выбора.
Сначала найдите n1 ‘й наименьший элемент, пусть это будет e1 , а список с нижней границей — это все элементы, такие что element <= e1 .
Сделайте то же самое для других диапазонов.

псевдокод для списка с нижней границей:

 getLowerRange(list,n):
  e <- select(list,n) 
  result <- []
  for each element in list:
     if element <= e:
         result.append(element)
  return result
  

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

Обратите внимание, что алгоритм выбора является O(n) , поэтому этот алгоритм будет потреблять линейное время, связанное с размером вашего списка.

Подход 1

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

Подход 2

Если назначение сегмента product-price предназначено для предварительного задания, например, путем передачи соответствующих значений цен для каждого сегмента при вызове функции, вы можете захотеть отсортировать товары по цене и использовать двоичный поиск для выбора m-ближайших соседей (например). Параметр m может быть указан в соответствии с соотношениями. Если вы укажете максимальное расстояние, вы можете отклонить товары, которые находятся за пределами желаемого ценового диапазона.

Подход 3

Если назначение ценового сегмента продукта необходимо определять автономно, вы могли бы применить свой алгоритм выбора кластеризации, например, k-means, для назначения ваших продуктов, скажем, k = 3 ценовым сегментам. Для фактического выбора продукта вы можете действовать аналогично описанному выше.

Похоже, вам следует попробовать решение для базы данных, а не использовать список. Ознакомьтесь с sqlite. По умолчанию он на Python