ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Нахождение эксклюзивных пар
25 сообщений из 27, страница 1 из 2
  1  все
Нахождение эксклюзивных пар
    #40026978
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
Наткнулся на интересную задачку, навеяно вопросом тут: 22245400

Из заданного множества пар, выбрать эксклюзивные по заданному критерию.

Например, Адам, Джон, Игорь и Карл подружились с Евой, Сю, Лиа и Кэт.
В таблице представлены взаимные симпатии (колонки М,Ж и степень симпатии)

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
with pairs(m,f,s) as (
  select 'Adam', 'Eva', 1 from dual union all
  select 'Adam', 'Sue', 1 from dual union all
  select 'John', 'Eva', 2 from dual union all
  select 'Carl', 'Eva', 3 from dual union all
  select 'Igor', 'Sue', 2 from dual union all
  select 'John', 'Lea', 2 from dual union all
  select 'John', 'Kat', 1 from dual union all
--  select 'John', 'Igor', 9 from dual union all
  select 'Carl', 'Kat', 1 from dual
)



Задача: поженить как можно больше этих людей по критерию максимального общего счастья (арифметической суммы симпатий).

Закомментированная строчка представляет усложненный вариант задачи.
...
Рейтинг: 0 / 0
11.12.2020, 17:49
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40026984
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
Задачу коммивояжера тут уже решали, воспользуйтесь поиском.
И это... Нафиг такие усложнения, у меня, быть может, фобия.
...
Рейтинг: 0 / 0
11.12.2020, 18:02
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40026991
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
НеофитSQL,

какая-то нетолерантная задача.
мнение Евы в этом маскулинном мире полностью игнорируется.
Видимо, у неё нет шансов отказаться, как, вероятно, и у несчастного Igor-a...

Вы точно из Маями ?
...
Рейтинг: 0 / 0
11.12.2020, 18:15
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027001
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
andrey_anonymous
Задачу коммивояжера тут уже решали, воспользуйтесь поиском.
И это... Нафиг такие усложнения, у меня, быть может, фобия.


Вы зря отмахиваетесь, не разобравшись.

Задача коммивояжера - NP. Эта задача - P.

Разный класс задач, эта задача намного проще, и она хорошо известна под другим именем.

Попробуйте без PL/SQL решить.

booby, вы так осведомлены ;)
Я живу немного к северу, в районе для белых.
...
Рейтинг: 0 / 0
11.12.2020, 18:37
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027017
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
НеофитSQL,

элементарная задачка с кучей уже опубликованных решений на форуме.

 
еще одно just for fun
Код: plsql
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.
with p(m,f,s) as (
  select 'Adam', 'Eva', 1 from dual union all
  select 'Adam', 'Sue', 1 from dual union all
  select 'John', 'Eva', 2 from dual union all
  select 'Carl', 'Eva', 3 from dual union all
  select 'Igor', 'Sue', 2 from dual union all
  select 'John', 'Lea', 2 from dual union all
  select 'John', 'Kat', 1 from dual union all
--  select 'John', 'Igor', 9 from dual union all
  select 'Carl', 'Kat', 1 from dual
)
,m as (select distinct m from p)
,f as (select distinct f from p)
,ranks as (
   select 
     m,f,s, 
     row_number()over(order by s desc nulls last) s_rnk
   from m cross join f outer apply (select s from p where m.m=p.m and f.f=p.f)
   where rownum>0
)
,res(m,f,cc,s,s_rnk,m1,f1) as (
      select m,f
            ,ku$_vcnt(m,f) cc
            ,s,s_rnk
            ,m m1,f f1
      from ranks r
      where s_rnk=1
   union all
      select case when ranks.m member of cc or ranks.f member of cc then '' else ranks.m end m
            ,case when ranks.m member of cc or ranks.f member of cc then '' else ranks.f end f
            ,case when ranks.m member of cc or ranks.f member of cc then cc else cc multiset union all ku$_vcnt(ranks.m,ranks.f) end as cc
            ,ranks.s,ranks.s_rnk
            ,ranks.m m1, ranks.f f1
      from res, ranks
      where res.s_rnk+1 = ranks.s_rnk
)
select m,f,s 
from res
where m is not null;




 
booby
Вы точно из Маями ?
НеофитSQL
Я живу немного к северу, в районе для белых.
немного?! только к северу? ничего что вообще другой материк?
...
Рейтинг: 0 / 0
11.12.2020, 19:41
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027022
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
xtender,

