Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм выделения общих свойств объектов / 7 сообщений из 7, страница 1 из 1
15.03.2011, 08:09
    #37164913
hellium
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
Есть прикладная задача, есть cамописное решение.

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

Есть идеи по уменьшению трудоемкости?

Есть идеи, как можно элегантно решить такую задачу на sql? У меня получилось только через процедуру, серий запросов + циклом.

Постановка задачи
Есть набор объектов, у каждого из которых задан набор свойств:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
my $objects = (
	['A', 'B'],          # первый объект, свойства A, B
	['B', 'E'],	     # второй объект, свойства B, E
	['E', 'A', 'C'],    
	['G', 'F', 'H'],
	['F', 'G'],
	['Z'],
	['Z'],               # Один и тот же набор свойств может встречаться в нескольких объектах
);
Требуется выделить группы свойств, такие что:
1. Один объект может входить только в одну группу.
2. Если 2 разных объекта содержат одинаковое свойство, они должны быть объединены в одну и ту же группу.
3. Если у двух разных объектов нет общего свойства, они должны быть в разных группах.

Т.е. в примере будет 3 группы (перечислены свойства в каждой группе):
Код: plaintext
1.
$groups = ( [A, B, E, C], [G, F, H], [Z] ); 

На практике еще добавляются "начальные" группы и разбор конфликтов, если объект попадает в разные "начальные" группы, но пока для простоты все эти моменты пропустил.

Алгоритм
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
#!/usr/bin/perl -w
use strict;
use warnings;
use Data::Dumper;

my @objects = (
	['A', 'B'],
	['B', 'E'],
	['E', 'A', 'C'],
	['G', 'F', 'H'],
	['Z'],
	['Z'],
);

# список групп 
my @groups = ();
 
# вспомогательный хэш для ускорения поиска (свойство => ссылка на группу)
my %feature2group;

for my $object (@objects) {
    # ищем группу, которой принадлежит объект
    my $group;
    for my $property (@$object) {
        last if $group = $feature2group{$property};
    }

    # если не найдено ни одной группы, создаем новую группу. 
    unless ($group) {
        $group = {};
        push @groups, $group;
    } 

    # добавляем в группу из объекта все отсутствующие в группе свойства
    for my $property ( @$object ) {
        unless (exists $group->{$property}) {
            $group->{$property} =  1 ;
            $feature2group{$property} = $group;
        };
    }
}
print Dumper \@groups;
...
Рейтинг: 0 / 0
16.03.2011, 09:19
    #37166900
Naf
Naf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
hellium,
по-моему требование противоречиво:
Код: plaintext
1.
2.
['A','B']
['B','C']
['C','D']
как их разбить?
...
Рейтинг: 0 / 0
16.03.2011, 09:26
    #37166908
hellium
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
Naf,

Противоречия нет, это будет одна группа (у 1 и 2 объекта общее свойство B, у 2 и 3 - общее свойство C)
...
Рейтинг: 0 / 0
16.03.2011, 09:50
    #37166940
Naf
Naf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
helliumNaf,

Противоречия нет, это будет одна группа (у 1 и 2 объекта общее свойство B, у 2 и 3 - общее свойство C)
а как же "3. Если у двух разных объектов нет общего свойства, они должны быть в разных группах. "?
...
Рейтинг: 0 / 0
16.03.2011, 10:21
    #37166984
hellium
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
Naf,

Да, это я неаккуратно написал :(. Попробую переформулировать:

1. Один объект может входить только в одну группу.
2. Если 2 разных объекта содержат одинаковое свойство, они должны быть объединены в одну и ту же группу,
3. При "транзитивной" похожести (например, [A,B], [B,C], [C,D]), объекты должны быть в одной и той же группе.
4. Если у двух разных объектов нет общего свойства (за исключением случаев "транзитивной" похожести), они должны быть в разных группах.
...
Рейтинг: 0 / 0
16.03.2011, 14:16
    #37167688
rt321
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
Это настолько элементарная задача (выделение связных компонент графа), что я пас
...
Рейтинг: 0 / 0
16.03.2011, 15:03
    #37167882
hellium
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм выделения общих свойств объектов
rt321,

ну вот, хоть название задачи подсказал )
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм выделения общих свойств объектов / 7 сообщений из 7, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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