This is an old revision of the document!


Поставка задатка

На улазу се задају природни бројеви N и K који означавају број елемената скупа чије комбинације са понављањем тражимо, односно класу тих комбинација. Након задавања тих параметара, корисник уноси елементе скупа. Програм треба да ради за скупове објеката било којег типа.

Поступак решавања

Сажетак алгоритма

Алгоритам конструкције комбинација са понављањем произвољног скупа заснива се на генерисању комбинација са понављањем скупа природних бројева од 0 до N-1. Нека је А коначан скуп чије комбинације тражимо(|A|=N). Тада можемо успоставити бијективно пресликавање f:A→{0,…,N-1}. Нека је b1b2…bk произвољна k-комбинација са понављањем скупа {0,…,N-1}. Одговарајућа комбинација са понављањем скупа А је f-1(b1b2…bk).

Комбинације са понављањем скупа {0,...,N-1}

Пример

Нека важи да је N=3 и K=3. Комбинације са понављањем скупа {0,1,2} су:

  1. 000
  2. 001
  3. 002
  4. 011
  5. 012
  6. 022
  7. 111
  8. 112
  9. 122
  10. 222

Уопштење

Нека је b1b2…bk једна комбинација са понављањем скупа {0,…,N-1}. Наредну добијамо следећим поступком:

КОРАК 1: Пронаћи највеће s> = са особином да је bs < N - 1 1)
КОРАК 2: Увећати bs за 1
КОРАК 3: Уписати нову вредност bs у свако bt, s < t < k - 1

Провера

Уочимо комбинацију 022 у претходном примеру. КОРАК 1: За s = 0, b0=0 < 2 (Проналак првог десног елемента са леве стране који је мањи од N-1) КОРАК 2: Увећамо b0 за 1. КОРАК 3: Препишемо 1 од b0 до b2 Добијена комбинација са понављањем је 111, што се слаже са примером. Да смо алгоритам применили на последњу комбинацију, 222, не бисмо пронашли ненегативно s, што би значило да наредне комбинације са понављањем нема.

Функција која налази наредну комбинацију са понављањем на основу задате

int sledeca(int *komb, int k, int n){
	int i,s;
	s=k-1;
	while(s>=0 && !(komb[s]<n-1)) s--;
	if(s<0) return 0;
	komb[s]=komb[s]+1;
	for(i=s;i<k-1;i++) komb[i+1]=komb[i];
	return 1;
}

Уколико наредна комбинација постоји, функција враћа 1. У супротном 0.

Програм који ради над произвољним скупом А

У сажетку алгоритма већ је објашњено на који начин проналазимо комбинације са понављањем произвољног скупа А. Наиме, не генеришемо директно његове комбинације, већ налазимо комбинације скупа {0,…,|A|-1}. На основу њих, штампамо тражене. Уместо да одштампамо комбинацију 002, одштампаћемо први елемент скупа А два пута, а затим трећи једном.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int sledeca(int *komb, char **skup, int k, int n){
	int i,s;
	s=k-1;
	while(s>=0 && !(komb[s]<n-1)) s--;
	if(s<0) return 0;
	komb[s]=komb[s]+1;
	for(i=s;i<k-1;i++) komb[i+1]=komb[i];
	return 1;
}
 
void ispis (int komb[],int k,char *skup[],int n){
	int i;
	for(i=0;i<k;i++) printf("%s|",skup[komb[i]]);
	putchar('\n');
}
 
 
main(){
	char **skup;
	int n;
	int k;
	int i;
	int *komb;
	int s;
	char string[50];
	printf("N i K?\n");
	skup=(char**)malloc(n*sizeof(char*));
	komb=(int*)malloc(k*sizeof(int));
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++) {
		scanf("%s",string);
		skup[i]=(char*)malloc(sizeof(string)+1);
		strcpy(skup[i],string);
	}
	printf("Skup\n");
	for(i=0;i<n;i++) printf("%s|",skup[i]);
	putchar('\n');
	printf("Kombinacije sa ponavljanjem klase %d.\n",k);
	for(i=0;i<k;i++) komb[i]=0;
	do ispis(komb,k,skup,n);
	while(sledeca(komb,k,n));
}

Поменута бијекција f је додељивање броја i објекту који уносимо. Њој инверзна функција је проналажење елемента коме је додељен број i.

Начини побољшања програма

Ова верзија третира елементе скупа А као стрингове зато што тако најједноставније можемо учитати целе бројеве, реалне бројеве, знакове и саме стрингове. Међутим, на тај начин се може трошити више меморије него што је потребно. Такође, уколико су објекти чије комбинације са понављањем тражимо реченице, програм није одговарајући. Наредне верзије програма се могу остварити овим напоменама.

1) Пошто индексирање почиње од 0
 
kombinacijesaponavljanjem.1323193733.txt.gz · Last modified: 2011/12/06 18:48 by milos.simic
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki