Codegolf Hafnian

22

Задача состоит в том, чтобы написать codegolf для гафнианской матрицы . Хафниан 2n-симметричной 2nматрицы Aопределяется как:

введите описание изображения здесь

Здесь S 2n представляет множество всех перестановок целых чисел от 1до 2n, то есть [1, 2n].

Ссылка на википедию говорит о матрицах смежности, но ваш код должен работать для любых вещественно симметричных входных матриц.

Для тех, кто интересуется приложениями Hafnian, ссылка mathoverflow обсуждает еще кое-что.

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

Входная матрица всегда квадратная и будет максимум 16 на 16. Нет необходимости иметь возможность обрабатывать пустую матрицу или матрицы нечетного измерения.

Ссылочная реализация

Вот пример кода Python от Mr. Xcoder.

from itertools import permutations
from math import factorial

def hafnian(matrix):
    my_sum = 0
    n = len(matrix) // 2
    for sigma in permutations(range(n*2)):
        prod = 1
        for j in range(n):
            prod *= matrix[sigma[2*j]][sigma[2*j+1]]
        my_sum += prod
    return my_sum / (factorial(n) * 2 ** n)


print(hafnian([[0, 4.5], [4.5, 0]]))
4.5
print(hafnian([[0, 4.7, 4.6, 4.5], [4.7, 0, 2.1, 0.4], [4.6, 2.1, 0, 1.2], [4.5, 0.4, 1.2, 0]])
16.93
print(hafnian([[1.3, 4.1, 1.2, 0.0, 0.9, 4.4], [4.1, 4.2, 2.7, 1.2, 0.4, 1.7], [1.2, 2.7, 4.9, 4.7, 4.0, 3.7], [0.0, 1.2, 4.7, 2.2, 3.3, 1.8], [0.9, 0.4, 4.0, 3.3, 0.5, 4.4], [4.4, 1.7, 3.7, 1.8, 4.4, 3.2]])
262.458

Вики-страница теперь (2 марта 2018 г.) была обновлена ​​ShreevatsaR, чтобы включить другой способ вычисления гафнианского. Было бы очень интересно увидеть этот гольф.

user202729
источник
5
Я думаю, что это будет легче переварить с неофициальным объяснением гафнианского. Примерно так: возьмите все подмножества n элементов матрицы, где их n индексов строк и n столбцов индексов образуют разбиение 1..2n, возьмите произведение каждого из них, сложите их и масштабируйте сумму.
xnor

Ответы:

9

R , 150 142 127 119 байт

function(A,N=nrow(A),k=1:(N/2)*2)sum(apply(gtools::permutations(N,N),1,function(r)prod(A[cbind(r[k-1],r[k])])))/prod(k)

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

Использую тот же трюк, который я обнаружил, играя в гольф по этому ответу, чтобы проиндексировать матрицу P, и @Vlo предложил подход, чтобы полностью удалить forцикл для -6 ​​байт!

Чтобы создать новый тестовый пример, вы можете сделать matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T).

Объяснение: (код тот же; он использует цикл, applyа не forцикл, но логика в остальном идентична).

function(A){
N <- nrow(A)                   #N = 2*n
k <- 1:(N/2) * 2               #k = c(2,4,...,N) -- aka 2*j in the formula
P <- gtools::permutations(N,N) #all N-length permutations of 1:N
for(i in 1:nrow(P))
 F <- F + prod(A[cbind(P[i,k-1],P[i,k])]) # takes the product of all A_sigma(2j-1)sigma(2j) for fixed i and adds it to F (initialized to 0)
F / prod(k)                    #return value; prod(k) == n! * 2^n
}

Giuseppe
источник
Применить дешевле на 2 байта, что позволяет дополнительно сэкономить 4 байта, объединяя остальные строки. tio.run/##PY6xDoIwEIZ3nsLxzpxiS4ymkYEXYHIjDFDEEKBtSokS47PX4sDw5/… Также довольно интересно, что в base R отсутствует функция перестановки для статистического языка программирования
Vlo
@Vlo очень приятно! мы можем перейти Nи kв аргументы функции , чтобы получить его в одном заявлении, удаление {}и сохранение еще два байта.
Джузеппе
@Giuseppe Дарн постоянно забывает, что вы можете определить их в аргументах функции. Потратил несколько минут, пытаясь выявить эти переменные ...
Vlo
8

Pyth , 24 байта

sm*Fmc@@Qhkek2d{mScd2.pU

Попробуй это здесь!


Старая версия, 35 байт

*c1**FK/lQ2^2Ksm*Fm@@Q@dtyk@dykK.pU

Попробуй это здесь!

Мистер Xcoder
источник
3
В настоящее время лидирует, но вы должны бояться, что ответы желе придут .... :)
Эх, желе точно побьет мой примерно на 10 байтов. Pyth не лучший инструмент для работы
г-н Xcoder
05AB1E выглядит так, как будто он может даже связать Пита (хотите верьте, хотите нет, наконец, матричный вызов, где a[b]достаточно, чтобы конкурировать).
Волшебная Осьминог Урна
@MagicOctopusUrn У меня уже есть решение 05AB1E, которое превосходит Pyth :-) Не собираюсь его публиковать (пока, по крайней мере)
Mr. Xcoder
Это что-то вроде xÍysè<¹sès·<ysè<èlmao? PS У меня 40 байтов, и он не так хорошо работает, так что не стесняйтесь его публиковать, так как я не смогу закончить, прежде чем уйти домой.
Волшебный Осьминог Урна
6

