Работа с многомерным массивом

Рейтинг: 2Ответов: 1Опубликовано: 18.05.2011

Здравствуйте! Мне нужна подсказка для решения следующей задачи: Имеется так называемое множество, которое состоит из замкнутых и незамкнутых множеств, где 1 является весом. Т.е. "a" имеет вес 1, b имеет 3 и т.п.

a 0001000
b 1101000
c 0011010
d 1000100
e 0100001

Замкнутые множества это например ab или ad, или be, или abc. Т.е. это строки в столбцах которых встречаются 1. А где они не встречаются, то множества являются считаются незамкнутыми. Мне необходимо сравнить каждую строку между собой и другими строками и вывести все замкнутые и незамкнутые множества.

c# алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 5Принят

В принципе, если у Вас количество символов (0 и 1) не больше 63, то можно использовать битовые операции для решения Вашей задачи.

Это будет выглядить примерно так (алгоритм для поиска ПАР замкнутых и не замкнутых множеств, небольшие изменения можно сделать для общего случая): 

for (int j=1; j < N; j++)
    for (int k=j+1; k <= N; k++)
        if (a[j] & a[k] != 0) //есть хотя бы один общий бит равный 1
            //множества с индексами j, k замкнуты
        else
            //множества с индексами j, k НЕ замкнуты

N - количество множеств, a - массив, хранящий множества.

Можно, конечно, круче. Построить бинарное дерево - бор. Вершины содержат числа. Корень - пустая вершина. Остальные вершины - определённый путь от корня, т.е. множество левых и правых сыновей каждой вершины пути, и, если мы идём к левому сыну, то тем самым "кодируем" нулевой бит, иначе - единичный, а когда прошлись по всем цифрам множества, т. е. пришли в какую-нибудь вершину, записываем в неё +1. Т. е. в ней хранится число "закодированных" множеств. Теперь НАСТОЯТЕЛЬНО рекоммендую нарисовать получившийся бор из примера. Рассмотрим вершину, в которой записано число > 0 и в пути к ней мы хотя бы раз пошли по правому ребру. Понятно, что все её потомки - замкнутые с ней множества. Кроме этого, необходимо просмотреть и другие вершины, находящиеся на том же уровне и ниже его в других поддеревьях. Понятно, что асимптотически выгодней подыматься в нашем боре от листьев к корню и попутно считая количество замкнутых множеств. Тогда количество не замкнутых можно подсчитать, отнявши от всего возможного количества комбинаций множеств число замкнутых.