Правила этой проблемы довольно специфичны, потому что я на самом деле смотрю на подмножество GLn, где векторы строк и столбцов должны иметь определенную форму (назовите эти векторы valid - примеры ниже), поэтому, пожалуйста, потерпите меня. Вот правила:
Вы можете случайным образом выбрать правильный ненулевой вектор длины n.
Учитывая действительные векторы v1, v2, ..., vk, вы можете определить, являются ли формируемые ими неполные столбцы префиксами действительных векторов (например, встречается ли [v1_1 v2_1 ... vk_1] в качестве первых k записей действительного вектора), используя функцию isPrefix.
Учитывая действительные векторы v1, v2, ..., vk, вы можете определить, являются ли они линейно зависимыми, используя функцию areIndependent.
Целью является выборка из этого подмножества GLn равномерно случайным образом. Вот наивное решение, которое терпит неудачу:
Step 1: Select a valid v1 uniformly at random.
If isPrefix(v1) then Go to Step 2.
Otherwise repeat Step 1.
Step 2: Select a valid v2 uniformly at random.
If areIndependent(v1,v2) & isPrefix(v1,v2), then go to Step 3.
Otherwise, repeat Step 2.
...
Step n: Select a valid vn uniformly at random.
If areIndependent(v1,v2,...,vn) & isPrefix(v1,v2,...,vn), then END.
Otherwise, repeat Step n.
Проблема с этим потенциальным решением состоит в том, что он может застрять в бесконечном цикле в не слишком маловероятном событии, которое areIndependent(v1,v2,...,vk) & isPrefix(v1,v2,...,vk) правильно возвращает TRUE, но нет способа завершить этот k-кортеж для линейно независимый действительный n-кортеж. Типичным примером этого является случай, когда k=n-1 и существует уникальный действительный вектор vn, такой, что isPrefix(v1,v2,...,vn) равен TRUE, но этот вектор не независимо от предыдущих n-1 векторов.
Поэтому мне нужно каким-то образом добавить, чтобы сделать резервную копию шага или двух, когда я нахожусь в этом цикле, но я не обязательно знаю, когда я в нем. Я ищу решение по следующим направлениям: Если шаг k не пройден f(k) раз для некоторой явной функции f, которая может зависеть от распределения действительных векторов, то вернитесь к шагу k-1 (или даже дальше, каким-то явным образом).
Любые предложения, комментарии, ссылки и т. Д. Будет принята с благодарностью! Спасибо!
Примеры:
Я на самом деле ищу общий справочник или руководство для того, как продолжить выборку. У меня есть несколько примеров допустимых векторов, по которым я хотел бы сделать это, и для меня более полезно иметь возможность сделать это самостоятельно в конечном счете, чем перечислять каждый пример и иметь решения хеш-сообщества сообщества SO. Однако, чтобы быть конкретными и дать представление о трудностях, приведенных ниже, приведем один пример:
Матрицы знаковых переменных : вектор действителен, если все его записи равны 0, -1, 1, ненулевые записи чередуются между 1 и -1, а сумма записей равна 1. Например, каждая матрица перестановок будет состоять из действительных векторов, а также следующего:
0 1 0
1 -1 1
0 1 0
Отдельные записи : вектор действителен, если он имеет разные записи. Это особенно раздражает, потому что условие применяется как к строкам, так и к столбцам.
Еще раз спасибо всем, кто смотрел на это!