Перечисление всех интересных разделов тетраэдра

Обновление ответа, 22/22: Используя наблюдение Питера Шора observation о том, что существует гомоморфизм между различными частями и перестановками объектов в кубе, перечислите все такие перестановки, представив группу симметрий куба как подгруппу SymmetricGroup [8] и используя GroupElements/Permute, найти назначения центроидов с помощью решателя Mathematica SAT, выбрать наборы точек с различными значениями единственного числа, немного больше деталей и полный код, приведенный здесь

Вопрос

Интересным 2D-сечением является плоскость, проходящая через центр правильного трехмерного симплекса и двух других точек, каждая из которых является центроидом некоторого непустого подмножества вершин. Он определяется двумя подмножествами вершин. Например, {{1}, {1,2}} дает плоскость, определяемую 3 точками - центром тетраэдра, первой вершиной и средним значением первой и второй вершин.

Интересный набор секций - это набор, в котором нет двух секций, определяющих одну и ту же плоскость при перемаркировке вершин. Например, набор {{{1}, {2}}, {{3}, {4}}} не интересен. Существует ли эффективный подход к поиску интересного набора интересных разделов? Мне нужно что-то, что могло бы обобщить аналогичную задачу для трехмерных участков 7D симплекса и закончить за одну ночь.

Мой попытанный подход ниже. Одна проблема заключается в том, что если вы игнорируете геометрию, некоторые эквивалентные секции будут сохранены, поэтому я получу 10 секций вместо 3. Большая проблема заключается в том, что я использовал грубую силу, и она определенно не масштабируется и (требуется 10 ^ 17 сравнений для 7D симплекса)

_{(источник: yaroslavvb.com)}

Вот код Mathematica для создания картинки выше.

entropy[vec_] := Total[Table[p Log[p], {p, vec}]];
hadamard = KroneckerProduct @@ Table[{{1, 1}, {1, -1}}, {2}];
(* rows of hadamard matrix give simplex vertex coordinates *)

vertices = hadamard;
invHad = Inverse[hadamard];
m = {m1, m2, m3, m4};
vs = Range[4];

