Generare Aranjamente

Aspecte teoretice:

În matemetică, numărul de aranjamente (fără repetiție) a n   ()   elemente luate câte k   ()   se notează cu și se calculează cu formula:

În practică, de multe ori se ajunge la necesitatea de a alege dintr-o mulțime oarecare de obiecte submulțimi care au anumite proprietăți sau de a aranja elementele unei mulțimi într-o numită ordine. Domeniul matematicii care studiază astfel de probleme se numește combinatorică și are importanță pentru teoria probabilităților, logica matematică, teoria numerelor, precum și pentru alte ramuri ale științei și tehnicii. Din această ramură a matematicii fac parte și aranjamentele.

Definiție: Daca este o mulțime cu elemente, atunci submulțimile ordonate ale lui , având fiecare câte elemente, unde , se numesc aranjamente de elemente luate câte .

Numărul aranjamentelor de elemente luate câte se notează și se citește: “aranjamente de luate câte “.

Problemă: Să se determine toate aranjamentele de n elemente luate câte m.

Implementare:

Cod Sursa C++

#include "stdafx.h"
#include<iostream>
#include <conio.h>
 
using namespace std;
 
int st[20],n,k;
 
void init()
{
	int i;
	cout<<"n=";cin>>n;
	cout<<"k=";cin>>k;
	for(i=1;i<=n;i++) 
		st[i]=0;
}
 
void tipar(int p)
{
	int j;
	for(j=1;j<=p;j++)
	cout<<st[j]<<" ";
	cout<<endl;
}
 
int valid(int p)
{
	int i,ok;
	ok=1;
	for(i=1;i<p;i++)
	if(st[p]==st[i]) 
		ok=0;
	return ok;
}
 
int solutie(int p)
{
	return (p==k);
}
 
void bkt(int p)
{
	int val;
	for (val=1;val<=n;val++)
	{
		st[p]=val;
		if (valid(p))
		if(solutie(p))
			tipar(p);
		else
			bkt(p+1);
	}
}
 
void main()
{
	init();
	bkt(1);
	system("pause");
}

Cod Sursa PASCAL

{generarea aranjamentelor}

program aranjamente;  {iterativ}
type stiva=array [1..10] of integer;
var st:stiva;
ev,ass:boolean;
n,k,p:integer;

procedure init(k:integer;
var st:stiva);
begin
st[k]:=0;
end;

procedure succesor(var ass:boolean;var st:stiva;k:integer);
begin
if st[k]<n then
begin st[k]:=st[k]+1;
ass:=true;
end
else
ass:=false;
end;

procedure valid(var ev:boolean; var st:stiva; k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do
if st[i]=st[k] then
ev:=false;
if (st[k]<0) and (st[k-1]<0) then
ev:=false;
end;

function solutie(k:integer):boolean;
begin
solutie:=(k=p);
end;

procedure tipar;
var i:integer;
begin
for i:=1 to p do write (st[i]);
writeln;
end;

begin;
write (‘n:=’);
readln (n);
write (‘p:=’);
readln (p);
k:=1;init(k,st);
while k>0 do
begin
repeat
succesor (ass,st,k);
if ass then valid(ev,st,k);
until (not ass) or (ass and ev);
if ass then
if solutie(k) then tipar
else
begin
k:=k+1;
init(k,st)
end
else k:=k-1;
end;
readln;
end.

Rezultat: