Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 Наборы уникальных комбинаций  [new]
mnemolog
Member

Откуда:
Сообщений: 27
Добрый день

Как можно получить набор уникальных комбинаций?
with t as (
select 1 id from dual
union all
select 2 from dual
union all
select 3 from dual
union all
select 4 from dual
)
select * from t t1,t t2 where t1.id < t2.id

1 2
1 3
1 4
2 3
2 4
3 4

Желаемы результат:
1я-группа:
1 2
2 4
2я-группа:
1 3
2 4
3я-группа:
1 4
2 3

элементов может быть больше 4

Спасибо
8 ноя 18, 15:07    [21728271]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
Dshedoo
Member

Откуда:
Сообщений: 228
mnemolog,

Мы не телепаты, мы просто переводчики с языка логики на SQL.
Опишите логику, согласно которой, строки должны попадать в ту или иную группу.
8 ноя 18, 15:34    [21728315]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
mnemolog
Member

Откуда:
Сообщений: 27
Dshedoo,

В группу попадают все уникальные значения в комбинациях, то есть:
для 1й зруппы:
уникальны 1 2 и 3 4 (ошибся, написал 2 вместо 3х)
для 2й:
1 3 и 2 4 - элементы не повторяются, всего два сочетания
8 ноя 18, 15:44    [21728329]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
-2-
Member

Откуда:
Сообщений: 13960
golomenm
Желаемы результат
Осталось пояснить, что является исходными данными.
8 ноя 18, 16:15    [21728364]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 16844
-2-
golomenm
Желаемы результат
Осталось пояснить, что является исходными данными.

Я пока не понял даже что именно хочет ТС - комбинации, сочетания или перестановки?
8 ноя 18, 16:21    [21728371]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
-2-
Member

Откуда:
Сообщений: 13960
andrey_anonymous
Я пока не понял даже что именно хочет ТС - комбинации, сочетания или перестановки?
Сочетание перестановок!
Вероятно группу образует максимальное количество пар с соблюдением сквозной уникальности элементов. Задача - получить все такие группы.
Однако не понятно, является ли первичным линейный список или непосредственно пары. Во втором случае получается возможна комбинация (1,2),(3,4),(5,6),(7,8). Которая образует единственную группу из четырех пар.
8 ноя 18, 16:34    [21728385]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
mnemolog
Member

Откуда:
Сообщений: 27
andrey_anonymous,

Комбинации уже есть.
Данные можно сгенирировать (элементы - возрастающая последовательность натуральных чисел):
+

with t as (
select 1 id from dual
union all 
select 2 from dual
union all
select 3 from dual
union all
select 4 from dual
)
select * from t t1,t t2 where t1.id < t2.id



Результат:
+

t1.idt2.id
12
13
14
23
24
34



Необходимо получить группы уникальных комбинаций, все элементы должны быть уникальны в рамках группы
Из приведенных выше данных должно получится 3 группы:
+

t1.idt2.id
12
34

t1.idt2.id
13
24

t1.idt2.id
14
23

8 ноя 18, 16:37    [21728393]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
Кобанчег
Member

Откуда:
Сообщений: 508
mnemolog,

Я так понимаю основная фишка в том, что если вторая пара уже была использована в одной из групп, то больше она использована быть не может.
SQL> with t(id) as (
  2  select 1 from dual
  3  union all
  4  select 2 from dual
  5  union all
  6  select 3 from dual
  7  union all
  8  select 4 from dual
  9  union all
 10  select 5 from dual
 11  )
 12  , tt as
 13  (select row_number() over (order by t1.id, t2.id) rn,
 14         t1.id x,
 15         t2.id y
 16    from t t1, t t2
 17   where t1.id < t2.id)
 18  , r(rn, x, y, x0, y0, allocated) as
 19  (
 20  select tt.rn,
 21         tt.x,
 22         tt.y,
 23         (select min(x) keep (dense_rank first order by t0.rn)
 24            from tt t0
 25           where tt.rn < t0.rn and tt.x not in (t0.x, t0.y) and tt.y not in (t0.x, t0.y)),
 26         (select min(y) keep (dense_rank first order by t0.rn)
 27            from tt t0
 28           where tt.rn < t0.rn and tt.x not in (t0.x, t0.y) and tt.y not in (t0.x, t0.y)),
 29         ku$_vcnt('~')
 30    from tt
 31   where rn = 1
 32  union all
 33  select tt.rn,
 34         tt.x,
 35         tt.y,
 36         (select min(x) keep (dense_rank first order by t0.rn)
 37            from tt t0
 38           where tt.rn < t0.rn and tt.x not in (t0.x, t0.y) and tt.y not in (t0.x, t0.y)
 39             and t0.x || '~' || t0.y not member of allocated multiset union ku$_vcnt(r.x0 || '~' || r.y0)),
 40         (select min(y) keep (dense_rank first order by t0.rn)
 41            from tt t0
 42           where tt.rn < t0.rn and tt.x not in (t0.x, t0.y) and tt.y not in (t0.x, t0.y)
 43             and t0.x || '~' || t0.y not member of allocated multiset union ku$_vcnt(r.x0 || '~' || r.y0)),
 44         allocated multiset union ku$_vcnt(r.x0 || '~' || r.y0)
 45    from tt
 46    join r on tt.rn = r.rn + 1
 47  )
 48  select x, y, x0, y0
 49    from r
 50   where x0 is not null;

         X          Y         X0         Y0
