Камень, ножницы, бумага для произвольного нечетного числа элементов
Как я эффективно создаю игру рок-бумаги ножниц для n элементов, где n является каким-либо нечетным числом> =3.
Другими словами, я хочу непереходное полное упорядочивание n элементов, таким образом, что каждый элемент больше, чем (n-1)/2 другие элементы, и каждый элемент меньше, чем (n-1)/2 другие элементы.
2 ответа
Фантастика, спасибо!
В качестве другого подхода (вдохновленного вашим), k бьет k+1 (mod n-1), k+2 (mod n-1) и т.д... для следующих (n-1)/2 элементов.
Предположим, что ваши предметы пронумерованы 0,1,2,...,n-1.
Пункт i побеждает пункт j, если i - j (mod n) > (n-1)/2.
Другими словами, вы можете повернуть список так, чтобы выбранный вами элемент оказался в середине списка:
i - (n-1) / 2, ..., i-2, i-1, i, i+1, i+2, ..., i + (n-1) / 2
Тогда элемент i побеждает все элементы, расположенные ниже него в списке.
Матрица i vs j будет выглядеть так:
0 1 2 3 4
0 - L L W W
1 W - L L W
2 W W - L L
3 L W W - L
4 L L W W -
Это не единственная возможность, но, вероятно, самая простая. Вы можете построить любую матрицу, которая подчиняется этим правилам:
- Все значения на диагонали равны нулю.
- Остальные значения равны 1 или -1 (выигрыш, проигрыш).
- Это кососимметричная матрица.
- Она имеет ровно (n-1)/2 выигрышей и проигрышей в каждой строке и каждом столбце.
Вот еще один более сложный пример:
0 1 2 3 4
0 - L W W L
1 W - W L L
2 L L - W W
3 L W L - W
4 W W L L -
Или сформулируем по-другому:
0 beats 2 and 3. 1 beats 0 and 2. 2 beats 3 and 4. 3 beats 1 and 4. 4 beats 0 and 1.
В этом примере можно перемаркировать элементы, чтобы получить ту же логику, что и в предыдущей игре. Однако я сомневаюсь, что это верно в общем случае.