Гость
Войти | Профиль | Очистить
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Нахождение эксклюзивных пар / 25 сообщений из 27, страница 1 из 2
  1  все
11.12.2020, 17:49
    #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, 18:02
    #40026984
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахождение эксклюзивных пар
Задачу коммивояжера тут уже решали, воспользуйтесь поиском.
И это... Нафиг такие усложнения, у меня, быть может, фобия.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.12.2020, 18:15
    #40026991
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахождение эксклюзивных пар
НеофитSQL,

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

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


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

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

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

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

booby, вы так осведомлены ;)
Я живу немного к северу, в районе для белых.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.12.2020, 19:41
    #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:57
    #40027022
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахождение эксклюзивных пар
xtender,

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

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

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


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

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

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

Я не знаю что такое упрощенный рюкзак, но погуглю.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.12.2020, 21:36
    #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
| Ответить | Цитировать | Написать  
12.12.2020, 18:30
    #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
| Ответить | Цитировать | Написать  
14.12.2020, 13:22
    #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, 14:07
    #40027630
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахождение эксклюзивных пар
Stax,

речь идет о том, что его нужно исключить из списка пригодных к спариванию мужчин,
после того, как на него пал выбор.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.12.2020, 15:12
    #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:34
    #40027660
Stax
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Нахождение эксклюзивных пар
booby, env

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

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

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

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

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

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

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

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

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

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

так я ж об етом

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

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

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


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

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

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

так я ж об етом

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

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

.....
stax


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


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