Блог

У меня есть матрица с сегментами и элементами, как показано ниже. Если элемент может поместиться в сегмент, он равен 1 в соответствующей ячейке

Например: если вы посмотрите на изображение, элемент x может поместиться в сегменты -a, b, c, а не в d и e

Я хочу найти наименьшее количество сегментов для группировки моих элементов. В этом случае сегменты c и d могут группировать все элементы всего в двух сегментах.

Есть идеи, могу ли я сделать это в bigquery динамически и эффективно? исходные данные не так просты, как это.

  select "element-x" as element , 1 as bucketa, 1 as bucketb, 1 as bucketc, 0 as bucketd, 0 as buckete
 union all
 select "element-y" as element , 0 as bucketa, 0 as bucketb, 1 as bucketc, 0 as bucketd, 0 as buckete
 union all
 select "element-z" as element , 1 as bucketa, 0 as bucketb, 1 as bucketc, 0 as bucketd, 0 as buckete
 union all
 select "element-p" as element , 0 as bucketa, 0 as bucketb, 1 as bucketc, 0 as bucketd, 0 as buckete
 union all
 select "element-q" as element , 1 as bucketa, 0 as bucketb, 0 as bucketc, 1 as bucketd, 0 as buckete
 union all
 select "element-r" as element , 0 as bucketa, 1 as bucketb, 0 as bucketc, 1 as bucketd, 1 as buckete
 

Рассмотрим приведенное ниже решение — очевидно, вам нужно убедиться, что вы предоставляете точные данные в matrix CTE, а также вам необходимо соответствующим образом настроить buckets_elements CTE для отражения всех сегментов в матрице. Остальная часть CTE и окончательный запрос сделают работу за вас!

 with matrix as (
  select "element-x" as element, 1 as bucketa, 1 as bucketb, 1 as bucketc, 0 as bucketd, 0 as buckete union all
  select "element-y", 0, 0, 1, 0, 0 union all
  select "element-z", 1, 0, 1, 0, 0 union all
  select "element-p", 0, 0, 1, 0, 0 union all
  select "element-q", 1, 0, 0, 1, 0 union all
  select "element-r", 0, 1, 0, 1, 1    
), buckets_elements as ( 
  select array[struct(a), struct(b), struct(c), struct(d), struct(e)] buckets
  from (
    select 
      array_agg(if(bucketa = 1, element, null) ignore nulls) a,
      array_agg(if(bucketb = 1, element, null) ignore nulls) b,
      array_agg(if(bucketc = 1, element, null) ignore nulls) c,
      array_agg(if(bucketd = 1, element, null) ignore nulls) d,
      array_agg(if(buckete = 1, element, null) ignore nulls) e
    from matrix
  )
), columns_names as (
  select 
    regexp_extract_all(to_json_string((select as struct * except(element) from unnest([t]))), r'"([^"] )"') cols
  from matrix t limit 1
), columns_index as (
  select generate_array(0, array_length(cols) - 1) as arr  
  from columns_names
), buckets_combinations as (
  select  
    (select array_agg(
      case when n amp; (1<<pos) <> 0 then arr[offset(pos)] end 
      ignore nulls)
     from unnest(generate_array(0, array_length(arr) - 1)) pos
    ) as combo
  from columns_index cross join 
  unnest(generate_array(1, cast(power(2, array_length(arr)) - 1 as int64))) n
)
select 
  array(select cols[offset(i)] from columns_names, unnest(combo) i) winners
from (
  select combo, 
    rank() over(order by (select count(distinct  el) from unnest(val) v, unnest(v.a) el) desc, array_length(combo)) as rnk
  from (
    select any_value(c).combo, array_agg(buckets[offset(i)]) val
    from buckets_combinations c, unnest(combo) i, buckets_elements b
    group by format('%t', c)
  )
)
where rnk = 1
 

с выводом