Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / поиск множеств содержащих одинаковые элементы. / 9 сообщений из 9, страница 1 из 1
15.05.2011, 14:57
    #37261282
scymaks
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
Добрый день!

Что-то не могу придумать достаточно эффективный алгоритм для нахождения множеств содержащих одинаковые числа,
ну например на матрице

Код: plaintext
1.
2.
3.
 2   4   4   4   4   2 
 2   3   4   2   2   2  
 4   5   6   6   3   4 

хочу получить

множества:

[fix]
2 4 4 4 4 2
2 2 2 2 66
[/fix]

в виде списка их координат:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
( 0 ,  0 )
( 1 ,  0 )

( 0 ,  1 )
( 0 ,  2 )
( 0 ,  3 )
( 0 ,  4 )

( 0 ,  5 )
( 1 ,  3 )
( 1 ,  4 )
( 1 ,  5 )

( 2 ,  2 )
( 2 ,  3 )

пытался придумать что-то типа dfs:
( псевдокод )

[src]
void dfs(int i, int j, list L)
{
visited[i][j] = true;
list.add( i, j );
if ( i + 1 < height && !visited[i][j] && matrix[i][j] == matrix[i+1][j]) {
dfs( i + 1, j );
}

// аналогично с
// ( i - 1, j ),
// ( i, j - 1 ),
// ( i, j + 1 )
}
[src]

но мне кажется есть более эффективный способ! Какие идеи ?
...
Рейтинг: 0 / 0
15.05.2011, 15:11
    #37261298
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
scymaks,

Можно переформулировать задание?
Скажем, на входе - матрица MxN целых чисел, из которых некоторые повторяются. Что должно быть на выходе?
...
Рейтинг: 0 / 0
15.05.2011, 15:52
    #37261330
scymaks
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
На выходе нужно получить список множеств, где каждое множество состоит из пар вида (x,y) где x и y это индексы элемента

ну то есть например на матрице

[fix]
2 1 2
1 1 2
[/fix]

нужно получить на выходе

Код: plaintext
1.
2.
3.
M1 = { ( 0 ,  0 ) } // множество содержащее  2 
M2 = { ( 0 ,  1 ), ( 1 ,  0 ), ( 1 ,  1 ) } // множество содержащее  1 
M3 = { ( 0 ,  2 ), ( 1 ,  2 ) } // еще одно множество содержащее  2 

Вот...
...
Рейтинг: 0 / 0
15.05.2011, 17:27
    #37261419
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
scymaks,

Что значит - "ещё одно множество, содержащее 2"? Почему бы тогда тупо не выделить каждый элемент в индивидуальное множество и вывести M*N множеств по одному элементу?
...
Рейтинг: 0 / 0
15.05.2011, 17:36
    #37261427
scymaks
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
не понял, объяснитесь
...
Рейтинг: 0 / 0
15.05.2011, 18:03
    #37261453
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
scymaksНа выходе нужно получить список множеств, где каждое множество состоит из пар вида (x,y) где x и y это индексы элемента

ну то есть например на матрице

Код: plaintext
1.
2 1 2
1 1 2

нужно получить на выходе

Код: plaintext
1.
2.
3.
M1 = { ( 0 ,  0 ) } // множество содержащее  2 
M2 = { ( 0 ,  1 ), ( 1 ,  0 ), ( 1 ,  1 ) } // множество содержащее  1 
M3 = { ( 0 ,  2 ), ( 1 ,  2 ) } // еще одно множество содержащее  2 

Вот...
Чем плох выход
M1={ (0,0) },
M2={ (0,1) },
M3={ (0,2) },
M4={ (1,0) },
M5={ (1,1) },
M6={ (1,2) } ?

Если же Вам нужно выделить связные области, заполненные одинаковыми числами, то почему в первом примере во втором множестве нет (1,2)?
...
Рейтинг: 0 / 0
15.05.2011, 19:03
    #37261516
scymaks
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
=) потому что опечатался ) и да, нужно найти связные области :) вы знаете как это сделать?
...
Рейтинг: 0 / 0
15.05.2011, 21:21
    #37261623
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
scymaks,

Известный мне алгоритм (названия не помню) использует матрицу-спутника: заводится дублирующая матрица того же размера, после чего примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
//Номер класса инициализируем единицей
//Для каждой строки
    //Для каждого элемента в строке
        //Помечаем текущий элемент в матрице-спутнике нулём
        //Если предыдущий элемент в строке имеет то же значение
            //Если к тому же предыдущий элемент в матрице-спутнике помечен не нулём
                //Пометить текущий элемент в спутнике тем же значением
            //Иначе же имеем новый класс:
                //Присваиваем ячейкам текущего и предыдущего элементов в спутнике "номер класса"
                //Увеличиваем "номер класса" на единицу
        //Теперь смотрим на элемент вверху - если он имеет то же значение
            //Если он помечен нулём
                //Если наш элемент помечен нулём
                    //Присваиваем верхнему и текущему элементам в спутнике "номер класса"
                    //Увеличиваем "номер класса" на единицу
                //Иначе же
                    //Присваиваем верхнему элементу номер класса текущего элемента
            //Если элемент вверху уже принадлежит другому классу
                //Если текущий элемент помечен нулём
                    //Помечаем текущий элемент значением верхнего
                //Иначе - имеем слияние двух классов
                    //Помечаем в словаре, что класс текущего элемента эквивалентен классу верхнего
                    //(или перенумеруем один из двух классов по алгоритму liquid fill)
В итоге имеем матрицу-спутник, в которой пронумерованы связные области. Если использовался словарь, можно ещё раз пройти по спутнику, после чего не проблема разбросать элементы матрицы по классам.
...
Рейтинг: 0 / 0
15.05.2011, 21:46
    #37261648
scymaks
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
поиск множеств содержащих одинаковые элементы.
оки, возьму за идею, буду курить :) Спасибо!
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / поиск множеств содержащих одинаковые элементы. / 9 сообщений из 9, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]