История изменений
Исправление aedeph_, (текущая версия) :
Для одномерного случая, например, разбиваем отрезок, которому принадлежат все точки на подобласти, где сохраняется порядок расстояний:
[0, 1, 3]
[0.0, 0.5] 1 2 3
[0.5, 1.5] 2 1 3
[1.5, 2.0] 2 3 1
[2.0, 3.0] 3 2 1
Точек перехода будет число инверсий от 1..n до n..1, то есть n(n-1)/2.
Для любой точки binary search'ом по множеству в log(n(n-1)/2 +1) находим какому подотрезку она принадлежит, это эквиалентно log(n). Возвращаем уже сгенерированную перестановку.
Исправление aedeph_, :
Для одномерного случая, например, разбиваем отрезок, которому принадлежат все точки на подобласти, где сохраняется порядок расстояний:
[0, 1, 3]
[0.0, 0.5] 1 2 3
[0.5, 1.5] 2 1 3
[1.5, 2.0] 2 3 1
[2.0, 3.0] 3 2 1
Точек перехода будет число инверсий от 1..n до n..1, то есть n(n-1)/2.
Для любой точки binary search'ом по множеству в log(n^2 + 1) находим какому подотрезку она принадлежит, это эквиалентно log(n). Возвращаем уже сгенерированную перестановку.
Исходная версия aedeph_, :
Для одномерного случая:
[0, 1, 3]
[0.0, 0.5] 1 2 3
[0.5, 1.5] 2 1 3
[1.5, 2.0] 2 3 1
[2.0, 3.0] 3 2 1
Точек перехода будет число инверсий от 1..n до n..1, то есть n(n-1)/2.
Для любой точки binary search'ом по множеству в log(n^2 + 1) находим какому подотрезку она принадлежит, это эквиалентно log(n). Возвращаем уже сгенерированную перестановку.