[kdb +/q]: преобразовать матрицу смежности в список смежности

Question

Данная (прямоугольная) матрица смежности m, как построить список смежности в q языке?

В QIdioms wiki я нашел решение в k языке, когда проходят через q консоль с k) команды дает мне сообщение об ошибке: 'vs

m:(1 0 1;1 0 1) 
k) (^m)_vs &,/m 
'vs 

Результат должен быть:

0 0 1 1 
0 2 0 2 

Это то, что Я смог реплицировать в q:

k) &,/m 
0 2 3 5 
q) where raze m 
0 2 3 5 

k «s ^ ака shape глагол отсутствует в q, так что я только что сделал:

k) (^m) 
000b 
000b 
q) 2 3#0b 
000b 
000b 

Теперь, так как:

q) parse "vs" 
k) {x\:y} 

Я безуспешно пытался как:

q) (2 3#0b) _vs where raze m 
' 
q) (2 3#0b) _\: where raze m 
'type 

Обратите внимание, что QIdioms wiki имеет q solution для обратной задачи: от adj.list до adj.matrix.

Answer 1

У вас есть ошибки, потому что оригинальные Q-идиомы записаны в k2 - старая версия k, которую не поддерживает современная версия kdb +. Текущая версия k - k4, и она не обратно совместима с k2.

Например, X _vs Y, где Х и Y являются целыми атомы или списки в старой k2 вели себя как X vs Yбудет ведут себя в КДБ +, начиная с 3.4t 2015.12.13: http://code.kx.com/q/ref/lists/#vs:

Since 3.4t 2015.12.13: For integer types, computes the base representation of Y in the radices X.

Еще один пример. Действительно, ^ в k2 был оператором формы, но это уже не так. Насколько я понял, в k2 ^m вернул 2 3 для матрицы m из вашего примера, тогда как текущая реализация ведет себя как qnot null.

Теперь вернемся к исходному вопросу, «как создать список смежности в q языке». Один из способов сделать это заключается в следующем:

q)lm:{flip raze(til count x),''where each x} 

или

k)lm:{+,/(!#x),''&:'x} 

UPDATE: Вот как это работает. Если бы мы должны были построить список смежности с помощью любого «многословный» язык мы будем делать что-то вроде этого:

for i = 0 to <number of rows> - 1   <---- (1) 
    for j = 0 to <number of columns> - 1  <---- (2) 
     if M[i;j] <> 0      <---- (3) 
      print i, j 

В языке массива, как д (1) можно «перевести» на til count M потому что count возвращает количество элементов на верхнем уровне, т. е. количестве строк.(2) и (3) объединенный может быть представлен: where each M. Действительно, для каждой строки мы возвращаем позиции ненулевых элементов. Учитывая исходную матрицу m, мы получим:

til count m -> 0 1 
where each m -> (0 2; 0 2) 

Все, что нам нужно сделать, это объединение индексов строк и столбцов. Мы не можем использовать только ,', потому что он присоединится к 0 с первым 0 2 и 1 со вторым 0 2, что приведет к (0 0 2; 1 0 2). Нам нужно идти на один уровень глубже, соединяя каждый элемент слева с каждым элементом каждого элемента вложенного списка (0 2; 0 2) справа, следовательно, двойные апострофы в ,''.

Надеюсь, теперь это имеет смысл.

---

Лично я бы не использовать flip (или + в к), я не могу читать матрицу смежности в таком виде:

0 0 1 1 
0 2 0 2 

Я думаю, что это гораздо более удобным для чтения:

0 0 
0 2 
1 0 
1 2 

Но это зависит от вас, конечно.