Сжать разреженную матрицу

18

Сжать разреженную матрицу, используя сжатый разреженный ряд (формат CSR, CRS или Yale) .

Это все одинаковые формы сжатия (игнорируйте новый Yale).

Входными данными может быть любая двумерная структура данных (список списков и т. Д.): Например,

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

И выходные данные должны быть тремя 1d структурами данных (список и т. Д.), Которые обозначают выходные данные A, IAи JA, например,

[5, 8, 3, 6]
[0, 0, 2, 3, 4]
[0, 1, 2, 1,]

Процесс описан википедией:

  • Массив A имеет длину NNZ и содержит все ненулевые элементы M в порядке слева направо сверху вниз («строка-майор»).

  • Массив IA имеет длину m + 1. Он определяется этим рекурсивным определением:

    • IA [0] = 0 IA [i] = IA [i - 1] + (количество ненулевых элементов в (i - 1) -й строке в исходной матрице)

    • Таким образом, первые m элементов IA хранят индекс в A первого ненулевого элемента в каждой строке M, а последний элемент IA [m] хранит NNZ, количество элементов в A, которое также можно рассматривать как индекс в A первого элемента фантомной строки сразу за концом матрицы M. Значения i-й строки исходной матрицы считываются из элементов A [IA [i]] в A [IA [i +] 1] - 1] (включительно с обоих концов), то есть от начала одной строки до последнего индекса непосредственно перед началом следующей. [5]

    • Третий массив, JA, содержит индекс столбца в M каждого элемента A и, следовательно, также имеет длину NNZ.

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

Контрольные примеры

Вход 1: 

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

Выход 1:

[ 5, 8, 3, 6 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

Вход 2

[[10 20 0 0 0 0],
 [0 30 0 40 0 0],
 [0 0 50 60 70 0],
 [0 0 0 0 0 80]]

Выход 2:

[ 10 20 30 40 50 60 70 80 ]
[  0  2  4  7  8 ]
[  0  1  1  3  2  3  4  5 ]

Вход 3:

[[0 0 0],
 [0 0 0],
 [0 0 0]]

Выход 3:

[ ]
[ 0 0 0 0 ]
[ ]

Вход 4:

[[1 1 1],
 [1 1 1],
 [1 1 1]]

Выход 4:

[ 1 1 1 1 1 1 1 1 1 ]
[ 0 3 6 9 ]
[ 0 1 2 0 1 2 0 1 2 ]

Вход 5: 

[[0 0 0 0],
 [5 -9 0 0],
 [0 0 0.3 0],
 [0 -400 0 0]]

Выход 5:

[ 5, -9, 0.3, -400 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

Предположим, что входные данные могут содержать любое действительное число, вам не нужно учитывать математические символы или экспоненциальное представление (например, 5000 никогда не будет введено как 5e3). Вам не нужно обрабатывать inf, -inf, NaNили любые другие «псевдо-номера». Вы можете вывести другое представление числа (5000 может быть представлен в виде 5E3 , если вы этого хотите).

Подсчет очков:

Это код-гольф , побеждает меньше байтов.

Leaderboards

Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

# Perl, 43 + 2 (-p flag) = 45 bytes

Вы также можете сделать название языка ссылкой, которая затем будет отображаться во фрагменте списка лидеров:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Показать фрагмент кода

code-golf number array-manipulation matrix Pureferret
источник
Можно ли использовать индексы на основе 1 для последней строки?
Лев
@ Лео для JA? Нет
Pureferret
1
Не является ли это IA[0] = 0совершенно ненужным? Нужно только определить IA[i] = IA[i − 1]..., но мы могли бы просто заявить, что если i-1 < 0использовать 0. То есть, IA [0] всегда равно 0, поэтому его можно сжать (да, я понимаю, что это критика алгоритма, не этот вызов).
Draco18s
Будет ли у нас и обратный вызов?
Адам
1
Ухоженная! Раньше я не сталкивался ни с одним из этих форматов, но я рад, что кто-то уже видел это раньше (я не должен быть человеком, который замечает тривиальные оптимизации в старых алгоритмах).
Draco18s

Ответы:

6

MATL , 19 байт

!3#f!Dx0Gg!XsYshDq!

Ввод используется в ;качестве разделителя строк.

Попробуйте онлайн! Или проверьте все тестовые случаи: 1 , 2 , 3 , 4 , 5 .

объяснение

!     % Implicit input. Transpose
3#f   % 3-output version of find: it takes all nonzero values and pushes
      % their column indices, row indices, and values, as column vectors
!     % Transpose into a row vector
D     % Display (and pop) vector of values
x     % Delete vector of row values
0     % Push 0
G     % Push input
g     % Convert to logical: nonzeros become 1
!     % Transpose
Xs    % Sum of columns. Gives a row vector
Ys    % Cumulative sum
h     % Prepend the 0 that's below on the stack
D     % Display (and pop) that vector
q     % Subtract 1 from the vector of row indices
!     % Transpose into a row vector. Implicitly display
Луис Мендо
источник
3

Haskell, 87 байт

f s|a<-filter(/=0)<$>s=(id=<<a,scanl(+)0$length<$>a,s>>= \t->[i|(i,e)<-zip[0..]t,e/=0])

Попробуйте онлайн!

Как это устроено:

a<-filter(/=0)<$>s           -- let a be the list of lists with all 0 removed]
                             -- e.g. [[1,0,0],[0,3,4]] -> [[1],[3,4]]

                             -- return a triple of

id=<<a                       -- a concatenated into a single list -> A 

scanl(+)0$length<$>a         -- partial sums of the length of the sublists of a
                             -- strating with an additional 0 -> IA

s>>=                         -- map the lambda over the sublists of s and concatenate
                             -- into a single list
   \t->[i|(i,e)<-zip[0..]t,e/=0]  -- the indices of the non-zero elements -> JA
Ними
источник
2

APL (Dyalog) , 31 28 символов или 36 33 байта *

Требуется ⎕IO←0для индексации с нуля. I / O - это список списков.

{(∊d)(0,+\≢¨d←⍵~¨0)(∊⍸¨⍵≠0)}

Попробуйте онлайн!

{… } Анонимная функция, в которой аргумент представлен ⍵

 (... )(... )(... ) вернуть список из трех вещей:

  ⍵≠0 Логическое где аргумент отличается от 0
  ⍸¨ ɩ ndices тех , для каждого суб-списка
  ∊ е NLIST (сплющить) объединить в один список

  ⍵~¨0 удалить нули из каждого суб-лист аргумента
  d← магазина , который , как д
  ≢¨  бирки каждой
  +\ совокупная суммы
  0, Prepend ноля

  ∊d ε NLIST (Flatten) d объединить в один список

  

* Чтобы запустить в Dyalog Classic, просто замените ⍸на ⎕U2378.

Адам
источник
Хорошо, я не понимаю, хотя формат ввода? f 4 4⍴а потом значения?
Pureferret
@Pureferret Код определяет функцию f. Входное действительно РЕПЛИ, который требует fот результата , 4 4⍴…который г eshapes данных в матрицу 4 × 4.
Адам
1
Ро для г eshapes. Я понял!
Pureferret
1
@Pureferret Я обновил Попробуйте онлайн! ссылка, чтобы лучше показать тестовые случаи.
Адам
2

PHP , 107 байт

<?for($y=[$c=0];$r=$_GET[+$l++];)foreach($r as$k=>$v)!$v?:[$x[]=$v,$z[]=$k,$y[$l]=++$c];var_dump($x,$y,$z);

Попробуйте онлайн!

PHP , 109 байт

<?$y=[$c=0];foreach($_GET as$r){foreach($r as$k=>$v)if($v){$x[]=$v;$z[]=$k;$c++;}$y[]=$c;}var_dump($x,$y,$z);

Попробуйте онлайн!

Йорг Хюльсерманн
источник
Нужно ли, чтобы числа были строками?
Pureferret
1
@Pureferret Любой вход в PHP - это строка или массив строк. Я не произвел входные данные, поэтому, если вы хотите, чтобы выходные данные были чисто int, замените их $x[]=$v на$x[]=+$v
Jörg Hülsermann
2

JavaScript (ES6), 117 байт

a=>[a.map((b,i)=>(b=b.filter((x,c)=>x&&o.push(c)),m[i+1]=m[i]+b.length,b),m=[0],o=[]).reduce((x,y)=>x.concat(y)),m,o]

Ввод - это двумерный массив чисел, а вывод - массив [A, IA, JA].

Разъяснения

a=>[
    a.map((b,i) => (                                // map each matrix row
            b = b.filter((x,c) => x                 // filter to only non-zero elements
                && o.push(c)                        // and add this index to JA
            )
            m[i+1] = m[i] + b.length,               // set next value of IA
            b                                       // and return filtered row
        ),
        m=[0],o=[]                          // initialize IA (m) and JA (o)
    ).reduce((x,y) => x.concat(y)),                 // flatten the non-zero matrix
m,o]                                                // append IA and JA

тесты

Показать фрагмент кода

Джастин Маринер
источник
1

Perl 6 , 84 байта

{.flatmap(*.grep(+*)),(0,|[\+] .map(+*.grep(+*))),.flat.kv.flatmap:{$^a%.[0]xx?$^b}}

Попробуйте онлайн!

Единственный матричный аргумент находится в $_.

  • .flatmap(*.grep(+*)) выбирает ненулевые элементы всей матрицы.
  • [\+] .map(+*.grep(+*))это треугольное сокращение числа элементов в каждой строке (которое некоторые языки называют scan). (0,|...)добавляет ноль к этому списку.
  • .flat.kvсоздает индексированный список всех элементов матрицы. .flatmap: { $^a % .[0] xx ?$^b }плоские карты по модулю каждого индекса по количеству столбцов в массиве (.[0] количество элементов в первой строке), реплицированные самим элементом, интерпретируются как логическое значение. Таким образом, ненулевые элементы реплицируются один раз, а нулевые элементы реплицируются ноль раз (то есть удаляются).
Шон
источник
1

Python + SciPy, 79 байт

я думаю встроенные модули не были запрещены

from scipy.sparse import*
A=csr_matrix(input())
print A.data,A.indptr,A.indices

Принимает ввод в формате [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Карл Напф
источник
1

Джапт , 31 27 байт

Принимает ввод как массив массивов и возвращает массив массивов.

[Uc f U®£X©NpYÃZèÃå+ iT NÅ]

Протестируйте это ( -Qпометьте только для визуализации)

объяснение

Неявный ввод массива U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Для первого sub = -array мы сглаживаем ( c), Uа затем фильтруем ( f) его, удаляя любые элементы Falsey (т. Е. 0s)
[1,1,1,1,1,1,1,1,1]

U®         Ã

Мы собираемся создать другие 2 подмассива одновременно, сопоставляя их U.

£     Ã

Мы отображаем каждый элемент (под-массив) в U

X©

Xявляется текущим элементом текущего подмассива и ©является логическим AND ( &&), поэтому, если Xне верно (не ноль), следующая часть не будет выполнена.

NpY

В Japt Nэто массив, содержащий все входные данные, поэтому здесь, если Xэто правда, мы помещаем ( p) индекс ( Y) текущего элемента в N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

Вернемся к карте основного массива, и для каждого элемента ( Z) мы получим количество элементов в этом подмассиве, которые являются истинными (не нулевыми).
[3,3,3]

å+

Кумулятивно уменьшить этот массив путем суммирования.
[3,6,9]

iT

Вставьте ( i) 0 в индекс 0, чтобы завершить второй под-массив.
[0,3,6,9]

NÅ

Для окончательного подмассива мы просто отрезаем Nот 1-го элемента.
[0,1,2,0,1,2,0,1,2]

мохнатый
источник
Я просто запустил другие примеры, и это работает
Pureferret