Stax , 23 22 19 17 байт

ü;Y╙◘▌Φq↓ê²╧▐å↑┌C

Запустите и отладьте его онлайн

Соответствующее представление ascii той же программы таково.

%r|TF2/{xsE@i^H/m:*+

Программа страдает от некоторой ошибки округления с плавающей запятой. В частности, он сообщает 33673.5000000011вместо 33673.5. Но я думаю, что точность приемлема, учитывая, что эта программа работает со значениями с плавающей запятой. Это также очень медленно, на пример входов на этой машине уходит почти минуту.

%                             get size of matrix
 r|T                          get all permutations of [0 ... size-1]
    F                         for each, execute the rest of the program
     2/                       get consecutive pairs
       {        m             map each pair... 
        xsE@                      the matrix element at that location
            i^H/                  divided by 2*(i+1) where i=iteration index
                 :*           product of array
                   +          add to running total
рекурсивный
источник
1
Очень впечатляюще!
5

05AB1E , 21 байт

ā<œε2ô{}Ùεε`Isèsè;]PO

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


Старая версия, 32 байта

āœvIg;©Lε·UIyX<èèyXèè}P}Oθ®!/®o/

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

Как это работает?

āœvIg;©Lε·UIyX<èèyXèè}P}Oθ®!/®o/ – Full program. Argument: A matrix M.
ā                                – The range [1 ... len(M)].
 œ                               – Permutations.
  v                    }         – Iterate over the above with a variable y.
   Ig;©                          – Push len(M) / 2 and also store it in register c.
       Lε            }           – For each integer in the range [1 ... ^]:
         ·U                      – Double it and store it in a variable X.
            yX<                  – Push the element of y at index X-1.
           I   è                 – And index with the result into M.
                yXè              – Push the element of y at index X.
                   è             – And index with the result into ^^.
                      P          – Take the product of the resulting list.
                        O        – Sum the result of the mapping.
                         θ       – And take the last element*.
                          ®!     – Take the factorial of the last item in register c.
                             ®o  – Raise 2 to the power of the last item in register c.
                            /  / – And divide the sum of the mapping accordingly.

* – Yeah, this is needed because I mess up the stack when pushing so many values in the loop and not popping correctly ;P
Мистер Xcoder
источник
1
Не шучу èsè, ха ... ха-ха ... Я маленький.
Волшебный Осьминог Урна
@MagicOctopusUrn Исправлено ... Я забыл, что 05AB1E индексируется по 0> _ <
Мистер Xcoder
3

Желе , 19 байт

LŒ!s€2Ṣ€QḅL_LịFHP€S

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

Альтернативная версия, 15 байт, задание после даты

LŒ!s€2Ṣ€QœịHP€S

Желе наконец получил индексирование n-мерного массива.

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

Как это работает

LŒ!s€2Ṣ€QœiHP€S  Main link. Argument: M (matrix / 2D array)

L                Take the length, yielding 2n.
 Œ!              Generate all permutations of [1, ..., 2n].
   s€2           Split each permutation into pairs.
      Ṣ€         Sort the pair arrays.
        Q        Unique; deduplicate the array of pair arrays.
                 This avoids dividing by n! at the end.
           H     Halve; yield M, with all of its elements divided by 2.
                 This avoids dividing by 2**n at the end.
         œị      At-index (n-dimensional); take each pair of indices [i, j] and
                 yield M[i][j].
            P€   Take the product the results corresponding the same permutation.
              S  Take the sum of the products.

19-байтовая версия работает аналогичным образом; он просто должен реализовать œịсебя.

...ḅL_LịFH...    Return value: Array of arrays of index pairs. Argument: M

    L            Length; yield 2n.
   ḅ             Convert each pair of indices [i, j] from base 2n to integer,
                 yielding ((2n)i + j).
     _L          Subtract 2n, yielding ((2n)(i - 1) + j).
                 This is necessary because indexing is 1-based in Jelly, so the
                 index pair [1, 1] must map to index 1.
        F        Yield M, flattened.
       ị         Take the indices to the left and get the element at these indices
                 from the array to the right.
         H       Halve; divide all retrieved elements by 2.
Деннис
источник
3

C (gcc) , 288 285 282 293 292 272 271 байт

  • Сохранение трех байтов путем игры с двумя постинкрементами и для размещения цикла.
  • Сохраненные три байта по пустячному с anothter постинкрементом, перемещая оба переменной инициализации перед ветвью - golfed if(...)...k=0...else...,j=0...до if(k=j=0,...)...else...- и выполнил индекс сдвиг.
  • Требуется одиннадцать байтов для поддержки floatматриц.
  • Сохраненный байт благодаря мистеру Xcoder ; играть в гольф 2*j+++1в j-~j++.
  • Сохраните двадцать байтов, удалив лишнее intобъявление типа переменной и не используя функцию факториала, а вместо этого вычисляя значение факториала, используя уже существующий цикл for.
  • Спас байт, играя S=S/F/(1<<n);в гольф S/=F*(1<<n);.
float S,p,F;j,i;s(A,n,P,l,o,k)float*A;int*P;{if(k=j=0,o-l)for(;k<l;s(A,n,P,l,o+1))P[o]=k++;else{for(p=-l;j<l;j++)for(i=0;i<l;)p+=P[j]==P[i++];if(!p){for(F=p=1,j=0;j<n;F*=j)p*=A[P[2*j]*2*n+P[j-~j++]];S+=p;}}}float h(A,n)float*A;{int P[j=2*n];S=0;s(A,n,P,j,0);S/=F*(1<<n);}

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

объяснение

float S,p,F;                    // global float variables: total sum, temporary, factorial
j,i;                            // global integer variables: indices
s(A,n,P,l,o,k)float*A;int*P;{   // recursively look at every permutation in S_n
 if(k=j=0,o-l)                  // initialize k and j, check if o != l (possible  permutation not yet fully generated)
  for(;k<l;s(A,n,P,l,o+1))      // loop through possible values for current possible  permuation position
   P[o]=k++;                    // set possible  permutation, recursively call (golfed into the for loop)
 else{for(p=-l;j<l;j++)         // there exists a possible permutation fully generated
  for(i=0;i<l;)                 // test if the possible permutation is a bijection
   p+=P[j]==P[i++];             // check for unique elements
  if(!p){                       // indeed, it is a permutation
   for(F=p=1,j=0;j<n;F*=j)      // Hafnian product loop and calculate the factorial (over and over to save bytes)
    p*=A[P[2*j]*2*n+P[j-~j++]]; // Hafnian product
   S+=p;}}}                     // add to sum
float h(A,n)float*A;{           // Hafnian function
 int P[j=2*n];S=0;              // allocate permutation memory, initialize sum
 s(A,n,P,j,0);                  // calculate Hafnian sum
 S/=F*(1<<n);}                  // calculate Hafnian

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

В основе программы лежит следующий генератор перестановок, который просматривает цикл S_n. Все вычисления Hafnian просто основаны на этом - и далее игра в гольф.

j,i,p;Sn(A,l,o,k)int*A;{          // compute every element in S_n
 if(o-l)                          // o!=l, the permutation has not fully been generated
  for(k=0;k<l;k++)                // loop through the integers [0, n)
   A[o]=k,Sn(A,l,o+1);            // modify permutation, call recursively
 else{                            // possible permutation has been generated
  for(p=-l,j=0;j<l;j++)           // look at the entire possible permutation
   for(i=0;i<l;i++)p+=A[j]==A[i]; // check that all elements appear uniquely
  if(!p)                          // no duplicat elements, it is indeed a permutation
   for(printf("["),j=0;j<l        // print
   ||printf("]\n")*0;)            //  the
    printf("%d, ",A[j++]);}}      //   permutation
main(){int l=4,A[l];Sn(A,l,0);}   // all permutations in S_4

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

Джонатан Фрех
источник
1
Здорово иметь ответ C, но, как вы предлагаете, в настоящее время он не соответствует требованиям.
@Lembik Исправлено. Теперь поддерживает floatматрицы.
Джонатан Фрех
2*j+++1эквивалентно j+j+++1, что аналогично тому j-(-j++-1), что мы можем эффективно использовать побитовое дополнение для сохранения байта: j-~j++( Попробуйте онлайн )
Mr. Xcoder
3

R , 84 78 байт

h=function(m)"if"(n<-nrow(m),{for(j in 2:n)F=F+m[1,j]*h(m[v<--c(1,j),v]);F},1)

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

Редактировать: Спасибо Вло за -6 байт.

Кажется, что все здесь реализуют стандартный эталонный алгоритм с перестановками, но я попытался воспользоваться знаниями сообщества, полученными в соответствующей задаче , которая в основном та же самая задача, предназначенная для самого быстрого кода вместо гольфа.

Оказывается, что для языка, который хорош в нарезке матриц (например, R), рекурсивный алгоритм: hafnian(m) = sum(m[i,j] * hafnian(m[-rows and columns at i,j])не только быстрее, но и довольно гольфистский. Вот негольфированный код:

hafnian<-function(m)
{
    n=nrow(m)
    #Exits one step earlier than golfed version
    if(n == 2) return(m[1,2])
    h = 0
    for(j in 2:n) {
        if(m[1,j] == 0) next
        h = h + m[1,j] * hafnian(m[c(-1,-j),c(-1,-j)])
    }
    h
}
Кирилл Л.
источник
Очень хороший ответ. -1 для вызова Ifс круглыми скобками, -4 для использования в Fкачестве инициализированной переменной, -1 для назначения nв if. tio.run/##XU/LCsIwELz7FcFTVtOQl1pf1/…
сентября,
аккуратный! Я бы сказал опубликовать его в тесте скорости, но, возможно, есть еще несколько оптимизаций (например, многопоточность), и хотя R точно не известен своей скоростью, было бы хорошо иметь его там для справки. ,
Джузеппе
Сделайте это в целях тестирования!
Vlo
Я действительно пытался проверить это на скорость, но быстро разочаровался в результате. Самая медленная подача Python в задании на скорость с использованием того же точного алгоритма обрезает матрицу 24x24 за несколько секунд на TIO, но время ожидания истекло. На моей локальной машине он также не отвечал в разумные сроки, даже если ему помогли с напоминанием из пакета «memo» ...
Кирилл Л.
2

Желе , 29 байт

LHµ2*×!
LŒ!s€2;@€€Wị@/€€P€S÷Ç

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

Я думаю, что ;@€€Wị@/€€P€часть, вероятно, может быть проиграна. Нужно вернуться позже, чтобы проверить и добавить объяснение.

dylnan
источник
Идентичен моему решению (кроме J) до игры в гольф . Умы желе думают одинаково ? источник
user202729
Я смог немного уменьшить его, реорганизовав часть, которую вы упомянули, а также деление на 2 и факториал. LḶŒ!s€2ḅL‘ịFZµPS÷JḤ$P$ TIO
миль
@ user202729 ха-ха приятно
Дилнан
@ Майлз Ого, это много сбережений. Я отредактирую его в своем ответе, но это совсем другое дело, поэтому не стесняйтесь
присылать
2

MATL , 29 24 22 байта

Zy:Y@!"G@2eZ{)tn:E/pvs

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

Как это работает

Zy       % Size of (implicit) input: pushes [2*n 2*n], where the
         % input is a 2*n × 2*n matrix. 
:        % Range: gives row vector [1 2 ... 2*n]
Y@       % All permutation of that vector as rows of a matrix
!"       % For each permutation 
  G      %   Push input matrix
  @      %   Push current permutation
  2e     %   Reshape as a 2-row array
  Z{     %   Split rows into a cell array of size 2
  )      %   Reference indexing. With a cell array as index this
         %   applies element-wise indexing (similar to sub2ind).
         %   Gives a row vector with the n matrix entries selected
         %   by the current permutation
  t      %   Duplicate
  n:     %   Number of elements, range: this gives [1 2 ... n]
  E      %   Double, element-wise: gives [2 4 ... 2*n]
  /      %   Divide, element-wise
  p      %   Product
  vs     %   Vertically concatenate and sum
         % End (implicit). Display (implicit)
Луис Мендо
источник
1

Perl 6, 86 байт

{my \n=$^m/2;^$m .permutations.map({[*] .map(->\a,\b{$m[a][b]})}).sum/(2**n*[*] 1..n)}
bb94
источник