SQL - Return All Possible Combinations of Values in a Column by Means of Two New Columns

Обновить

November 2018

Просмотры

307 раз

2

Я хочу, чтобы вернуть все возможные комбинации значений в столбце с помощью двух новых столбцов. Например, моя колонка состоит из значений (A, B, C, D). Возможные комбинации этих значений являются (А, В), (А, С), (А, D), (В, С), (В, D), (С, D), (А, В, С) , (в, D, с), (D, с, А), (с, А, в) [Замечание: Я не хочу, чтобы рассмотреть (1) combintions только с одним значением, (2) комбинации с все значения и (3) сочетание без каких-либо значений. Таким образом, у меня есть 2 ^ (N) -N-1-1 комбинации для различных значений п]. Я хочу, чтобы перечислить все эти комбинации в двух столбцах, как показано ниже.

Считайте, что я начинаю с этой колонки:

Col0
----
A
B
C
D

Из Col0 я хочу, чтобы произвести 10 комбинаций с использованием двух колонок:

Col1 Col2
---- ----
1    A
1    B
2    A
2    C
3    A
3    D
4    B
4    C
5    B
5    D
6    C
6    C
7    A
7    B
7    C
8    B
8    C
8    D
9    C
9    D
9    A
10   D
10   A
10   B

Как это сделать в SQL? Я использую SQLite.

Спасибо большое!

3 ответы

1

Идея заключается в том , чтобы перечислить набор мощности, путем присвоения каждому значению степени 2, то итерация от 1 до 2 ^ N - 1 , и фильтровать элементы , которые устанавливаются соответствующий бит.

-- map each value with a power of 2 : 1, 2, 4, 8, 16
with recursive ELEMENTS(IDX, POW, VAL) as (
  -- init with dummy values 
  values(-1, 0.5, null)
  union all
  select IDX + 1,
    POW * 2,
    -- index the ordered values from 0 to N - 1
    ( select COL0 
      from DATA d1 
      where (select count(*) from DATA d2 where d2.COL0 < d1.COL0) = IDX + 1)
  from ELEMENTS 
  where IDX + 1 < (select count(*) from data)
), POWER_SETS(ITER, VAL, POW) as (
  select 1, VAL, POW from ELEMENTS where VAL is not null
  union all
  select ITER + 1, VAL, POW
  from POWER_SETS
  where ITER < (select SUM(POW) from elements) )
select ITER, VAL from POWER_SETS
-- only if the value's bit is set
where ITER & POW != 0

EDIT: вторая версия, с помощью MatBailie . Только один из КТР является рекурсивным, и одноэлементные подмножества исключаются.

WITH RECURSIVE
  -- number the values
  elements(val, idx) AS (
    SELECT d1.col0, (select count(*) from DATA d2 where d2.COL0 < d1.COL0)
    FROM DATA d1
  ), 
  -- iterate from 3 (1 and 2 are singletons) 
  -- to 2^n - 1 (subset containing all the elements)
  subsets(iter) AS (
    VALUES(3)
    UNION ALL
    SELECT iter + 1
    from subsets
    WHERE iter < (1 << (SELECT COUNT(*) FROM elements)) - 1
  )
SELECT iter AS Col1, val AS Col2
FROM elements
CROSS JOIN subsets
-- the element is present is this subset (the bit is set)
WHERE iter & (1 << idx) != 0
-- exclude singletons (another idea from MatBailie)
AND iter != (iter & -iter)
ORDER BY iter, val
bwt
1

Если окно функции и КТР доступна, то вы можете использовать следующий подход

with data_rn as
(
    select d1.col0 col1, 
           d2.col0 col2, 
           row_number() over (order by d1.col0) rn
    from data d1
    inner join data d2 on d1.col0 > d2.col0
)
select rn, col1 from data_rn
union all
select rn, col2 from data_rn
order by rn

dbfiddle демо

2

У меня есть решение, но оно требует два изменений ...

  1. Каждый элемент должен быть дан id (начиная с 1)
  2. Выходные идентификаторы не могут быть последовательными


 id | datum
----+-------
  1 |   A
  2 |   B
  3 |   C
  4 |   D

(Выход id«s рассчитать эффективно идентификаторы для каждого перестановки , но я не выходные перестановок вы не заинтересованы в ...)

 group_id | datum
----------+-------
    6     |   A
    6     |   B

    7     |   A
    7     |   C

    8     |   A
    8     |   D

    12    |   B
    12    |   C

    13    |   B
    13    |   D

    18    |   C
    18    |   D

    32    |   A
    32    |   B
    32    |   C

    33    |   A
    33    |   B
    33    |   D

    38    |   A
    38    |   C
    38    |   D

    63    |   B
    63    |   C
    63    |   D


http://dbfiddle.uk/?rdbms=sqlite_3.8&fiddle=87d670ecaba8b735cb3f95fa66cea96b

http://dbfiddle.uk/?rdbms=sqlite_3.8&fiddle=26e4f59874009ef95367d85565563c3c

WITH
  cascade AS
(
  SELECT
    1          AS depth,
    NULL       AS parent_id,
    id,
    datum,
    id         AS datum_id
  FROM
    sample

  UNION ALL

  SELECT
    parent.depth + 1,
    parent.id,
    parent.id * (SELECT MAX(id)+1 FROM sample) + child.id - 1,
    child.datum,
    child.id
  FROM
    cascade  AS parent
  INNER JOIN
    sample   AS child
      ON child.id > parent.datum_id
),
  travelled AS
(
    SELECT
      depth       AS depth,
      parent_id   AS parent_id,
      id          AS group_id,
      datum       AS datum,
      datum_id    AS datum_id
    FROM
      cascade
    WHERE
       depth NOT IN (1, (SELECT COUNT(*) FROM sample))

    UNION ALL

    SELECT
      parent.depth,
      parent.parent_id,
      child.group_id,
      parent.datum,
      parent.datum_id
    FROM
      travelled   AS child
    INNER JOIN
      cascade     AS parent
        ON parent.id = child.parent_id
)
SELECT
  group_id,
  datum
FROM
  travelled
ORDER BY
  group_id,
  datum_id

Первый КТР ходит все доступные комбинации (рекурсивно) , создавая направленный граф. На данном этапе я не исключаю комбинации одного элемента или все элементы, но я исключаю эквивалентные перестановки.

Каждый узел также имеет уникальный идентификатор , рассчитанный для него. Есть пробелы в этих idх, потому что расчет также будет работать для всех перестановок , даже если они не включены.

Принимая любой узел в этом графике и ходить до конечного родительского узла (рекурсивно снова) всегда будет давать различные комбинации , чем если бы вы начали с другого узла в графе.

Таким образом, второй КТР делает все эти прогулки, за исключением комбинаций «только один пункт» и «все элементы».

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

Пробелы в id«S, вероятно , можно избежать , но математика слишком трудно для моей головы в конце рабочего дня.