Permutacje, algorytm Dijkstry

Piszę program wypisujący w konsoli wszystkie permutacje danego ciągu znaków. Działa dla ciągu o długości do 7, przy 7 program się zawiesza, prawdopodobnie przez Stack Overflow. Sam nie dałem rady znaleźć przyczyny tego błędu, może Wam się uda :)

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

typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long uint64;

double silnia(uint16 n) {
  if (n == 0 || n == 1) return 1;
  else if (n == 2) return 2;
  else return n*silnia(n-1);
}

void odbij(uint16 from, char str[], uint16 size) {
  //lustrzane odbicie tablicy char ( abc -> cba )
  char tmp[size];

  int i = 0;
  for (i = from; i < size; i++)
    tmp[from+size-i-1] = str[i];

  for (i = from; i < size; i++)
    str[i] = tmp[i];
}
void permutuj(char basket[], uint16 size, double n, double koniec) {
  //generowanie permutacji zbioru, wykorzystuje Algorytm Dijkstry
  if (n == 0)
  {
    //pierwsza permutacja (ten sam zbior)
    printf("%s\n", basket);
    permutuj(basket, size, n+1, koniec);
  }
  else if (n != koniec)
  {
    int i = 0;
    for (i = size-2; i >= 0; i--)
    {
      //poszukiwanie (od prawej storny) pierwszego elemntu mniejszego niz element wczesniejszy
      if (basket[i] < basket[i+1])
      {
        int j = 0;
        for (j = size-1; j >= 0; j--)
        {
          if (basket[j] > basket[i])
          {
            char tmp = basket[j];
            basket[j] = basket[i];
            basket[i] = tmp;
            break;
          }
        }
        break;
      }
    }

    odbij(i+1, basket, size);
    printf("%s\n", basket);
    permutuj(basket, size, n+1, koniec);
  }
}

int main(void) {

  printf("\n\t>>> PERMUTACJE <<<\n\n> ");

  char str[] = "12345678";
  printf("%s", str);

  printf("\n\nRezultat: \n");
  permutuj( str, strlen(str), 0, silnia( strlen(str) ) );

  return 0;
}

Za dużo rekurencji, nic dziwnego, że masz Stack Overflow. Po pierwsze: silnia da się zrobić ładnie iteracyjnie. Po drugie: funkcję permutuj() też da się przerobić na wersję iteracyjną. Zauważ, że masz tam praktycznie rekurencję ogonową, więc powinno to pójść niemal automatycznie.

Edit I jeszcze jedno: funkcja odbij() ma złożoność pamięciową O(n), a bez problemu da się to zrobić w O(1) pamięci i dwa razy szybciej, jeśli będziesz odwracać w miejscu, bez tymczasowej tablicy.

Rekurencja obowiązkowa - jest to zadanie z listy, w której mamy ćwiczyć rekurencje ;)

EDIT: Wersja iteracyjna działa bezproblemowo, nawet bez zmiany algorytmu odbicia.

Ale algorytm Dijkstry znajduje następną permutację w porządku leksykograficznym iteracyjnie. Ten algorytm nie nadaje się na ćwiczenie rekurencji. Chyba, że to jest inny algorytm, niż ten przedstawiony tutaj. Na jego podstawie implementacja przedstawia się dużo prościej:

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

typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long uint64;

uint64 silnia(uint16 n) {
	uint64 res = 1;
	while (n > 1)
		res *= n--;
	return res;
}

#define SWAP(a, b) { char tmp = tab[(a)]; tab[(a)] = tab[(b)]; tab[(b)] = tmp; }

void next_permutation(char* tab, uint16 N)
{
	assert(N > 0);

	int i = N - 1;
	while (tab[i-1] >= tab[i]) 
		--i;
	if (i < 1)
		return;

	int j = N;
	while (tab[j-1] <= tab[i-1]) 
		--j;
	if (j < 1)
		return;

	// swap values at positions (i-1) and (j-1)
	SWAP(i-1, j-1)

	++i;
	j = N;
	while (i < j)
	{
		SWAP(i-1, j-1)
		i++;
		j--;
	}
}

int main(void) {

	char str[] = "12345678";

	uint16 len = strlen(str);
	uint64 max = silnia(len);

	for (uint64 i = 0; i < max; ++i) {
		printf("%s\n", str);
		next_permutation(str, len);
	}

	getchar();

	return 0;
}

Chyba pozostanę przy iteracji.

btw, zmieniłem odbij()... teraz wygląda tak:

void odbij(uint16 from, int tab[], uint16 size) {
  //lustrzane odbicie tablicy char ( abc -> cba )
  uint16 i;
  for (i = 0; i < (size-from)>>1; i++)
  {
    int tmp = tab[i+from];
    tab[i+from] = tab[size-1-i];
    tab[size-1-i] = tmp;
  }
}

Lepiej, nie? :)