/*****************************************************************************
 * Program liczy wyznacznik macierzy kwadratowej metoda permutacyjna         *
 * User podaje rozmiar macierzy i jej wspolczynniki po odpaleniu programu    *
 * Permutacje obliczam metoda rekurencyjna: permutuje tablice o 1 krotsza    *
 * po kolei wstawiajac na "obcinany" element wszystkie elementy z tablicy    *
 *****************************************************************************/

#include <stdio.h>
#include <stdlib.h>

/* liczymy wszystkie permutacje; na koncu kazdej wykonujemy liczenie
 * "wkladu" danej permutacji w wyznacznik */
/* co - wskaznik do poczatku aktualnie permutowanej tablicy, calosc - wskaznik
 * do calej tablicy (potrzebne na dnie wywolan rekurencyjnych) */
void permutuj(char *co, char *calosc);
/* majac permutacje liczymy jej wklad w wyznacznik */
/* permutacja - tablica zawierajaca zapisana permutacje */
void oblicz(char *permutacja);
/* potrzebny jest tzw. znak permutacji, czyli czy dana permutacje do
 * wyznacznika dodajemy, czy odejmujemy (w zasadzie zawsze dodajemy, ale
 * mnozac wklad przez +-1) */
/* argument - j.w. */
int znak(char *permutacja);

int **macierz;
int wyznacznik = 0;

int main(void)
{
char *wsp;
int rozm, i = 0, j;

puts("Podaj rozmiar macierzy:");
scanf("%i", &rozm);

/* bloczek instrukcji, zeby tablica 2D zachowywala sie, jak na zwykla
 * tablice 2D przystalo */
macierz = (int**) calloc(sizeof(int*), rozm);
macierz[0] = (int*) calloc(sizeof(int), rozm * rozm);
for (j = 1; j < rozm; ++j) macierz[j] = macierz[0] + rozm * j;


wsp = (char*) calloc(sizeof(char), rozm + 1);    /* rozm + 1, bo dodatkowy */
                                                 /* na konczacy NULL       */
while (i < rozm)                /* wpisujemy wspolczynniki dla permutacji */
  {
  wsp[i] = i + '0';
  ++i;
  }

for (i = 0; i < rozm; ++i)            /* pobieramy wspolczynniki macierzy */
  {
  printf("wiersz %i:\n", i + 1);
  for (j = 0; j < rozm; ++j) scanf("%i", &(macierz[i][j]) );
  }

/* liczymy wyznacznik */
permutuj(wsp, wsp);

/* wypisanie calej macierzy */
for (i = 0; i < rozm; ++i)
  {
  for (j = 0; j < rozm; ++j) printf("%4i ", macierz[i][j]);
  putchar('\n');
  }

/* i wyznacznika */
printf("Wyznacznik: %d\n", wyznacznik);

free(macierz[0]);    /* zwalniamy przydzielona pamiec */
free(macierz);
return 0;
}

void permutuj(char *co, char *calosc)
{
char *zmiana = co, temp;

if (!co[1]) /* przypadek elementarny - jeden element do permutacji */
  {
  oblicz(calosc);  /* zatem liczymy wklad do wyznacznika */
  return;
  }

permutuj(co + 1, calosc); /* najpierw permutujemy niezmienione */
while (zmiana[1]) /* dopoki bedziemy mogli sie przeniesc o 1 dalej */
  {
  temp = *zmiana;   /* przenosimy liczbe z poczatku na jej stare miejsce, */
  *zmiana++ = *co;  /* liczbe z tego starego miejsca o jeden dalej, */
  *co = *zmiana;    /* a ta z kolei liczba idzie na poczatek */
  *zmiana = temp;

  permutuj(co + 1, calosc); /* permutujemy obcinajac poczatkowy element */
  }
temp = *zmiana; /* sprzatamy tablice: ostatni element to ten, ktory przed */
*zmiana = *co;  /* zamieszaniem byl na poczatku, a ten poczatkowy to ten, */
*co = temp;     /* ktory kiedys byl na koncu */
/* sprzatanie po sobie jest konieczne, bo mogloby powodowac (prawie)
 * nieprzewidywalna wedrowke elementow, co burzyloby nam porzadek permutowania
 * (niektore ustawienia by sie powtarzaly) */
}

void oblicz(char *permutacja)
{
int pamiec = znak(permutacja),  /* od razu liczymy znak permutacji */
    i = -1;         /* a dzieki temu w petli bedzie o jedna instrukcje mniej */

/* mnozymy przez siebie elementy a(i,j), gdzie i jest brane po kolei,
 * a j jest wyznaczone przez permutacje */
while (permutacja[++i]) pamiec *= macierz[ i ][ permutacja[i] - '0'];

wyznacznik += pamiec;
}

/* ustalanie znaku permutacji sprowadza sie do policzenia inwersji, czyli
 * takich par, ze mniejsza poprzedza wieksza:
 * dla permutacji (321) 3 poprzedza 1, 3 poprzedza 2 oraz 2 poprzedza 1, czyli
 * sa trzy inwersje */
int znak(char *permutacja)
{
char *wsk;
int inwersje = 0;                   /* poczatkowo nie mamy zadnych inwersji */

while (*permutacja)
  {
  wsk = permutacja + 1;                 /* zaczynamy od nastepnego znaku */
  while (*wsk)                          /* do skonczenia tablicy */
    {
    if (*permutacja > *wsk) ++inwersje; /* liczymy ilosc inwersji */
    ++wsk;                              /* przesuwamy sie o 1 dalej */
    }
  ++permutacja;                         /* liczymy inwersje nastepnej liczby */
  }

/* jesli ilosc inwersji jest parzysta, to (-1)^inwersje = 1, jesli nieparzysta,
 * to (-1)^inwersje = -1 */
return (inwersje % 2) ? -1 : 1;
}