(* take a set of vertex averages, generate all combinations arising \
from labeling of vertices *)
vertexPermutations[set_] := (
   newSets = set /. Thread[vs -> #] & /@ Permutations[vs];
   Map[Sort, newSets, {2}]
   );
(* anchors used to define a section plane *)

sectionAnchors = Subsets[{1, 2, 3, 4}, {1, 3}];
(* all sets of anchor combinations with centroid anchor always \
included *)
anchorSets = Subsets[sectionAnchors, {2}];
anchorSets = Prepend[#, {1, 2, 3, 4}] & /@ anchorSets;
anchorSets = Map[Sort, anchorSets, {2}];
setEquivalent[set1_, set2_] := MemberQ[vertexPermutations[set1], set2];
equivalenceMatrix = 
  Table[Boole[setEquivalent[set1, set2]], {set1, anchorSets}, {set2, 
    anchorSets}];
Needs["GraphUtilities'"];
(* Representatives of "vertex-relabeling" equivalence classes of \
ancher sets *)
reps = First /@ StrongComponents[equivalenceMatrix];

average[verts_] := Total[vertices[[#]] & /@ verts]/Length[verts];
makeSection2D[vars_, {p0_, p1_, p2_}] := Module[{},
   v1 = p1 - p0 // Normalize;
   v2 = p2 - p0;
   v2 = v2 - (v1.v2) v1 // Normalize;
   Thread[vars -> (p0 + v1 x + v2 y)]
   ];

plotSection2D[f_, pointset_] := (
   simplex = 
    Graphics3D[{Yellow, Opacity[.2], 
      GraphicsComplex[[email protected]@hadamard, 
       Polygon[Subsets[{1, 2, 3, 4}, {3}]]]}];
   anchors = average /@ pointset;
   section = makeSection2D[m, anchors];
   rf = Function @@ ({{x, y, z, u, v}, 
       And @@ Thread[invHad.{1, x, y, z} > 0]});
   mf = Function @@ {{p1, p2, p3, x, y}, f[invHad.m /. section]};
   sectionPlot = 
    ParametricPlot3D @@ {Rest[m] /. section, {x, -3, 3}, {y, -3, 3}, 
      RegionFunction -> rf, MeshFunctions -> {mf}};
   anchorPlot = Graphics3D[Sphere[Rest[#], .05] & /@ anchors];
   Show[simplex, sectionPlot, anchorPlot]
   );
plots = Table[
   plotSection2D[entropy, anchorSets[[rep]]], {rep, reps}];
GraphicsGrid[Partition[plots, 3]]

Ответ 1

Правильное решение для программирования в контуре:

Обратите внимание, что центры входят в проективные пары - так идентифицируйте и удерживайте только половину центров, которые находятся в одной или других полусферических крышках множества центров. Пары дополняют друг друга. Примерное правило: все подмножества, содержащие вершину 1, и те, что на "экваторе", те, которые содержат вершину 2, и на этом множестве "экватор", те, которые содержат вершину 3, и т.д., Рекурсивно сохраняя граничную половину, примыкающую к наименьшему индексированному вершина.
Заметим, что для каждого подсимплекса либо подсимплекс смежна с вершиной 1, либо имеет расстояние 1 от симплекса. (Причина: каждая новая вершина в тетраэдре привязана к каждой предыдущей вершине тетраэдра - следовательно, каждый подсимплекс либо падающий на вершину 1, либо вершина 1 связана с каждой вершиной симплекса.) Следовательно, существует только две популяции каждого вид подсимплекса (относительно заданной вершины). (Мы можем заменить это наблюдение решением только сохранить меньший член каждой проективной пары, но тогда правило для маркировки вершин сложнее.)
Тетраэдры полностью симметричны при перестановке вершинных меток. Следовательно, любой "интересный раздел" эквивалентен другому разделу, содержащему только ведущий сегмент вершин, т.е. Может быть идентифицирован среди вершин Range [1, n] для некоторого n.
Соблюдая приведенное выше, мы обнаруживаем, что из интересного раздела есть сюръекция к набору графов. Для каждого графика мы должны перечислять согласованные членства в вершинах (описано ниже). За исключением одной вершины, вершины графа попадают в пары
- Пара содержит все центры заданной мощности (все подсимплики заданной размерности).
- Один член пары содержит центры, инцидентные вершине 1.
- Другой член пары содержит центры, не инцидентные вершине 1.
- Специальная вершина - это либо центр, содержащий все вершины, либо его проективную пару ( "пустой центр" ).
- Если граф содержит любой член пары, он должен (по крайней мере) содержать элемент, содержащий центры, падающие на 1 (или вершины могут быть перемаркированы, чтобы сделать это).
Края графа взвешены. Вес - это количество вершин, разделяемых этими двумя центрами. Существуют ограничения на вес, основанные на мощности центров на каждом конце и на основе того, являются ли две вершины как первыми членами, так и вторыми членами или являются одним из каждого. (Например, "один из каждого" не может совместно использовать вершину 1.)
Граф - полный подграф на множестве вершин, содержащий специальную вершину. Например, для тетраэдра граф представляет собой K_ {3} на множестве вершин, указанных выше, причем одна вершина является специальной и с весами ребер.
Раздел представляет собой график с последовательным применением меток к центрам в конце каждого ребра (т.е. последовательно помеченным для учета количества общих вершин, обозначенных весом кромки, и что каждое подмножество в одном наборе вершин графа содержит вершина 1). Поэтому данный график может представлять несколько разделов (с помощью разных меток). (Что не так много вариантов, как кажется, если они будут иметь смысл в секунду.)
Раздел не интересен, если матрица, составленная из координат ее центров, имеет нулевой определитель.

В случае трех измерений с четырьмя вершинами мы получаем следующие множества (мы используем короткую проективную пару, потому что в этом примере достаточно видимости, чтобы не требовать более простого правила отклонения метки вершин):
0: проективная пара {1,2,3,4}
1: {1}
1 ': {2}, {3}, {4}
2: {1,2}, {1,3}, {1,4}
2 ': проективные пары до 2 (так опущены)
3: проективные пары к 1 '(так опущены)
3 ': проективные пары до 1 (так опущены)

Ограничения меток:
{0- > х, х}
{0- > х", х}
{1- > 1,1} - запрещено: центры не включены дважды

{1- > 1', 0}
{1- > 2,1}
{2- > 2,1}
Никакие другие веса не возможны с этими вершинами графа.

Граф является инцидентом K_ {3} на 0, следующие графики сохраняют правила выбора графа:
A: {0- > 1,1}, {0- > 1 ', 1}, {1- > 1', 0}
B: {0- > 2,2}, {0- > 2,2}, {2- > 2,1}

A имеет только одну маркировку: {1}, {2}, {} и ваш трехугольный интересный набор. Эта маркировка не имеет детерминанта нуля. B имеет только одну маркировку: {1,2}, {1,3}, {} и ваш квадратный интересный набор. Эта маркировка не имеет нулевого определителя.

Преобразование в код остается как упражнение для читателя (потому что я должен уйти на работу).