Уважаемые коллеги и гуры :)
Есть всяческие задачки которые можно обобщить так:
- есть
Nлампочек; - есть
Mвыключателей; - каждый из выключателей переключает (!) состояние некоторых (известно каких) лампочек.
В начальном состоянии какие-то лампочки включены, какие-то выключены и спрашивается какое подмножество выключателей можно щёлкнуть чтобы перевести все лампочки в выключенное состояние.
Стало любопытно — как она решается? Ну кроме перебора (который видимо для 20 выключателей ещё ничего сработает, а дальше уже некруто). Если решение простое, то приветствуются тонкие намёки, чтоб всё-таки слегка подумать. Если сложное — то буду благодарен за ссылку.
Вообще это выглядит как система линейных уравнений на GF(2), но я пока не понял, приближает ли меня это к решению.
Это самая обычная система уравнений, Вам осталось только придумать матрицу:-)
Вы всё правильно сказали. GF(Z2) — это поле по модулю два, состояние всех лампочек — какой-то N-мерный вектор над этим полем. Каждое преобразование — это прибавление одного из M фиксированных векторов. Вас, фактически, спрашивают — Существуют ли a1, a2, ..., aM, такие что start + a1V1 + a2V2 + ... + aMVM = (00...00).
Это задача из линейной алгебры. Надо решить систему из N уравнений для каждого из разрядов в уравнении выше. Делается обычным методом Гаусса, который, к тому же. надо полем по модулю два дико приятно и просто писать на плюсах. Достаточно воспользоваться встроенными битсетами, у которых перегружен оператор
^, обозначающий пресловутое сложение по модулю два. К тому же, сразу получится быстро и оптимально засчёт битового сжатия.Дошло, спасибо :)
Непонятно почему, но мне упорно мерещилось что именно из-за GF(2) я не смогу решать систему "как обычную". Но Гаусс-то конечно работает!
Мне очень стыдно :D
Но у битсетов размер задается при компиляции, или есть способ делать это во время выполнения?
Ага, например, написать свой) А если серьезно, то этого сделать нельзя по крайней мере
std::bitsetне имеет такой функциональности. Можно писать на яве — там можно указывать произвольный размер, а в скорости сильно не уступает.Ещё вопрос связанный, чтоб не плодить постов:
Я вероятно туплю но не могу придумать "красивого" способа генерировать (псевдо)случайную линейно-независимую систему векторов в GF(2).
Т.е. можно генерить следующий случайный вектор после чего проверять не может ли он быть представлен линейной комбинацией уже нагенерённых... Но изящным это не выглядит :)
*Ну, прикидывал вариант — взять базис из N векторов и случайным образом выбирая A и B среди них добавлять B к A... Хм... Правильно ли я понимаю что линейная независимость будет гарантированно сохраняться?
А, ну вроде правильно. Извиняюсь, видимо утомительные выходные плохо влияют на умственные способности*
Да, более того ранк матрицы, если все рядом записать, будет сохраняться ибо это элементарное преобразование над столбцами матрицы(как в Гауссе)