//Autor: Artur Czekalski (Sator)  www.epokaY.net/artur  artur@epokaY.net
//Liczenie wyznacznika macierzy
#include <stdio.h> //printf
#include <windows.h> //GetTickCount()
//---------------------------------------------------------------------------
const int gWymiar = 11; //liczba wierszy i kolumn w macierzy
double Mat[gWymiar*gWymiar]; //macierz
//---------------------------------------------------------------------------
inline bool PermLexSuccSelf(int N, int *P)
{
 //Ustala następnika permutacji w kolejności leksykogrficznej tzn. t[i]<t[i+1]
 //N - rozmiar permutacji
 //P - tablica z daną permutacją
 //! Wynik zapisywany jest z powrotem do tablicy P
 if (N <= 1) return false;
 int i = N-2,  j = N-1,  w,  k;

 while (i >= 0 && P[i+1] < P[i]) --i; //znajdź pierwszy od prawej, który psuje porządek rosnący
 if (i == -1) return false; //ostatnia permutacja

 while (j > i && P[j] <= P[i]) --j; //znajdź element pierwszy od prawej > P[i]
 if (j == i) return false; //to nie jest permutacja

 w = P[i];  P[i] = P[j];  P[j] = w; //zamień P[i] z P[j]

 k = i + (N-i-1) / 2;
 for (j=i+1; j<=k; ++j) //zapisz w odwrotnej kolejności: od i+1 do n
  {w = P[j];  P[j] = P[N+i-j];  P[N+i-j] = w;
  }
 return true; //Jest następnik
}
//---------------------------------------------------------------------------
inline int LInwersji(int N, int *P)
{
 //Podaje liczbę inwersji w permutacji P; np. 3,1,4,2 ma 3 inw.: (3,1),(3,2),(4,2)
 int i,  j,  LInw = 0;
 for (i=0; i<N-1; ++i)
  for (j=i+1; j<N; ++j)
   if (P[i] > P[j]) ++LInw;
 return LInw;
}
//--------------------------------------------------------------
inline double DetMacierz(int Wymiar, double *M)
{//Liczy wyznacznik macierzy M ze wzoru
 if (Wymiar <= 1) return 0.0;

 double Suma = 0.0,  Iloczyn;  int i;
 int *P = new int[Wymiar]; //permutacja
 for (i=0; i<Wymiar; ++i) P[i] = i; //pierwsza permutacja
 //---------------------------
 do
  {Iloczyn = M[P[0]];
   for (i=1; i<Wymiar; ++i) Iloczyn *= M[ Wymiar*i + P[i] ];
   if ((LInwersji(Wymiar, P) % 2) == 0) //parzysta liczba inwersji
    Suma += Iloczyn;
   else
    Suma -= Iloczyn;
  }
 while (PermLexSuccSelf(Wymiar, P));

 delete[] P;
 return Suma;
}
//===========================================================================
int main(int, char* [])
{int i, czas;  double w;
 //---Spr.1
 Mat[0]=1; Mat[1]=2; Mat[2]=3; Mat[3]=4;
 printf("Spr. Det st. 2 = %f\n", DetMacierz(2, Mat));
 //---Spr.2
 Mat[ 0]=2; Mat[ 1]= 9; Mat[ 2]= 9; Mat[ 3]= 4;
 Mat[ 4]=2; Mat[ 5]=-3; Mat[ 6]=12; Mat[ 7]= 8;
 Mat[ 8]=4; Mat[ 9]= 8; Mat[10]= 3; Mat[11]=-5;
 Mat[12]=1; Mat[13]= 2; Mat[14]= 6; Mat[15]= 4;
 printf("Spr. Det st. 4 = %f\n", DetMacierz(4, Mat));
 //---
 for (i=0; i<gWymiar*gWymiar; ++i)
  Mat[i] = i+1 - (i % 3) - (i % 5) + (i % 10);
 w = 0.0;  for (i=0; i<gWymiar*gWymiar; ++i) w += Mat[i]; 	 
 //---
 for (i=0; i<gWymiar*gWymiar; ++i)
  {printf("%4.0f ", Mat[i]);
   if (i%gWymiar==gWymiar-1) printf("\n");
  }
 printf("Suma wyrazow = %f\n", w);
 //---Test
 czas = GetTickCount();
 w = DetMacierz(gWymiar, Mat);
 czas = GetTickCount() - czas;
 printf("Wyznacznik st. %d = %f\n", gWymiar, w);
 printf("MinGW Dev. Studio C++ 2.05 (GCC 3.4.2): Czas=%d", czas);
 getchar();  return 0;
}