Permutacje, algorytm Dijkstry

 
#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;
}

#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;
}

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;
  }
}