Лучший из n выбранных элементов путем сравнения алгоритма

Мне нужно создать систему, которая сравнивает 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, поэтому число резко возрастет и система потеряет смысл.

Знаете ли вы какие-нибудь эффективные алгоритмы для сравнения элементов с отсортированным ранжированным списком в конце в качестве результата?


person Stefanija    schedule 18.06.2020    source источник
comment
Итак, просто чтобы проверить, правильно ли я понял: пользователю представлены два случайно выбранных, но разных элемента из списка N элементов. Затем пользователь решает, нравится ли ему элемент 1 больше, чем элемент 2, или наоборот. Если элемент 1 был выбран вместо элемента 2, элемент 1 получает 5 баллов, а элемент 2 — только 1? После того, как каждая возможная пара в списке была сыграна, вы хотите вернуть список, отсортированный по очкам? Или вы хотите оптимизировать, сколько сравнений было сыграно? Кроме того, если вы хотите второй способ, есть ли какие-либо ограничения с точки зрения пространственной сложности?   -  person CodingTil    schedule 18.06.2020
comment
Каждый получает одно очко при выборе над другим, с этим я хотел сказать, если вы выбираете собаку в качестве первого элемента, то собаку нужно сравнивать с 9 другими, если в сценарии собака выбрана пять раз (более чем пять других животных), чем собака получает 5 баллов. На следующей итерации мы получаем второй элемент, например. кошка сравнивается с 8 другими, потому что у нас есть результат сравнения собаки и кошки, который может быть либо 0, либо 1 баллом для кошки. так далее..   -  person Stefanija    schedule 18.06.2020
comment
Я хочу оптимизировать количество сравнений более конкретно, чтобы не нужно было сравнивать все со всеми, не знаю, есть ли какое-либо логическое решение для этого, но для больших N чисел эта логика бессмысленна, поскольку пользовательский опыт   -  person Stefanija    schedule 18.06.2020
comment
Нет ограничений по площади   -  person Stefanija    schedule 18.06.2020
comment
Второе решение, которое, по моему мнению, было ограничено первыми 5 лучшими элементами, может немного оптимизировать, но все же не лучшее решение @CodingTil   -  person Stefanija    schedule 18.06.2020


Ответы (1)