nixp.ru v3.0

22 октября 2017,
воскресенье,
05:55:16 MSK

DevOps с компанией «Флант»
Mathemat написал 20 декабря 2006 года в 13:16 (483 просмотра) Ведет себя как мужчина; открыл 1 тему в форуме, оставил 2 комментария на сайте.

Привет, форумяне!

Я здесь новичок; вроде бы наконец-то нашел приличный форум, куда можно запостить такое сообщение. Не судите строго, если я «не туда попал»…

При решении одной проблемы всплыла следующая задачка. Постановка задачи такова:

Имеется вектор А = (a1, a2, … aN), причем некоторые из его компонент могут совпадать. Над вектором А определена операция транспозиции А -> Transpose(А), т.е. перестановка его компонент. Условие равенства векторов обычное, т.е. векторы равны при равенстве всех соответствующих компонент. Соответственно если в исходном векторе есть равные компоненты, то после перестановки именно этих компонент он не меняется.

Задан линейный функционал: F(А) = (А, W) (скалярное произведение), где W=(W1, W2, … WN) — другой фиксированный вектор.

Найти число разных транспозиций вектора А, таких, чтобы F(Transpose(А)) отличался от F(А) не более чем на заданное число Eps. Вообще говоря, Eps может оказаться и равным нулю, т.е. в этом случае должно соблюдаться точное равенство значений функционала на группе транспозиций.

Вообще говоря, задача комбинаторная, так как для точного решения придется перебрать N! векторов. Понятно, что уже при N>10 вариантов получается много. Мне же достаточно только быстро оценить решение с точностью порядка процентов, можно даже десятков процентов — для N~50 или даже больше.

В принципе компоненты векторов А и W можно задать как натуральные числа, но как это может помочь решению, пока не представляю.

Я пока даже не знаю, где искать алгоритм решения этой задачи, хоть в какой области-то? Буду рад конструктивным советам, не слишком сложно воплощаемым в компутерный код. Спасибо.

// Тему переместил(а) decvar из форума «Общий по программированию».

// Тему переместил(а) Longobard из форума «Помощь за деньги».

Longobard

сессия на носу, а лабы не сданы?

Mathemat

Нее, Хитрый хрен, мое время лаб уже давным-давно прошло. Глянь в мой профиль — узнаешь мой возраст. Кстати, мне твоя подпись очень нравится. И движок здешнего форума мне очень по душе: быстрый такой, без ненужных прибамбасов…

Ладно, я не обидчивый, пусть «помощь за деньги». Открою маленький секрет: я пытаюсь сделать приличную систему для торговли на FOREX. Но мне уже порядком надоело комбинировать крайне слабо обоснованные инструменты теханализа в расчете на авось; хочется чего-то математически обоснованного. Наткнулся на мысль — вот и получилась такая задачка. Искать ответ на трейдерских форумах — неэффективно, а форумов по комбинаторике ни одного приличного так и не нашел. А задачка-то — на стыке комбинаторики и кодирования. Так что я вроде как все же по адресу…

Ну дык как, сколько бабла ты хочешь за совет по поводу того, где искать ответ? Только скажу сразу: ответ «перечислительная комбинаторика» я уже знаю. Но для этого надо проштудировать книжку Стенли, а она жутко большая и вумная. А вот интересно мне получить сразу алгорифм (пусть просто краткое описание или блок-схему, так лучше даже) — или просто асимптотическую формулу…

Спасибо.

Uncle Theodore

В общем-то было очевидно, что задача не лабная. Извращенная она, явно из реальной жизни. Что тут сказать? В принципе, можно прикинуть геометрически. Перестановки компонент отображают данный N-вектор в другие вектора, концы которых лежат на N-мерной сфере. Фиксируем вектор W и смотрим на функционал. Его минимальное значение есть ноль, когда вектор-перестановка перпендикулярен W, а максимум равен произведению длин W и оригинального вектора. Это дает верхнюю границу разумного эпсилон…

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

Я бы перенес тему обратно в Программирование, но я тут не модер. ;)

Good Luck,

UT

Longobard

Mathemat приношу свои извинения, был неправ.

Mathemat

Большое спасибо за ответы.

2 Uncle Theodore: Ну если сделать Eps в точности равным нулю, а компоненты векторов целочисленными, то задачка становится намного красивей, уже не похожа на сильно извращенную и вполне может рассматриваться как достойная для мозгов профессоров комбинаторики. Да, геометрическая интертрепация задачки тут бросается в глаза, хотя гиперсфера, пожалуй, избыточна. Ну а тупой перебор векторов в 50-мерном пространстве (вполне реально для FOREX) дает 50! ~ 3*10^64 вариантов. Эх, долго перебирать придется, помру я ко времени решения задачи…

2 Longobard: да ладно, чего уж там, ничего обидного не было. Я и сам вспоминаю лабное и сессионное время как самое счастливое в жизни…