Мне нужно создать систему, которая сравнивает N
элементов.
Система должна сообщить пользователю, какие элементы являются его любимыми из списка N
элементов. Он должен возвращать список сохраненных элементов, ранжированных от наиболее понравившихся до наименее понравившихся по их выбору. Фоновый алгоритм должен выдавать два элемента в каждом раунде, где пользователи голосуют, а фоновый алгоритм сравнивает их и вычисляет лучший результат.
Сначала я подумал, что это классика :Combination without repetition
:
Пример: Есть десять животных (n = 10)
{"Dog", "Cat", "Squirrel", "Chimpanzee", "Ox", "Lion", "Panda", "Walrus", "Otter", "Elephant"}
Если я использую Комбинацию без повторений по формуле n!/k!*(n-k)!
, то будет 45 сравнений
{"Dog", "Cat"},
{"Dog", "Squirrel"},
{"Dog", "Chimpanzee"}
...
{"Cat", "Cat"},
{"Cat", "Chimpanzee"},
{"Cat", "Ox"}
...
Если пользователь выбирает Собаку 5 раз, Собака получает 5 баллов, любые другие, которые были выбраны вместо Собаки, получают 1 балл, а затем идет Кошка, затем Белка и т. д. И список в конце будет выглядеть примерно так:
"Dog" : 8,
"Cat" : 6,
"Squirrel" : 3
...
Но я нахожу эту логику очень неэффективной, потому что пользователям приходится выбирать 45
раз, плюс N
может быть больше 10
, поэтому число резко возрастет и система потеряет смысл.
Знаете ли вы какие-нибудь эффективные алгоритмы для сравнения элементов с отсортированным ранжированным списком в конце в качестве результата?
N
элементов. Затем пользователь решает, нравится ли ему элемент 1 больше, чем элемент 2, или наоборот. Если элемент 1 был выбран вместо элемента 2, элемент 1 получает 5 баллов, а элемент 2 — только 1? После того, как каждая возможная пара в списке была сыграна, вы хотите вернуть список, отсортированный по очкам? Или вы хотите оптимизировать, сколько сравнений было сыграно? Кроме того, если вы хотите второй способ, есть ли какие-либо ограничения с точки зрения пространственной сложности? - person CodingTil   schedule 18.06.2020