Привет, форумяне!
Я здесь новичок; вроде бы наконец-то нашел приличный форум, куда можно запостить такое сообщение. Не судите строго, если я «не туда попал»…
При решении одной проблемы всплыла следующая задачка. Постановка задачи такова:
Имеется вектор А = (a1, a2, … aN), причем некоторые из его компонент могут совпадать. Над вектором А определена операция транспозиции А -> Transpose(А), т.е. перестановка его компонент. Условие равенства векторов обычное, т.е. векторы равны при равенстве всех соответствующих компонент. Соответственно если в исходном векторе есть равные компоненты, то после перестановки именно этих компонент он не меняется.
Задан линейный функционал: F(А) = (А, W) (скалярное произведение), где W=(W1, W2, … WN) — другой фиксированный вектор.
Найти число разных транспозиций вектора А, таких, чтобы F(Transpose(А)) отличался от F(А) не более чем на заданное число Eps. Вообще говоря, Eps может оказаться и равным нулю, т.е. в этом случае должно соблюдаться точное равенство значений функционала на группе транспозиций.
Вообще говоря, задача комбинаторная, так как для точного решения придется перебрать N! векторов. Понятно, что уже при N>10 вариантов получается много. Мне же достаточно только быстро оценить решение с точностью порядка процентов, можно даже десятков процентов — для N~50 или даже больше.
В принципе компоненты векторов А и W можно задать как натуральные числа, но как это может помочь решению, пока не представляю.
Я пока даже не знаю, где искать алгоритм решения этой задачи, хоть в какой области-то? Буду рад конструктивным советам, не слишком сложно воплощаемым в компутерный код. Спасибо.
// Тему переместил(а) decvar из форума «Общий по программированию».
// Тему переместил(а) Longobard из форума «Помощь за деньги».
Последние комментарии
-
OlegL, 17 декабря в 15:00 →
Перекличка
21
-
REDkiy, 8 июня 2023 года в 9:09 →
Как «замокать» файл для юниттеста в Python?
2
-
fhunter, 29 ноября 2022 года в 2:09 →
Проблема с NO_PUBKEY: как получить GPG-ключ и добавить его в базу apt?
6
-
Иванн, 9 апреля 2022 года в 8:31 →
Ассоциация РАСПО провела первое учредительное собрание
1
-
Kiri11.ADV1, 7 марта 2021 года в 12:01 →
Логи catalina.out в TomCat 9 в формате JSON
1
ecobeing.ru
сессия на носу, а лабы не сданы?
Нее, Хитрый хрен, мое время лаб уже давным-давно прошло. Глянь в мой профиль — узнаешь мой возраст. Кстати, мне твоя подпись очень нравится. И движок здешнего форума мне очень по душе: быстрый такой, без ненужных прибамбасов…
Ладно, я не обидчивый, пусть «помощь за деньги». Открою маленький секрет: я пытаюсь сделать приличную систему для торговли на FOREX. Но мне уже порядком надоело комбинировать крайне слабо обоснованные инструменты теханализа в расчете на авось; хочется чего-то математически обоснованного. Наткнулся на мысль — вот и получилась такая задачка. Искать ответ на трейдерских форумах — неэффективно, а форумов по комбинаторике ни одного приличного так и не нашел. А задачка-то — на стыке комбинаторики и кодирования. Так что я вроде как все же по адресу…
Ну дык как, сколько бабла ты хочешь за совет по поводу того, где искать ответ? Только скажу сразу: ответ «перечислительная комбинаторика» я уже знаю. Но для этого надо проштудировать книжку Стенли, а она жутко большая и вумная. А вот интересно мне получить сразу алгорифм (пусть просто краткое описание или блок-схему, так лучше даже) — или просто асимптотическую формулу…
Спасибо.
В общем-то было очевидно, что задача не лабная. Извращенная она, явно из реальной жизни. Что тут сказать? В принципе, можно прикинуть геометрически. Перестановки компонент отображают данный N-вектор в другие вектора, концы которых лежат на N-мерной сфере. Фиксируем вектор W и смотрим на функционал. Его минимальное значение есть ноль, когда вектор-перестановка перпендикулярен W, а максимум равен произведению длин W и оригинального вектора. Это дает верхнюю границу разумного эпсилон…
В общем, есть о чем подумать. Но скорее всего, придется тупо перебирать, накапливать ошибку и сравнивать с эпсилон. Если ошибка превысила эпсилон, рвать цикл и переходить к другой перестановке.
Я бы перенес тему обратно в Программирование, но я тут не модер. ;)
Good Luck,
UT
Mathemat приношу свои извинения, был неправ.
Большое спасибо за ответы.
2 Uncle Theodore: Ну если сделать Eps в точности равным нулю, а компоненты векторов целочисленными, то задачка становится намного красивей, уже не похожа на сильно извращенную и вполне может рассматриваться как достойная для мозгов профессоров комбинаторики. Да, геометрическая интертрепация задачки тут бросается в глаза, хотя гиперсфера, пожалуй, избыточна. Ну а тупой перебор векторов в 50-мерном пространстве (вполне реально для FOREX) дает 50! ~ 3*10^64 вариантов. Эх, долго перебирать придется, помру я ко времени решения задачи…
2 Longobard: да ладно, чего уж там, ничего обидного не было. Я и сам вспоминаю лабное и сессионное время как самое счастливое в жизни…