Выберите Отдельные значения один раз из нескольких столбцов в этой таблице, сохранив исходный порядок?

Question

У меня есть (подзапрос) таблица, в которой перечислены предпочтения в еде для моих друзей.Каждую еду можно принимать только один раз, и каждый человек может съесть только одну еду.

row_number person_id   meal_id
   1           1           3       
   2           2           1
   3           2           2
   4           2           3      
   5           3           1   
   6           3           2
   7           3           3

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

person_id   meal_id
   1           3       
   2           1   
   3           2

Поскольку еда 1 принимается пользователем 2, пользователь 3 получает еду 2. Я думаю, что это можно решить, выбрав разные значения в обоих столбцах на основе их первоначального порядка, но я не могу понять, как записать этозапрос.Любая помощь приветствуется.

Обновление Добавлено row_number в исходную таблицу.

Answer 1

Если я правильно понимаю, это довольно сложная проблема с ходом по графу.Прежде всего я должен отметить, что нет гарантии оптимального решения - без большой и большой работы.Но вы можете реализовать жадный алгоритм, используя рекурсивные CTE:

with recursive t as (
      select v.*
      from (values (1, 1, 3), (2, 2, 1), (3, 2, 2), (4, 2, 3), (5, 3, 1), (6, 3, 2), (7, 3, 3)
           ) v(row_number, person_id, meal_id)
     ),
     cte (row_number, person_id, meal_id, rows, persons, meals, lev) as (
     select row_number, person_id, meal_id, array[row_number], array[person_id], array[meal_id], 1 as lev
     from t
     where row_number = 1
     union all
     select t.row_number, t.person_id, t.meal_id,
            (case when t.person_id = any(cte.persons) or t.meal_id = any(cte.meals)
                  then cte.rows
                  else array_append(cte.rows, t.row_number)
             end),
            (case when t.person_id = any(cte.persons) or t.meal_id = any(cte.meals)
                  then cte.persons
                  else array_append(cte.persons, t.person_id)
             end),
            (case when t.person_id = any(cte.persons) or t.meal_id = any(cte.meals)
                  then cte.meals
                  else array_append(cte.meals, t.meal_id)
             end),
            cte.lev + 1
     from cte join
          t
          on t.row_number = cte.row_number + 1
    )
select t.*
from t cross join
     (select rows from cte order by lev desc fetch first 1 row only) as last1
where t.row_number = any (last1.rows);

Здесь - это db <> скрипка.