Соревнование
Для данного набора из n целых чисел напишите программу, которая выведет свой лексикографический индекс.
Правила
- Входные данные должны быть только набором уникальных неотрицательных целых чисел, разделенных пробелами.
- Вы должны вывести лексикографический индекс (от 0 до n! -1 включительно) перестановки.
- Никакие библиотеки перестановок или встроенные перестановки не могут быть использованы.
- Вы не можете генерировать набор перестановок или любое подмножество перестановок входных данных, чтобы помочь вам найти индекс.
- Вы также не можете увеличивать или уменьшать данную перестановку до следующей / предыдущей (лексикографически) перестановки.
- Бонусные баллы (-10 байт), если вы найдете способ выполнить это без использования факториалов.
- Время выполнения должно быть менее 1 минуты для n = 100
- Самый короткий код по количеству байтов выигрывает
- Победитель выбран во вторник (22 июля 2014 г.)
Подробнее о перестановках
- http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
- Операция перестановочной группы
- http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html
Примеры
0 1 2 --> 0
0 2 1 --> 1
1 0 2 --> 2
1 2 0 --> 3
2 0 1 --> 4
2 1 0 --> 5
0 1 2 3 4 5 6 7 --> 0
0 1 2 3 4 5 7 6 --> 1
0 1 2 3 4 6 5 7 --> 2
1 3 5 17 --> 0
781 780 779 13 --> 23
81 62 19 12 11 8 2 0 --> 40319
195 124 719 1 51 6 3 --> 4181
code-golf
math
combinatorics
set-theory
permutations
Кайл Маккормик
источник
источник
Ответы:
GolfScript, 12 (22 персонажа - 10 бонусов)
Бонусные баллы за неиспользование факториалов. Входные данные должны быть указаны в STDIN в формате, описанном в вопросе. Вы можете попробовать код онлайн .
источник
CJam, 31, с факториалами
источник
Python 2 (77 = 87-10)
Такой читабельный. Многое встроено. Ух ты.
Мы используем тот факт, что лексикографический индекс перестановки - это сумма по элементам перестановок числа инверсий над этим элементом (значения после него, но под ним), умноженная на факториал количества элементов после него. Вместо того, чтобы оценивать это полиномиальное выражение термин за термином, мы используем нечто похожее на метод Хорнера .
Вместо того, чтобы зацикливаться на индексах массива, мы многократно удаляем первый элемент списка и обрабатываем оставшиеся элементы. Выражение
sorted(p).index(p.pop(0))
подсчитывает количество инверсий после первого индекса, занимая его позицию в отсортированном списке, и в то же время выполняет удаление.К сожалению, мне пришлось использовать Python 2 и взять еще 4 символа для
raw_input
(хотя -1 дляprint
), потому что в Python 3map(int,...)
создает объект карты, который не поддерживает операции со списками,источник
Пиф (13 = 23-10)
Порт моего Python ответа .
Перевод на Python (с некоторыми несущественными вещами, отфильтрованными):
Введенные числа остаются строками, но сортируются как целые, используя eval в качестве ключа. Список перевернут так, что
pop
занимает переднюю, а не заднюю часть.источник
Кобра - 202
Очевидно, что Кобра на самом деле не конкурирует в этом.
источник
J, 5 байтов (15 - 10)
Это выполняется за время O ( n 2 ) и может легко обработать n = 100.
Применение
объяснение
источник