Вобщем на входе есть матрица, например вот такая:


0 1 0 0 1
0 0 0 1 0
1 0 0 0 0
1 0 0 0 1
0 0 0 0 1

на выходе мне нужно получить все возможные вектора, содержащие номера столбцов с единицами.

т.е. в данном случае это будут:

(2 4 1 1 5),  (5 4 1 1 5),  (2 4 1 5 5),  (5 4 1 5 5)

для этого я написал рекурсию, но она почемуто неработает
вот сам код (алгоритм) рекурсии (на паскале)



Может рекурсия не самый лучшый выход для решения этой задачи?

Это сообщение отредактировал(а) TP@MB@Y - 29.10.2006, 17:24

Попробую перефразировать задачу.
Нужны все варианты этой матрицы чтобы по строкам было не более одной единицы.

А в матрице только нули и единицы? Если да, то стоит проссумировать строки. Если реузльтат 1 - это та строка, которая подходит.

anwe,  ну это понятно. но мне надо все варианты матриц, в которых не более одной единицы на строке.

Что-то я нифигачего не понимаю   
Что значит все возможные? Столбец либо содержит 1 либо нет  

откуда получился 1 столбец? И почему он дважды?
P.S. Можно поподробнее? Как для тупого  (но не сильно   )

ivashkanet,  вобщем если перейти от абстракции, то я вычисляю все возможные аппликатуры аккорда(на интервале 5 ладов).
Т.е. есть шесть струн (строк) и пять столбцов(ладов). Аккорд состоит из нот. В этой матрице содержится элементы - ноль если нота не принадлежит аккорду и 1 если принадлежит. Вот мне и надо перебрать все возможные варианты ;)

Думаю теепрь все встало на свои места. Какие предложения?

TP@MB@Y, ну ты прикинь. Это же 5^6=15625 вариантов.
Может лучше на гитаре.   Ведь все равно аккорды и 5 нот встречаются редко, к тому же, если у тебя две или более нот стоят рядом, как то до-ре(-ми), то получается совсем не красиво.  

anwe,  я же пример привел в начале  там всего 4 варианта для данной матрицы.

вот дана матрица такая - 

0 1 0 0 1
0 0 0 1 0
1 0 0 0 0
1 0 0 0 1
0 0 0 0 1

нужно на выходе получить такие матрицы - 

0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1


0 0 0 0 1
0 0 0 1 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1


0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 1


0 0 0 0 1
0 0 0 1 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 1



вот я и хочу спросить оптимальный алгоритм как эти варианты перебрать.
написал рекурсивную функцию. но оа где то не срабатывает.

TP@MB@Y, 
рекурсия здесь  не нужна. Она была бы нужна, если необходимо было бы выбрать такое расположение, чтобы в СТОЛБЦАХ не было повторений (как в задаче о 8 ферзях)
здесь же очевидное решение.
6 циклов по каждой строке (струне)
Но если очень уж хочется рекурсией, да и мало ли, ты для пианино программу захочешь разработать  
Идея: нашли первую ненулевую позицию в струне - идем дальше вниз и повторяем все то же самое


В векторе res содержатся номера столбцов(лады) для каждой струны.
P.S. Тебе еще имхо нужно будет продумать ситуацию про открытые струны
P.P.S. Есть отличнейшая программулина - Guitar Pro называется. Там это все есть + куча табулатур

Кстати, примеры у тебя какие то странные, ты говоришь про матрицу 6 на 5, а примеры все 5х5

Это сообщение отредактировал(а) Kuvaldis - 1.11.2006, 22:30

Kuvaldis,  БОЛЬШУЩЕЕ СПАСИБО! 
Просто я забыл как правильно рекурсии писать)
Вся прелесть рекурсий, в их минимализме 

Я воспользовался Вашей функцией, немного поправв ее под себя. Спасибо. Работает.

Про гитар про я знаю конечно же. Но программу пишу спецально для себя, с узконаправлеными свойствами. Гитарпро слишком перегружена имхо.