Это хорошо замаскированная проблема в комбинаторике.Во-первых, обратите внимание, что это кольцо целых чисел;линейный «массив» является выбором реализации, а не частью анализа прочности.Давайте посмотрим на второй случай, заданный как (1,2,6,3,4,5):
1
5 2
4 6
3
Каждый элемент появляется ровно в двух терминах.Таким образом, мы имеем простую линейную комбинацию элементов с коэффициентами -2, 0 2. Если элемент больше, чем оба соседа (например, 5), коэффициент равен 2;если меньше, чем оба соседа (например, 1), это -2;если между, две операции abs отменяются, и это 0 (например, 4).
Лемма: сила должна быть четным числом.
Таким образом, суммирование и некоторые преобразованияможет быть исследовано достаточно легко с помощью простого анализа.Наибольшее число всегда имеет коэффициент +2;самый маленький всегда имеет коэффициент -2.
Вы можете найти «близкие относительные» перестановки, найдя взаимозаменяемые элементы.Например, вы можете всегда менять местами самые большие два элемента (6 и 5) и / или самые маленькие два элемента (1 и 2), не влияя на прочность.Например, 6 и 5 можно поменять местами, потому что они строго больше, чем их соседи:
(6-2) + (6-3) + (5-1) + (5-4) =
(5-2) + (5-3) + (6-1) + (6-4) =
2*6 + 2*5 - 2 - 3 - 1 - 4
1 и 2 можно поменять местами, даже если они находятся рядом, по аналогичной причине ... за исключениемчто существует только три термина, один из которых включает пару:
(5-1) + (2-1) + (6-2) =
(5-2) + (2-1) + (6-1) =
5 + 6 - 2*1
В зависимости от распределения набора чисел, вероятно, будут более прямые способы построения кольца с заданнымпрочность.Поскольку у нас еще нет определенного порядка в перестановках, у нас нет способа определить «следующий».Тем не менее, простым является отметить, что повороты и отражения данной перестановки будут иметь одинаковую силу:
(1,2,6,3,4,5)
(2,6,3,4,5,1)
(6,3,4,5,1,2)
...
(5,4,3,6,2,1)
(4,3,6,2,1,5)
...
Это заставляет вас двигаться?
Добавление по OPОбновления:
Доступно несколько тривиально инвариантных по силе свопов.Я уже упоминал две крайние пары (6-5) и (1-2).Вы также можете поменять соседние, последовательные числа: это добавляет (4-5) и (3-4) в приведенном выше примере.Из простых алгебраических свойств вы часто можете определить 2-элементный обмен или 3-элементное вращение (с учетом увеличения лексикографической позиции), которое генерирует следующую желаемую перестановку.Например:
(5, 6, 1, 3, 4, 2)
(5, 6, 1, 4, 2, 3) rotate 3, 4, 2
(5, 6, 1, 4, 3, 2) swap 2, 3
Однако в последовательности есть сбои, которые вам будет сложно найти таким образом.Например, прыжок для изменения первого или второго элемента не так чист:
(5, 6, 3, 1, 4, 2)
(5, 6, 3, 2, 4, 1) swap 1, 2 -- easy
(6, 1, 2, 4, 5, 3) wholesale rearrangement --
hard to see that this is the next strength=14
Мне кажется, что для их поиска потребуется набор алгебраических правил, которые бы находили простые движения и исключали недопустимые движения (например генерация 563421 до "оптовой перестановки" чуть выше).Однако следование этим правилам часто занимало бы на больше времени, чем прохождение всех перестановок.
Мне бы очень хотелось узнать, что я ошибаюсь в этом последнем пункте.: -)