Algoritmo disposizioni semplici e con ripetizione.

[gas89]

Salve a tutti, sono nuovo del forum e stò impazzendo da un bel pò di tempo per cercare di realizzare un algoritmo che visualizzi tutte le disposizioni semplici e con ripetizione, dato n(numero di oggetti) e k(classe), oltre a chiedere se lo si deve risolvere con le ripetizioni o meno.
Sapendo che il numero di disposizioni è dato da n*(n-1)*(n-2)*.....*(n-k+1), io devo realizzare un algoritmo che mi visualizzi tutti i raggruppamenti che si ottengono, magari utilizzando una matrice.
Qualcuno di voi saprebbe aiutarmi? O in precedenza ha fatto qualcosa di simile?
Possibilmente mi servirebbe in c++, ma comunque mi va bene in qualsiasi linguaggio di programmazione, anche in pseudocodifica.
Ringrazio quanti mi aiuteranno e premetto che lo dovrei realizzare al più presto possibile.
Grazie a tutti.

P.S. Dimenticavo di dire che l'algoritmo deve essere iterativo e non ricorsivo!!!

[Vincenzo1968]

Il seguente programma in C, utilizza una lista concatenata per memorizzare le permutazioni:

//typedef int Item;
typedef char Item;

typedef struct tagPermutations
{
	Item * a;
	struct tagPermutations *next;
} Permutations;

Permutations* NewNode(Item *pItem)
{
	Permutations *n;

	n = (Permutations *)malloc(sizeof(Permutations));

	if( n == NULL )
		return NULL;

	n->a = pItem;
	n->next = NULL;

	return n;
}

void Print(Permutations *first, unsigned int nDim)
{
	Permutations *n = first;

	while( n != NULL )
	{
		for(unsigned int k = 0; k < nDim; k++)
			//_tprintf(_T("%5d"), n->a[k]);		
			_tprintf(_T("%5c"), n->a[k]);		
		n = n->next;
		printf("\n");
	}
}

void Free(Permutations *first)
{
	Permutations *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1->a);
		free(n1);
		n1 = n2;
	}
}

int Find(Permutations *first, Item *pItem, unsigned int nDim)
{
	Permutations *n = first;
	unsigned int j = 0;

	while( n != NULL )
	{
		for(unsigned int k = 0; k < nDim; k++)
		{
			if ( pItem[k] != n->a[k] )
				break;
			else
				++j;
		}
		if ( j == nDim )
			return 1;
		n = n->next;
		j = 0;
	}

	return 0;
}

Permutations * MakePermutations(Item *pItems, unsigned int nDim, int WithoutRepetition)
{
	register unsigned int i, j;
	Item *pa;
	Item tmp;
	int *p;

	p = (int *)malloc((nDim + 1)*sizeof(int));
	if ( !p )
		return NULL;

	pa = (Item*)malloc(sizeof(Item)*nDim);
	if ( pa == NULL )
		return NULL;

	Permutations *pPerm = NULL, *pFirst = NULL;

	for(i = 0; i < nDim; i++)
	{
		*(pa + i) = *(pItems + i);
		*(p + i) = i;
	}
	*(p + nDim) = nDim;

	pPerm = NewNode(pa);
	if ( !pPerm )
		return NULL;
	pFirst = pPerm;

	i = 1;
	while(i < nDim)
	{
		--*(p + i);
		j = i % 2 * *(p + i);
		tmp = *(pItems + j);         // scambia(array[i], array[j])
		*(pItems + j) = *(pItems + i);
		*(pItems + i) = tmp;

		i = 1;
		while ( !(*(p + i)) )
		{
			*(p + i) = i;
			i++;
		}

		if ( WithoutRepetition && Find(pFirst, pItems, nDim) )
			continue;

		pa = (Item*)malloc(sizeof(Item)*nDim);
		if ( pa == NULL )
			return NULL;
		for(unsigned int k = 0; k < nDim; k++)
			*(pa + k) = *(pItems + k);
		if ( !pPerm )
		{
			pPerm = NewNode(pa);
			if ( !pPerm )
				return NULL;
		}
		else
		{
			pPerm->next = NewNode(pa);
			if ( !pPerm )
				return NULL;
			pPerm = pPerm->next;
		}
		if ( !pFirst )
			pFirst = pPerm;
	}

	free(p);

	return pFirst;
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int nDim;

	Permutations * pPerm = NULL;

	//Item a[] = {1, 2, 1};
	Item a[] = {_T('A'), _T('B'), _T('A'), _T('B')};

	nDim = sizeof(a)/sizeof(a[0]);

	pPerm = MakePermutations(a, nDim, 0);
	_tprintf(_T("Permutazioni:\n"));
	Print(pPerm, nDim);
	Free(pPerm);

	pPerm = NULL;
	pPerm = MakePermutations(a, nDim, 1);
	_tprintf(_T("\nPermutazioni senza ripetizioni:\n"));
	Print(pPerm, nDim);
	Free(pPerm);

	return 0;
}

Nella funzione main inizializziamo un array di char.
Possiamo utilizzare un tipo diverso per l'array; Se vogliamo, per esempio, utilizzare un array di int, cambiamo la definizione di Item da

typedef char Item;

a

typedef int Item;

Nella funzione Print cambiamo il codice di formato da %c a %d; quindi

_tprintf(_T("%5c"), n->a[k]);

diventa

_tprintf(_T("%5d"), n->a[k]);

e, naturalmente, nella funzione main, inizializziamo l'arry con valory interi:

Item a[] = {1, 2, 1};

Il lavoro è svolto dalla funzione MakePermutations che accetta tre parametri: un puntatore alla lista concatenata, un puntatore all'array da permutare e un valore booleano che ci consente di scegliere se vogliamo una permutazione senza ripetizioni o meno.

Nell'esempio vengono prima visualizzate le 24 permutazioni che si ottengono dall'array di quattro elementi ( A, B, A, B ) e, dopo, le sei permutazioni senza ripetizioni:

B A B A
A B B A
B B A A
B A A B
A B A B
A A B B