Рекурсивный определитель 2х2

17

Определитель матрицы 2 на 2

a b
c d

дается ad - bc.

Учитывая матрицу цифр с размерами 2 n на 2 n , n ≥ 1, выведите результат, полученный путем рекурсивного вычисления определителя каждого субблока 2 на 2, пока мы не достигнем одного числа.

Например, учитывая вход

3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

После одного шага мы получаем:

(3*9 - 1*5)    (4*6 - 1*2)    =    22  22
(5*7 - 3*9)    (5*3 - 8*9)         8  -57

И повторяя еще раз, мы получаем:

(22*-57 - 22*8) = -1430

Следовательно, вывод должен быть -1430.

правила

  • Элементы матрицы всегда будут однозначными целыми числами, то есть от 0 до 9.
  • Вы можете вводить данные в любом удобном формате списка или строки, если не выполняется предварительная обработка данных. Поскольку матрица всегда квадратная, вы можете принять ввод как один одномерный список вместо двухмерного списка, если хотите.
  • Ввод может быть через ввод функции, STDIN, аргумент командной строки или ближайшую альтернативу.
  • Вывод должен быть одним целым числом для функции вывода, STDOUT или ближайшей альтернативой. Вы не можете вывести одно целое число в списке или матрице.
  • Вы можете использовать встроенные детерминанты и методы матричной манипуляции, если ваш язык поддерживает их.
  • Ваш алгоритм должен работать теоретически для любого корректного ввода.
  • Применяются стандартные правила игры в гольф .

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

Следующие тесты приведены в виде списков в стиле Python:

[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8

(Спасибо @ MartinBüttner за помощь в решении этой проблемы)

code-golf arithmetic linear-algebra matrix Sp3000
источник
3
Интересный факт: я провел несколько экспериментов по этому вопросу, и есть удивительно большое количество двоичных матриц с ненулевым рекурсивным определителем. Для размеров 2x2, 4x4, 8x8, 16x16, мы получаем 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832 матрицы с ненулевым определителем, что составляет соответственно 28,88%, соответственно 28,28%, соответственно 28,28%, соответственно 28,28%.
Мартин Эндер
@ MartinBüttner: я получаю 6, 22560, 10160459763342013440, ... что соответствует A055165 .
Чарльз
@ Чарльз, странно, я проверю свой код
Мартин Эндер
@ MartinBüttner: Возможно, мы просто вычисляем две разные вещи?
Чарльз
@ Чарльз Рассмотрим матрицу [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. Полный определитель этого равен нулю, поскольку он имеет две одинаковые строки. Следовательно, эта матрица является единственной (то есть необратимой) матрицей 4 × 4, поэтому она не учитывается A055165. Тем не менее, «рекурсивный» определитель, обсуждаемый здесь, является 1*1-1*0==1. В обратном направлении матрица [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]имеет «рекурсивный» определитель 0*0-0*0==0. Однако его полный определитель должен быть ненулевым, потому что его строки - это просто строки единичной матрицы в другом порядке; и он считается A055165.
Джепп Стиг Нильсен

Ответы:

8

J 21 25 байт

0{0{(_2(_2-/ .*\|:)\])^:_

Использование:

   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

На каждом шаге мы разрезаем матрицу до 2 на 2 и вычисляем каждый определитель, что приводит к входной матрице следующего шага. Мы повторяем этот процесс до тех пор, пока результат не изменится (последний элемент - сам определитель). Конвертируем конечный результат в скаляр с 0{0{.

Попробуйте это онлайн здесь.

randomra
источник
Попытался использовать для этого функцию тайлинга Cut, но не смог сыграть в нее так далеко, как ваша версия. 29 байт: (2 2$2)&(-/ .*;._3^:(2^.#@])) попробуйте онлайн!
Ион
4

Mathematica, 52 40 байт

Спасибо Мартину Бюттнеру за сохранение 12 байтов.

Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&

объяснение

BlockMap[f,expr,n]разделить exprна подсписки размера nи карты fна каждом подсписках. BlockMap[Det,#,{2,2}]&разбить входной массив на 2 * 2 блока и вычислить их детерминанты.

Прецедент

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)
njpipeorgan
источник
1
Я написал эталонную реализацию в Mathematica, обсуждая идею вызова со Sp3000, и это 40 байтов. Хотя он очень похож на ваш, поэтому я дам вам время, чтобы найти его самостоятельно, если хотите. :)
Мартин Эндер
@ MartinBüttner Я потерпел неудачу. :(
njpipeorgan
1
Вы можете избежать [[1,1]]с Trи Nestс //.:Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&
Мартин Эндер
@ MartinBüttner На самом деле, я придумал //. Идея при чтении ответа в J, но застрял в поиске хорошего способа сопоставления массива. : P
njpipeorgan
не стесняйтесь использовать мое решение, чтобы обновить свой ответ
Мартин Эндер,
3

Желе, 20 17 байт

s€2s2U×¥/€ḅ-µL¡SS

Попробуйте онлайн! или проверьте все тестовые случаи одновременно .

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

s€2s2U×¥/€ḅ-µL¡SS  Main link. Input: M (matrix)

s€2                Split each row of M into pairs.
   s2              Split the result into pairs of rows.
        /€         Reduce each pair...
       ¥             by applying the following, dyadic chain:
     U                 Reverse each pair of the left argument (1st row).
      ×                Multiply element-wise with the right argument (2nd row).
          ḅ-       Convert each resulting pair from base -1 to integer.
                   This maps [a, b] -> b - a.
            µ      Turn the previous links into a monadic chain. Begin a new one.
             L     Yield the length of the input.
              ¡    Execute the previous chain L times.
                   log2(L) times would do, but who's counting?
               SS  Sum twice to turn the resulting 1x1 matrix into a scalar.
Деннис
источник
2

Haskell , 93 86 байт

РЕДАКТИРОВАТЬ: Спасибо @Laikoni за сокращение этого целых 7 байтов!

f[[a,b],[c,d]]=a*d-b*c
f m|let l=[take,drop]<*>[div(length m)2]=f[f.($b<$>m)<$>l|b<-l]

Я не знал, что вы можете поместить оператор let перед =, и я никогда не привык к этим операторам монады. Еще раз спасибо @Laikoni

Старая версия:

f[[a,b],[c,d]]=a*d-b*c
f m=f[[f$a$map b m|a<-l]|b<-l]where h=length m`div`2;l=[take h,drop h]

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

Эта функция возвращается сама по себе двумя различными способами. Сначала сопоставление с образцом перехватывает базовый случай: матрицу 2x2 и выполняет вычисление. Я использую это для вычисления в рекурсивном случае, вызывая функцию с генерируемой мной матрицей 2x2, в которой есть рекурсивные решения. Эта матрица генерируется путем итерации дважды по массиву функций, каждый из которых разбивает список пополам. Я применяю его к строкам простым вызовом и применяю к столбцам с помощью map.

user1472751
источник
Вместо where h=length m`div`2;l=[take h,drop h], вы можете использовать f m|let l=[take,drop]<*>[length m`div`2]=. map b mможет быть b<$>mи [f$a$b<$>m|a<-l]может быть сокращено до f.($b<$>m)<$>l. Всего 86 байт: [ tio.run/… Попробуйте онлайн!]
Лайкони
1

Python, 166 байт

def f(m):l=len(m)/2;g=lambda x,y:[(s[:l],s[l:])[x]for s in(m[:l],m[l:])[y]];return f(g(0,0))*f(g(1,1))-f(g(0,1))*f(g(1,0)) if l>1 else m[0][0]*m[1][1]-m[1][0]*m[0][1]

Это проходит все предоставленные тесты. m должен быть двумерным массивом (как в тестовых примерах), g выбирает подматрицу.

Базиль-генри
источник
1

Пиф, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Тестирование

Он состоит из двух частей: M-F*VG_Hпереопределяет функцию gдля вычисления определителя матрицы два на два. Это сохраняет байты, хотя мы используем его только один раз, потому что он распаковывает две строки.

Другая часть - это большое сокращение, которое мы называем log_2( len( input() ) )временем. К сожалению, выполнение шага сокращения матрицы 1 на 1 приводит к тому, что результат будет заключен в список, поэтому мы не получаем фиксированную точку. Редукция в основном просто разбивает матрицу, чтобы получить матрицы 2 на 2, а затем применяет g.

FryAmTheEggman
источник
1

MATL , 26 30 байт

`tnX^teHHhZC2Ih2#Y)pwp-tnq

Ввод - это двумерный массив со строками, разделенными ;, то есть

[3 1 4 1; 5 9 2 6; 5 3 5 8; 9 7 9 3]

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

`             % do...while loop
  tnX^te      %   reshape into square matrix. Implicitly asks for input the first time
  HHhZC       %   transform each 2x2 block into a column
  2Ih2#Y)     %   push matrix with rows 2,3, and also matrix with remaining rows (1,4)
  pwp-        %   multiplications and subtraction to compute the 2x2 determinants
  tnq         %   condition of do...while loop: is number of elements greater than 1?
              % implicitly end loop
              % implicitly display
Луис Мендо
источник
1

Perl 5 , 120 + 1 ( -a) = 121 байт

while($#F){@r=();for$i(@o=0..($l=sqrt@F)/2-1){push@r,$F[$k=$i*$l*2+2*$_]*$F[$k+$l+1]-$F[$k+$l]*$F[$k+1]for@o}@F=@r}say@F

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

Принимает ввод как список разделенных пробелом чисел.

Xcali
источник
0

ES6, 91 байт

(a,x=0,y=0,w=a.length)=>(w>>=1)?f(a,x,y,w)*f(a,x+w,y+w,w)-f(a,x,y+w,w)*f(a,x+w,y,w):a[x][y]

Простое рекурсивное решение.

Нил
источник
0

R 111 байтов

f=function(m)"if"((n=nrow(m))-2,f(matrix(c(f(m[x<-1:(n/2),x]),f(m[y<-x+n/2,x]),f(m[x,y]),f(m[y,y])),2)),det(m))

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

Принимает ввод в виде матрицы R (которая преобразуется функцией в заголовке).

Giuseppe
источник
0

Groovy, 221 189 байт (на данный момент мог бы использовать Java)

f={x->b=x.size();c=b/2-1;a=(0..c).collect{i->(0..c).collect{j->z=x.toList().subList(i*2,i*2+2).collect{it.toList().subList(j*2,j*2+2)};z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Старая дрянная версия, которая также может быть Java (221 байт):

f={x->b=x.size();a=new int[b/2][b/2];for(i=0;i<b-1;i+=2){for(j=0;j<b-1;j+=2){z=x.toList().subList(i,i+2).collect{it.toList().subList(j,j+2)};a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Ungolfed код:

f=
{x->
  b=x.size();
  int[][]a=new int[b/2][b/2];
  for(i=0;i<b-1;i+=2) {
    for(j=0;j<b-1;j+=2) {
      z=x.toList().subList(i,i+2).collect{
        it.toList().subList(j,j+2)
      };
      a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];
    }
  }
  a.size()==1
    ?
      a:f(a)
}
Урна волшебного осьминога
источник