Последовательности попарно неортогональных восьмимерных векторов, заданных на множестве {0, 1, -1} и содержащих ровно 4 нуля.

Упорядоченный список из 907 найденных упорядоченных списков векторов

Определения.

Два вектора X = (x1, x2, x3, x4, x5, x6, x7, x8) и Y = (y1, y2, y3, y4, y5, y6, y7, y8) являются неортогональными, если их скалярное произведение не равно нулю:

X Y = x1 y1 + x2 y2 + x3 y3 + x4 y4 + x5 y5 + x6 y6 + x7 y7 + x8 y8 ≠ 0

Мощностью конечного множества является количество элементов в этом множестве.

Задача.

Существуют ли множества попарно неортогональных векторов , заданных на множестве {0, 1, -1} и содержащих ровно 4 нуля, мощности 81? Каково количество различных множеств попарно неортогональных векторов , заданных на множестве {0, 1, -1} и содержащих ровно 4 нуля, мощности 80?

∀ i: xi ∈ {0, 1, -1}, yi ∈ {0, 1, -1}, x и y содержат ровно 4 нуля

Мне показалась интересной задача из первой лекции курса Райгородский Андрей Михайлович. Основы комбинаторики и теории чисел. Там предлагалось найти последовательности попарно неортогональных векторов , заданных на множестве {0, 1, -1} и содержащих ровно 4 нуля, мощности 80 , а также говорилось, что неизвестны такие последовательности мощности 81. К сожалению, оказалось возможным при помощи компьютера найти только некоторые последоваьельности мощности 80, но не удалось найти ответ ни на вопрос, существуют ли последоваельности длины 81, ни на вопрос о количестве последовательностей длины 80.

Число всех векторов в массиве vectorsGlobal равно числу сочетаний из 8 по 4, умноженному на число размещений с повторениями из 2 по 4, то есть равно 35*16 = 1120. Эти вектора нумеруются в массиве vectorsGlobal от 0 до 1119.

Алгоритм нахождения некоторых множеств попарно неортогональных векторов , заданных на множестве {0, 1, -1}, мощности 80.

К сожалению, данный алгоритм находит только некоторые множества мощности 80 и не дает ответ ни на первый, ни на второй вопрос задачи.

Алгоритм получения некоторых (не всех) перестановок из 1120 неотрицательных чисед от 0 до 1119

Функция sequence(begin, delta) зависит от двух параметров: от начального элемента begin (begin = {0, 1, 2, … , 1119}) и от шага delta (delta = {1, 2, …, 1119}). Пока число элементов в массиве bypass не достигнет 1120 в массив bypass добавляется элемент num, который вычисляется следующим образом: изначально num = initialElem = begin. Затем к num прибавляется delta и берется остаток от деления суммы num + delta на 1120 до тех пор, пока это значение не совпадет с начальным элементом initialElem. Если, например, шаг delta является делителем числа 1120, и в других случаях, когда очередной остаток от деления на 1120 суммы num + delta совпадет с initialElem, и при этом все 1120 номеров не будут добавлены в массив, то есть длина массива bypass окажется меньше 1120, то initialElem увеличивается на единицу и внутренний цикл, начиная уже от элемента begin + 1 повторяется снова. Этот внутренний цикл будет повторяться k раз, начиная от begin + 1, begin + 2, … , begin + k до тех пор, пока число элементов в массиве bypass не станет равно 1120.

Всего таким способом можно получить 1120*1119 = 1253280 различных упорядоченных списков из 1120 элементов, что, конечно, намного меньше числа перестановок из 1120 элементов, равного 1120!

некоторые перестановки из 1200 элементов

Алгоритм без сортировки.

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

Начиная от 0 до 1119 номера вектора включительно с шагом от 1 до 1119 включительно перебираются все 1120 номеров векторов в определенном порядке. То есть для каждого из 1253280 массивов bypass , для всех i от 0 до 1119, если элемент массива векторов vectorsGlobal с номером bypass[i] не является ортогональным ни одному элементу массива векторов vectorsGlobal с номерами, находящимися в массиве NoIndexOrt , номер bypass[i] добавляется в массив NoIndexOrt.

Среди 1253280 последовательностей попарно неортогональных векторов различной мощности , заданных на множестве {0, 1, -1} и содержащих ровно 4 нуля, программа найдет 2725 последовательностей мощности 80. Последовательностей длины 81 программа не находит, но это не доказывает того, что таких последовательностей нет.

Алгоритм с сортировкой по возрастанию.

Так как порядок векторов в каждом законченном решении мощности 80 не важен, то все массивы NoIndexOrt можно упорядочить по возрастанию и рассматривать только различные упорядоченные по возрастанию множества из 80 попарно неортогональных векторов, заданных на множестве {0, 1, -1} и содержащих ровно 4 нуля. Тогда число решений сокращается от 2725 до 907

Неупорядоченный список из 907 найденных упорядоченных списков векторов мощности 80

Для удобства двумерный массив упорядоченных списков можно также отсортировать.

Упорядоченный список из 907 найденных упорядоченных списков векторов мощности 80

Алгоритм поиска всех решений.

Массивы индексов IndexGlobal содержит номера тех векторов массива vectorsGlobal, которые попарно не перпендкулярны, заданы на множестве {0, 1, -1} и содержат ровно 4 нуля.

До тех пор, пока существует вектор, удовлетворяющий условию задачи с номером first в пределах от числа, на единицу больше значения последнего элемента массива индексов IndexGlobal до 1119 включительно, его номер first добавляется к массиву индексов IndexGlobal.

Как только к массиву индексов больше нечего добавить, ибо все вектора с номерами, которые больше последнего элемента массива IndexGlobal, ортогональны какому-либо вектору с номером из массива IndexGlobal, из массива индексов IndexGlobal2 удаляется последний элемент до тех пор, пока не найдется такой вектор с номером second на единицу больше удаляемого элемента , и найденный номер second добавляется в конец укороченного массива индекса IndexGlobal2. Другими словами, последний элемент массива IndexGlobal либо заменяется на большее значение, если такая замена возможна, либо удаляется. То есть, последний элемент массива IndexGlobal удаляется до тех пор, пока его нельзя заменить на какой-либо больший, чем он, элемент, удовлетворяющий условию задачи.

алгоритма поиска неортогональных векторов алгоритм проверки векторов на ортогональность

Другой алгоритм получения всех решений мощности 80 и мощности 81 – получить все сочетания из 1200 по 80, и все сочетания из 1200 по 81, и проверить, являются ли попарно ортогональными все вектора в этих сочетаниях, подсчитав таким способом число решений мощности 80 и выяснив, существуют ли решения мощности 81. Однако, число сочетаний из 1200 по 80 – громадное число из 127 цифр, в чем можно убедиться на странице вычисления числа сочетаний из n по k и самих сочетаний из n по k. Скорее всего, компьютеру снова потребуются триллионы триллионов лет для решения такой задачи.

На главную страницу