---------- ---------- ---------- ----------
         1          2          3          4
         1          3          2          4
         1          4          2          3
         2          3          4          5
         2          4          3          5


Это решение для версии 11gR2.
На 12с+ можно использовать cross apply/lateral вместо скаляров.

Еще решается моделью.
8 ноя 18, 17:04    [21728434]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 1371
mnemolog,

для 5-ти как будет?
 1  with t as (
 2  select 1 id from dual
 3  union all
 4  select 2 from dual
 5  union all
 6  select 3 from dual
 7  union all
 8  select 4 from dual
 9  union all
10  select 5 from dual
11  --union all
12  --select 4 from dual
13  )
14* select * from t t1,t t2 where t1.id < t2.id
QL> /

       ID         ID
--------- ----------
        1          2
        1          3
        1          4
        1          5
        2          3
        2          4
        2          5
        3          4
        3          5
        4          5

0 rows selected.


напр для 1 2

группы
1 2
3 4

или
1 2
3 5

или
1 2
4 5
какую брать ?

зи
недавно пятничная задачка похожая была

.....
stax
8 ноя 18, 17:38    [21728494]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
-2-
Member

Откуда:
Сообщений: 13960
Кобанчег
если вторая пара уже была использована в одной из групп, то больше она использована быть не может
Странный критерий "вторая" в неупорядоченном множестве. Последняя пара, естественно никогда не повторяется, потому что полностью зависима от предшествующих (остаток из). Но в наборе, полученном из чисел 1-4 и первая пара получается единственной в группе как предстаток от остатка.
8 ноя 18, 17:46    [21728515]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 1371
Кобанчег,

я так понимаю в группе не обязательно две пары,
напр для n=6 допустимая группа
1 2
3 4
5 6

.....
stax
8 ноя 18, 17:47    [21728518]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 1371
mnemolog,

сгенерить всевозможные перестановки 1 2 3 4 ... n (n!)
із них нарезать пары (по два значения)

.....
stax
8 ноя 18, 17:54    [21728527]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
Кобанчег
Member

Откуда:
Сообщений: 508
-2-
Кобанчег
если вторая пара уже была использована в одной из групп, то больше она использована быть не может
Странный критерий "вторая" в неупорядоченном множестве. Последняя пара, естественно никогда не повторяется, потому что полностью зависима от предшествующих (остаток из). Но в наборе, полученном из чисел 1-4 и первая пара получается единственной в группе как предстаток от остатка.
Если мы составляем пары из множесва уникальных чисел, то эти пары можно упорядочить.
Автор получил пары путем self join, но этого же можно было достичь с помощью powermultiset_by_cardinality(..., 2), не суть.

Касаемо "переиспользования", то пара (2, 3) не может быть использована для (1, 5), поскольку уже задействована для (1, 4).
Ну это моё понимание задачи ТС.
Если же "переиспользование" возможно, то простой self join пар поможет достичь цели.
8 ноя 18, 17:57    [21728532]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
SkilledJunior
Member

Откуда:
Сообщений: 284
with t  as (select level id from dual connect by level <= :n)
    ,tt as (select t1.id a1,
                   t2.id a2
            from t t1,t t2
            where t1.id < t2.id)
    ,r  as (select tt1.a1 a11,
                   tt1.a2 a12,
                   tt2.a1 a21,
                   tt2.a2 a22,
                   row_number() over (order by tt1.a1, tt1.a2, tt2.a1, tt2.a2) gr
            from tt tt1, tt tt2
            where tt2.a1 >  tt1.a1 and
                  tt1.a1 != tt2.a2 and
                  tt1.a2 != tt2.a1 and
                  tt1.a2 != tt2.a2)
    ,m  as (select level l from dual connect by level <= 2)
select gr, decode(l, 1, a11, 2, a21) n1, decode(l, 1, a12, 2, a22) n2
from r, m
order by gr, l
9 ноя 18, 01:33    [21728937]     Ответить | Цитировать Сообщить модератору
 Re: Наборы уникальных комбинаций  [new]
-2-
Member

Откуда:
Сообщений: 13960
Stax
для 5-ти как будет?
Предположу, что при непереиспользовании пар "пятый" элемент выпадет в однопарные группы
МНОГОРАЗ   или  ОДНОРАЗ
---------       ---------
1,2  3,4        1,2  3,4 
1,2  3,5        1,3  2,4 
1,2  4,5        1,4  2,3 
1,3  2,4        1,5      
1,3  2,5        2,5      
1,3  4,5        3,5      
1,4  2,3        4,5      
1,4  2,5 
1,4  3,5 
1,5  2,3 
1,5  2,4 
1,5  3,4 
2,3  4,5 
2,4  3,5 
2,5  3,4 
9 ноя 18, 07:04    [21728959]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить