Забрутфорсить симметрии?

[B@R5uk]

У меня имеется множество из n точек в m-мерном пространстве, и имеется высокая вероятность, что это множество или какие-то его подмножества симметричны. Я хочу эти симметрии (и, возможно, симметричные подмножества) найти. С какой стороны лучше к этой задаче подойти, чтобы решить её наименее трудозатратно?

[wrest]

B@R5uk
А что значит "множество m-мерных точек симметрично'?

Пусть m=2, а точек n=5.

[B@R5uk]

wrest в сообщении #1721239 писал(а):

Пусть m=2, а точек n=5.

Правильный пятиугольник, например, (вершины его, точнее) или квадрат с точкой в центре. Или правильный треугольник и две точки в рандомных местах и, поэтому, не относящиеся с симметричной части. Или даже правильный шестиугольник с одной пропущенной точкой. Все такие случаи хотелось бы найти.

В данном случае под симметрией имеется в виду такое линейное преобразование пространства (не обязательно с положительным определителем, отражение тоже допустимо как часть движения), которое сохраняет расстояния между всеми точками; и для которого образ и оригинальное множество имеет более чем или равно m+1 совпадающих точек. Последнее требование связано с тем, что для однозначного задания такого движения необходимо достаточное количество информации (я, правда, мог промахнуться с количеством точек, если что, проверьте, пожалуйста).

-- 29.03.2026, 19:36 --

Я боюсь, что если совсем в лоб делать, сопоставляя каждой точке каждую, до тех пор, пока движение не будет однозначно определено, то выйдет что-то вроде нелепо большого числа комбинаций:

$$C_n^{m+1}A_n^{m+1}$$

[wrest]

B@R5uk в сообщении #1721252 писал(а):

Или даже правильный шестиугольник с одной пропущенной точкой. Все такие случаи хотелось бы найти.

Или правильный 100-угольник с пропущенными 95-ю вершинами?

[B@R5uk]

wrest, если это 5 последовательных вершин 100-угольника, то почему бы и нет? Совмещаем 3 пары вершин, ещё одна находит пару самостоятельно, а для одной нет прообраза и у одной нет образа в исходном множестве. Всё работает без проблем. По крайней мере, если это делать вручную.

[dgwuqtj]

B@R5uk в сообщении #1721252 писал(а):

Я боюсь, что если совсем в лоб делать, сопоставляя каждой точке каждую, до тех пор, пока движение не будет однозначно определено, то выйдет что-то вроде нелепо большого числа комбинаций:

$$C_n^{m+1}A_n^{m+1}$$

Если останавливать перебор, когда движение точно не существует, то куча комбинаций отвалится. Скажем, если все расстояния между точками различны, то останется $C_n^2 A_n^2 = O(n^4)$ проверок. И в этом случае можно ещё улучшить до $O(n^3 \log n)$: сначала переберём одну точку и её образ, потом для каждого варианта отсортируем остальные точки по расстоянию до исходной точки и до её образа, ну и проверим эти списки на совпадение расстояний.

А вот если $n \sim m$ и ваш набор похож на вершины правильного симплекса, то идей нет.

[B@R5uk]

dgwuqtj в сообщении #1721256 писал(а):

А вот если $n \sim m$ и ваш набор похож на вершины правильного симплекса, то идей нет.

Ну, в случае правильного m-мерного симплекса будет ровно $(m+1)!$ комбинаций, тут никуда не денешься. Группой движений будет $S_{m+1}$

dgwuqtj в сообщении #1721256 писал(а):

Скажем, если все расстояния между точками различны, то останется $C_n^2 A_n^2 = O(n^4)$ проверок.

К сожалению, много расстояний планируется быть одинаковым. Взять, например, тот же икосаэдр или курносый куб. Это я продумываю подход к автоматическому анализу локальных решений задачи Таммеса.

dgwuqtj в сообщении #1721256 писал(а):

А вот если $n \sim m$ и ваш набор похож на вершины правильного симплекса, то идей нет.

Размерность пространства планируется не очень большая 3-6 где-то. А вот точек может быть много и даже 4-я степень по их числу может оказаться проблемой.

[ИСН]

Кто-то должен произнести слова "приведение к главным осям".

[B@R5uk]

ИСН, спасибо за упоминание, но можно по-подробней применительно к моей задаче? Потому что я только знаю, как положительно определённую квадратичную форму к главным осям приводить.

[ИСН]

Вот и тут надо привести форму, так называемый тензор инерции. Впрочем, как раз в самом сложном случае (с высокой симметрией) это нам не поможет.

[B@R5uk]

ИСН Если вы имеете в виду матрицу косинусов углов между векторами точек в системе центра масс, то в моём случае это работать не будет. Потому что одна левая точка (или одна отсутствующая) и всё насмарку.

[Sender]

B@R5uk в сообщении #1721238 писал(а):

С какой стороны лучше к этой задаче подойти, чтобы решить её наименее трудозатратно?

Можно попробовать применить Nauty&Traces, раскрасив рёбра графа попарных расстояний так, что рёбрам одинаковой длины соответствуют одинаковые цвета. Изначально поддерживаются только вершинно-раскрашенные графы, но в мануале рассказывается, как решить задачу поиска автоморфизмов в рёберно-раскрашенных графах (см раздел 14).
https://pallini.di.uniroma1.it/Guide.html

-- Вт мар 31, 2026 22:39:00 --

Впрочем, если симметричен только какой-то подграф, не сработает.