[LUGOS-PROG] Permutacije

[Ales Casar]

On Fri, 19 Jul 2002, Nejc Skoberne wrote:

> Pred par dnevi sem se zacel uciti C. Trudil sem se, a mi ni uspelo
> napisati programa, ki bi kot input vzel najprej moc mnozice, nato pa
> se posamezne elemente le-te (poljubno stevilo) in bi jo nato
> permutiral in vse permutacije izpisal na ekran.

> Vendar, kot lahko vidite na koncu nisem nasel resitve. A mi lahko kdo
> da kak hint?

Ker imam ravno pri roki en tak program, ki sem ga pred meseci napisal, ga
tukaj prilagam:

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

void Perm(int a[], int n, int k)
  {
    int i, t, j;

    for (i = k; i < n; i++)
      {
	t = a[i];
	a[i] = a[k];
	a[k] = t;
	if (k + 2 < n)
	  Perm(a, n, k + 1);
	else
	  {
	    for (j = 0; j < n; j++)
	      printf(" %d", a[j]);
	    printf("\n");
	  }
	t = a[i];
	a[i] = a[k];
	a[k] = t;
      }
  }


int main(int argn, char *argc[])
  {
    int i, n, *a;

    n = atoi(argc[1]);
    a = (int *) malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
      a[i] = i;
    Perm(a, n, 0);
    return 0;
  }
======================================================================

Kaksnih kontrol pravilnosti delovanja in vhodnih podatkov tukaj ni. Za
prvi parameter program pricakuje stevilo elementov. Elementi so v polju
'a'. Jedro je funkcija 'Perm', ki na 'k'-to mesto po vrsti razvrsti vse se
nerazporejene elemente in potem za vsakega rekurzivno opravi se
permutacije vseh preostalih nerazporejenih elementov.

Program je nastal, ko sem sodelavca zalotil pri vecurnem preucevanju
raznih nerekurzivnih na WWW najdenih algoritmov za permutacije. Ker se je
rekurzije vztrajno izogibal, sem mu hotel pokazati, da prav z rekurzijo
lahko iz nic veliko hitreje napises delujoci program. Sicer me je takrat
kljub vsemu prehitel za nekaj minut, ampak ce upostevamo skupen cas in to,
da se mu na koncu sanjalo ni zakaj in kako tista njegova resitev sploh
deluje...

Ales

-- 
Ales Casar                |  Email:    casar at uni-mb.si
Computer Centre           |  DECnet:   RCUM::ALES
University of Maribor     |  AX.25:    S56SAC @ S50MBR.SVN.EU
SLOVENIA                  |  WWW:      http://www.el.feri.uni-mb.si/~ales/