Задачка для меня новая, поэтому я с интересом с ней повозился, решил тоже рекурсивно на моем 11.2.
Разбираюсь с вашим решением в 28 строк, там несколько конструкций которые мне незнакомы.

А какие еще были решения? У меня не получилось найти через sql.ru поиск.

Напишите поисковую строку, если вам удалось.
...
Рейтинг: 0 / 0
11.12.2020, 19:57
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027027
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
xtender,

У вас в коде ошибка, дает неверный ответ для

Код: plsql
1.
2.
3.
4.
5.
6.
with p(m,f,s) as (
  select 'Carl', 'Eva', 5 from dual union all
  select 'Igor', 'Eva', 4 from dual union all
  select 'Carl', 'Lea', 4 from dual union all
  select 'Igor', 'Lea', 1 from dual
)



Там рекурсия начинается со строки высокого рейтинга, ошибочно полагая что оно будет включено в оптимальное решение.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
,res(m,f,cc,s,s_rnk,m1,f1) as (
      select m,f
            ,ku$_vcnt(m,f) cc
            ,s,s_rnk
            ,m m1,f f1
      from ranks r
      where s_rnk=1
   union all



В моем решении я использовал пустышку для нулевой строки, может это и здесь можно сделать.
...
Рейтинг: 0 / 0
11.12.2020, 20:17
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027035
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
Моя попытка, вроде правильно работает.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
with pairs(m,f,s) as (
  select 'Carl', 'Eva', 5 from dual union all
  select 'Igor', 'Eva', 4 from dual union all
  select 'Carl', 'Lea', 4 from dual union all
  select 'Igor', 'Lea', 1 from dual
),
cte(n,mm,ff,ss) as (
  select 0,   '+', '-', 0 from dual 
union all
  select n+1, mm||','||m, ff||','||f, ss+s
   from cte,pairs c
  where n < (select count(*) from pairs) and 
        instr(mm,m)=0 and instr(ff,f)=0
)
select mm,ff,ss from cte order by ss desc fetch first row only
...
Рейтинг: 0 / 0
11.12.2020, 20:57
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027038
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
НеофитSQL
У вас в коде ошибка
что за бред?
 
Код: plsql
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.
43.
SQL> ;
  1  with p(m,f,s) as (
  2    select 'Carl', 'Eva', 5 from dual union all
  3    select 'Igor', 'Eva', 4 from dual union all
  4    select 'Carl', 'Lea', 4 from dual union all
  5    select 'Igor', 'Lea', 1 from dual
  6  )
  7  ,m as (select distinct m from p)
  8  ,f as (select distinct f from p)
  9  ,ranks as (
 10     select
 11       m,f,s,
 12       row_number()over(order by s desc nulls last) s_rnk
 13     from m cross join f outer apply (select s from p where m.m=p.m and f.f=p.f)
 14     where rownum>0
 15  )
 16  ,res(m,f,cc,s,s_rnk,m1,f1) as (
 17        select m,f
 18              ,ku$_vcnt(m,f) cc
 19              ,s,s_rnk
 20              ,m m1,f f1
 21        from ranks r
 22        where s_rnk=1
 23     union all
 24        select case when ranks.m member of cc or ranks.f member of cc then '' else ranks.m end m
 25              ,case when ranks.m member of cc or ranks.f member of cc then '' else ranks.f end f
 26              ,case when ranks.m member of cc or ranks.f member of cc then cc else cc multiset union all ku$_vcnt(ranks.m,ranks.f) end as cc
 27              ,ranks.s,ranks.s_rnk
 28              ,ranks.m m1, ranks.f f1
 29        from res, ranks
 30        where res.s_rnk+1 = ranks.s_rnk
 31  )
 32  select m,f,s
 33  from res
 34* where m is not null
SQL> /

M    F            S
---- --- ----------
Carl Eva          5
Igor Lea          1

2 rows selected.

...
Рейтинг: 0 / 0
11.12.2020, 21:09
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027039
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
xtender
НеофитSQL
У вас в коде ошибка
что за бред?
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
SQL> ;
  1  with p(m,f,s) as (
  2    select 'Carl', 'Eva', 5 from dual union all
  3    select 'Igor', 'Eva', 4 from dual union all
  4    select 'Carl', 'Lea', 4 from dual union all
  5    select 'Igor', 'Lea', 1 from dual
  6  )


M    F            S
---- --- ----------
Carl Eva          5
Igor Lea          1

2 rows selected.



Должно быть

Код: plaintext
1.
2.
3.
4.
M    F            S
---- --- ----------
Carl Lea          4
Igor Eva          4

для полного счастья.
...
Рейтинг: 0 / 0
11.12.2020, 21:14
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027040
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
тьфу, так ты упрощенный рюкзак решал что ли? даже внятно задачу поставить не можешь...
...
Рейтинг: 0 / 0
11.12.2020, 21:15
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027041
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
xtender
тьфу, так ты упрощенный рюкзак решал что ли? даже внятно задачу поставить не можешь...


> Задача: поженить как можно больше этих людей по критерию максимального общего счастья (арифметической суммы симпатий).

Если вы решали другую задачу, в какой версии задачи "6" является правильным ответом?

У вас код правильно ищет максимум перебором, но ошибочно выбирает первую пару, поэтому попадает на локальный максимум.

Я не знаю что такое упрощенный рюкзак, но погуглю.
...
Рейтинг: 0 / 0
11.12.2020, 21:26
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027043
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
В вашем примере, если я заменю отмеченные строки на "from p", это что-то сломает?
Я не уловил, в чем логика воссоздания уже существующей таблицы p через кросс-джойны, и как "rownum>0" что-то делает.
Вроде как рекурсия будет дольше работать, в конце дожигая nulls которых в таблице p ранее не было.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
with p(m,f,s) as (
  select 'Carl', 'Eva', 5 from dual union all
  select 'Igor', 'Eva', 4 from dual union all
  select 'Carl', 'Lea', 4 from dual union all
  select 'Igor', 'Lea', 1 from dual
)
,m as (select distinct m from p)
,f as (select distinct f from p)
,ranks as (
   select 
     m,f,s, 
     row_number()over(order by s desc nulls last) s_rnk
   from m cross join f outer apply (select s from p where m.m=p.m and f.f=p.f)
   where rownum>0
)
...
Рейтинг: 0 / 0
11.12.2020, 21:36
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027218
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
Погуглил knapsack problem. Нет, это не та.

Задача рюкзаков, и ее модификации отличаются от задач нахождения эксклюзивных пар по критерию.
Она еще известна как задача нахождения некасающихся ребер графа. В варианте (М,Ж) - направленного графа, эта задачка менее обсосана в учебниках, но совместными силами мы ее вроде решили через SQL.

Кто-то хочет попробовать силы в решении более, ээ, либерального варианта задачки?
У меня есть пара идей, но я подожду до понедельника.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
with pairs(m,f,s) as (
  select 'Adam', 'Eva', 1 from dual union all
  select 'Adam', 'Sue', 1 from dual union all
  select 'John', 'Eva', 2 from dual union all
  select 'Carl', 'Eva', 3 from dual union all
  select 'Igor', 'Sue', 2 from dual union all
  select 'John', 'Lea', 2 from dual union all
  select 'John', 'Kat', 1 from dual union all
  select 'John', 'Igor', 9 from dual union all
  select 'Carl', 'Kat', 1 from dual
)
...
Рейтинг: 0 / 0
12.12.2020, 18:30
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027614
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
НеофитSQL

Кто-то хочет попробовать силы в решении более, ээ, либерального варианта задачки?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
with pairs(m,f,s) as (
  select 'Adam', 'Eva', 1 from dual union all
  select 'Adam', 'Sue', 1 from dual union all
  select 'John', 'Eva', 2 from dual union all
  select 'Carl', 'Eva', 3 from dual union all
  select 'Igor', 'Sue', 2 from dual union all
  select 'John', 'Lea', 2 from dual union all
  select 'John', 'Kat', 1 from dual union all
  select 'John', 'Igor', 9 from dual union all
  select 'Carl', 'Kat', 1 from dual
)



я английский плохо знаю
если ==> select 'John', 'Igor', 9 from dual union all про гомиков
то не пойму чем ето усложняет задачу, если решать перебором

.....
stax
...
Рейтинг: 0 / 0
14.12.2020, 13:22
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027630
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Stax,

речь идет о том, что его нужно исключить из списка пригодных к спариванию мужчин,
после того, как на него пал выбор.
...
Рейтинг: 0 / 0
14.12.2020, 14:07
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027649
Фотография env
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
env
Участник
Stax,

Появлением иерархий и циклов. А ещё может оказаться, что рёбра графа не изотропны в зависимости от направления обхода и тогда задача станет окончательно запутанной.

Код: plsql
1.
2.
3.
4.
5.
6.
...
  select 'John', 'Igor', 9 from dual union all
  select 'Igor', 'John', 1 from dual union all
  select 'Kat', 'Sue', 3 from dual union all
  select 'Sue', 'John', 8 from dual union all
...
...
Рейтинг: 0 / 0
14.12.2020, 15:12
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027660
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
booby, env

я наверное неправильно выразился

имел ввиду, простой/грубый перебор сущеструющих пар, без оптимизации

и выбрать с максимальной сумарной выгодой

.....
stax
...
Рейтинг: 0 / 0
14.12.2020, 15:34
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027665
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
да без разницы, задача один хрен остается такой же скучной на перебор - подвид рюкзачных - упрощенная задачка о корзинках
НеофитSQL
Задача коммивояжера - NP. Эта задача - P.
...
Рейтинг: 0 / 0
14.12.2020, 15:44
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027676
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Stax,

выбирается такая последовательность с максимальной суммой, которая содержит допустимый, непротиворечивый список пар.
Не только ведущие мужчины в наборе не должны повторяться, но и ведомые женщины тоже.
Когда без разницы, это называется "шведская семья".
Здесь шведская не подразумевается.
...
Рейтинг: 0 / 0
14.12.2020, 15:55
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027682
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
booby,

да какая разница, если пары не генерить, берем только предоставленные (готовые), для других симпатия=0

подружили кого-то, больше их (обоих, кроме 'Adam', 'Adam' не знаю как толерантно написать) не берем

.....
stax
...
Рейтинг: 0 / 0
14.12.2020, 16:12
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027692
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Stax
... берем только предоставленные (готовые)...
.....
stax

алгоритм такой: взяв такую пару, разрешаем ей быть элементом результата, если ни левый, ни правый элемент еще не был выбран ранее, иначе отбрасываем.
Из всего набора результатов выбираем результат с максимальной оценкой.
Жадный алгоритм будет работать просто на сортированном по текущей стоимости наборе наборе пар и вернет единственную комбинацию.
Алгоритм с соединниями множеств сгенерит все возможные комбинации, дающие максимальный результат.
"простая" задача решается путем ведения двух списков имен - раздельно для "мужчин" и "женщин".
"сложная" - ведением одного, общего списка имен, и в этом отношении,
она как раз проще "простой" - проверка на существование при выборе следующей пары
происходит в одном списке, вместо двух.
...
Рейтинг: 0 / 0
14.12.2020, 16:27
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027700
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
booby

"сложная" - ведением одного, общего списка имен, и в этом отношении,
она как раз проще "простой" - проверка на существование при выборе следующей пары
происходит в одном списке, вместо двух.

так я ж об етом

и для "простой" можно обойтисть одним списком, вперемешку (м,ж)

зі
двойной список нужен для вывода результата (или нужен ид пар)

.....
stax
...
Рейтинг: 0 / 0
14.12.2020, 16:52
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027704
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
xtender
да без разницы, задача один хрен остается такой же скучной на перебор


Обычно задачу называют скучной или простой, решив ее без ошибок.

У вас пока этого не получилось.
...
Рейтинг: 0 / 0
14.12.2020, 17:00
| Ответить | Цитировать | Написать  
Нахождение эксклюзивных пар
    #40027705
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
Stax
booby

"сложная" - ведением одного, общего списка имен, и в этом отношении,
она как раз проще "простой" - проверка на существование при выборе следующей пары
происходит в одном списке, вместо двух.

так я ж об етом

и для "простой" можно обойтисть одним списком, вперемешку (м,ж)

зі
двойной список нужен для вывода результата (или нужен ид пар)

.....
stax


Я тоже думаю что один список - это более чистое решение задачи чем помещение гомов в оба списка, с последующим исключением дубликатов. Второе решение довольно просто записать, первое (с единым списком) я пока не пробовал.
...
Рейтинг: 0 / 0
14.12.2020, 17:04
| Ответить | Цитировать | Написать  
25 сообщений из 27, страница 1 из 2
  1  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Нахождение эксклюзивных пар
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=40026978&tid=1880607]:
 0ms
get settings:
 7ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 106ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 307ms
total:  505ms
созд. / загр.: 505ms
x
x
Закрыть


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