powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм выделения общих свойств объектов
7 сообщений из 7, страница 1 из 1
Алгоритм выделения общих свойств объектов
    #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
Алгоритм выделения общих свойств объектов
    #37166900
Naf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hellium,
по-моему требование противоречиво:
Код: plaintext
1.
2.
['A','B']
['B','C']
['C','D']
как их разбить?
...
Рейтинг: 0 / 0
Алгоритм выделения общих свойств объектов
    #37166908
hellium
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Naf,

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

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

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

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

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


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