# Shkenca > Informatikë dhe Internet > Arti i programimit >  Kombinacionet - të gjitha nënbashkësitë e mundshme të një bashkësie

## 3rror21

do doja t'ju beja edhe nje pyetje tjeter nqs ka mundesi te me ndihmoni...
jam duke bere nje program te vogel per te gjetur te gjithe nen bashkesite e 
  X numrave qe futen (input) pastaj duhet qe programi te nxjerri te gjithe nen bashkesite e atyre X numrave... por per kete me duhet nje funksion qe sja kam edhe aq shume idene se si ta formuloj...!
do doja ndonje mendim nga ju cunimartum edspace etj.etj..
faleminderit

----------


## edspace

Nuk e kuptoj se çfarë kërkon të bësh. Shpjegohu me hollësisht. 
Çfarë gjuhe duhet përdorur?  C++?

----------


## 3rror21

atehere programi duhet ne C(ansi C):
programi funksionon keshtu kur exekutohet:

kompjuteri te pyet sa numra do te fusesh:
perdoruesi shtyp nje numer cfaredo..psh:4
kompjuteri te kerkon te gjithe numrat nje pas nje:
psh:
2
5
6
4
7
dhe pas ketyre 5 numrave qe mund te jene edhe me shume (X numra) 
te nxjerr te gjitha nen bashkesite e ketyre numrave..
psh :i ngrysur: 2,6,4,7,);(5,6,4,7,);(2,5,4,7);(2,5,6,4);(2,5,6,4,  7,);(edhe bashkesia boshe).
atehere me duhet nje funksiopn qe te beje ketop nene bashkesite..
faleminderit
ciao

----------


## Clauss

shiko, nqs se kam kuptuar gabim, problemi tend eshte i thjeshte, teorikisht te pakten. bashkesite qe thua jane thjesht kombinacionet e numurave [ x, y, z ... n] qe permbajne numrin y. domethene nga gjithe kombinaci9onet e mundshme hiq gjithe kombinacionet qe spermbajne numrin y. keto jane bashkesite e tua. gjithmone nqs se kam kuptuar gabim. 
mbase ka menyre me te "zgjuar" po mua kjo me vjen ne mendje tani. dal ta shikoj e do te te them. peace

----------


## 3rror21

eshte puna duhet nje funksion rekursiv per te bere te gjitha nen bashkesite e mundshme te elementeve  [x,y,z,....,n],prandaj eshte edhe pak e veshtire ta formulosh...
thnx cheers

----------


## edspace

Nuk kam kohe te bej dicka vete por shiko kete faqe 
http://answers.google.com/answers/threadview?id=67058

edhe kete qe ka dicka te ngjashme ne java
http://www.merriampark.com/comb.htm

----------


## cunimartum

E fillova dicka dje por per nja nje jave do jem shume i zene.
Duhet te kesh parasysh qe eshte shume e veshtire kjo qe kerkon te besh.
Minimumi duhet t'ja kesh pak idene algoritmeve dhe te lexosh te gatshme
Disa algoritme mund ti gjesh ketu:
http://www.theory.cs.uvic.ca/~cos/dis/programs.html

----------


## werewolf

une di nje qe gjen te gjitha nenbashkesite e mundeshme te  X numrave te pare ( 1....X )
per x numra qe fut vete nga Inputi nuk di ndonje, dhe nuk mund te merrem tani se jam shume i zene, po deshe te shkruaj ate dhe provoje mos e modifikon vete qe te punoj me x numra qe fut ti!  bye!

----------


## 3rror21

cuna faleminderit per pergjigjet
werewolf ma dergo njehere ate se ma ha mendja se e modifikoj 
flm edhe nje here
ciao

----------


## edspace

Nuk ka rendesi se cfare numra/shkronja jep perdoruesi. 
psh: Perdoruesi shkruan 4 shkronjat A B C D dhe keto shkronja i fusim ne nje vektor. 
------------------
| A | B | C | D |
------------------

Funksioni qe do gjeje kombinimet formon nje vektor 2-dimensional me permasa
[X. Y] ku X eshte numri i te gjitha kombinimeve te mundshme dhe Y eshte numri i elementeve qe duhen kombinuar. Ne shembullin tone X = 4 ndersa Y = 4! ( prodhimi faktorial i 4) = 4 * 3 * 2 * 1 = 24

Per 4 elemente, vektori 2-dimensional do dukej keshtu:
1 2 3 4
1 2 4 3
1 3 2 4 
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4 
2 3 4 1
2 4 1 3
2 4 3 1
3 2 1 4
3 2 4 1
3 1 2 4 
3 1 4 2
3 4 2 1
3 4 1 2
4 2 3 1
4 2 1 3
4 3 2 1 
4 3 1 2
4 1 2 3
4 1 3 2

Tani kemi 2 vektorë, njerin me elementet ABCD dhe te dytin me kombinimet e numrave 1234. 
Per te prodhuar kombinimet e ABCD mjafton te krijojme 2 unaza (for loop). 

for int i nga 0 deri ne 23 
------ for int j nga 0 deri ne 3
------------ printo elementet[ kombinimet[i, j] - 1 ] 
------ printo \n; 

Kjo do nxjerre ne ekran vektorin e kombinimeve por numrat do jene zevendesuar me elementet qe fut perdoruesi. Pra 1 do zevendesohet me A, 2 me B, 3 me C, 4 me D

A B C D
A B D C
A C B D 
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D 
B C D A
B D A C
B D C A
C B A D
C B D A
C A B D 
C A D B
C D B A
C D A B
D B C A
D B A C
D C B A 
D C A B
D A B C
D A C B

Pra ideja eshte qe nuk ka rendesi se cfare fut perdoruesi ne fillim sepse kombinimet mund te krijohen gjithnje me numrat 1-X dhe pastaj numrat te perdoren si tregues (index) per vektorin(array) e elementeve.

----------


## edspace

Gjeta kodin rekursiv ketu dhe e modifikova qe te punoje me vlerat qe fut perdoruesi. 

Menyra qe permenda me lart kerkon qe te zeme shume memorje me nje vektor (array) te kombinimeve. Ne kodin me poshte nuk i ruajme kombinimet por thjesht i printojme ato ne ekran.

- Pyesim perdoruesin per nje numer N
- Formojme array Value[N]  dhe Elementet[N] dhe i mbushim me 0
- Kerkojme N numra nga perdoruesi dhe i fusim ato ne array Elementet
- Therasim funksionin rekursiv

Programi punon por ki parasysh se ka rritje faktoriale. 

Ja dhe kodi ne ANSI C:


```

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

void visit (int);

int level = -1;
int N;
int *Value;
int *Elementet;

int main(void)
{
    int i;
    
    printf ("Sa numra do te perdoresh? ");  
    scanf ("%d", &N);
    printf ("\n");

    Value = malloc (N * sizeof (int));
    Elementet = malloc (N * sizeof (int));
    
    for (i=0; i < N; i++){
        Value[i] = 0;
        Elementet[i] = 0;
    }
    
    for (i=0; i < N; i++){
        printf ("> ");  
        scanf ("%d", &Elementet[i]);
        printf ("\n");
    }

    visit(0);

    return 0;
}


void visit (int k)
{
    int i;
    
    Value[k] = ++level;
    if (level == N)
    {
        for (i=0; i < N; i++) {
            printf ("%d ", Elementet[ Value[i] - 1]);
        }
        printf ("\n");
    }
    else
        for (i = 0; i < N; i++)
            if (Value[i] == 0) 
                visit(i);
            
    level--;
    Value[k] = 0;

} 



```

----------


## werewolf

Permutacionet e (X1, ...., Xn) duhen apo nenbashkesite se nuk po marr vesh gje???????!!!!!

----------


## werewolf

permutazionet i ben ai i edspace!
Nese te duhen te gjitha  nenbashkesite implemento ne  c ( a ku ta di une) kete:

Sott( n , i , sol )
{
   if ( i==n)  then print(sol)
   else 
         sol[i+1] = 0
   Sott ( n ,i+1 ,sol )
   sol[i+1] = 1
   Sott ( n, i+1, sol)
  }
      sol eshte nje vektor me n elemente  (n := numri i elementeve qe fut ti)      
      nese sol[i] = 1 elementi ben pjese ne nenbashkesi, perndryshe jo!

    Nuk pata kohe ta bej ne C po eshte e thjeshte per tu bere. per ta bere te gjej nenbashkesite e elementeve qe fut ti modifikoje duke perdorur te njejten menyre si edspace.     
veri ne nje vektor V elementet dhe nese sol[i]= 1 stampo elementin V[i].
keshtu gjen gjithe nenbashkesite e mundeshme!
bye

----------


## edspace

Kerkesa nuk ishte shume e qarte por une e kuptova sikur duheshin te gjitha kombinimet e mundshme te disa elementeve, pra permutacionet. Mund te kem qene gabim.

----------


## 3rror21

cuna rrofshit per pergjigjet
nuk duheshin permutazionet por nen bashkesite megjithate ai programi me ndihmoi shume edspace.e kam modifikuar ca po ska dale tamam ajo qe duhej do provoj njehere ate rrugen qe tha werewolf-i tek programi i edspace 
edhe nje here faleminderit
ja kalofshi mire

----------


## noop

Me poshte eshte nje variant i thjeshte per te listuar gjithe nenbashkesite e nje bashkesie.
Per te kuptuar algoritmin duhen pasur parasysh disa gjera:
-Numri i nenbashkesive eshte 2^n, ku n eshte kardinali i bashkesise
-Per te gjeneruar nenbashkesite bridhen me radhe numrat 0..2^n

Per me shume shikoni kodin me poshte.


_#include <stdio.h>
int main(){
int intsize=sizeof(int);
//m elemente
int m =6;
//qe jane
int elems[]={23,24,25,26,45,52};
//numri i nenbashkesive eshte 2^n
int noofsubsets = 1<<m;

printf("m :%d 2m :%d \n",m,noofsubsets);
//qe duan bredhur me radhe
for(int i=0;i<noofsubsets;i++){
        //mjafton te shikosh paraqitjen binare te i per te pare se cilet elemente jane ne nenbashkesine e i
        printf("{");
        for(int j=0;j<intsize*8 && j<m;j++){
                if((i & (1<<j))!=0)
                        printf("%d,",elems[j]);

        }
        printf("}\n");

}_

----------


## 3rror21

noop rrofsh lal po s'eshte ajo qe kerkoj.
sa per cunat e tjere faleminderit edhe njehere.
ndoshta sjam shpjeguar mire me pare por me duheshin te gjitha nenbashkesite
psh:fusim tre numra
>2
>3
>4

dhe comp. duhet te nxjerre:
(2),(3),(4),
(2,3),(2,4),(3,4),
(2,3,4),(boshe)

jo vetem me dy shifra kombinimet por edhe me nje ,edhe me tre 
derisa te jete numri qe fut.
psh;fusim 7 numra
duhet te nxjerrti te gjitha nen bashkesite nga  me 1 shifer me 2 shifra e deri me shtate shifra.

ndoshta jam bere pak i bezdisshem por e kam provuar me te pakten 20 menyra
dhe skam nxjerre gje ne drite....
prandaj edhe ju drejtova juve...
ja kalofshit mire 
bye

----------


## Clauss

mua me duket se ajo eshte zgjidhja. gabim, nuk me duket, eshte zgjidhja. shikoje me mire, ajo eshte e ska tjeter me te paster/thjeshte. ajo qe duhet te besh ti tani eshte te jape numrat , ne vend ti printosh, ti shkruash ne nje **p, dhe pastaj te printosh vetem ata qe kane numrin X. 
urime noop. peace

----------


## noop

3error21,

ne fakt te gjitha nenbashkesite merreshin parasysh.
Vetem se i kisha lene fikse numrin e elementeve dhe leximin nga tastiera se kujtova se doje ta beje vete.
Ngaqe kam perdorur int nr maximal i elementeve qe mund te lexohet eshte 16 (varet nga platforma ne fakt) . Mgjate nr i nenbashkesive te 16 elem eshte 65536 keshtu qe mund te mjaftoje. Nqse jo perdor long.
Po ta kompilosh do ta shikosh qe dhe varianti i vjeter punon shume mire.
Mgjate ketu poshte e bera dhe leximin nqse te duhet.




```
#include <stdio.h>

#define MAXSIZE = 16
int main(){
int intsize=sizeof(int);
//m elemente
int m ;
//qe jane

//int elems[]={23,24,25,26,45,52};
#include <stdio.h>

#define MAXSIZE  16
int main(){
int intsize=sizeof(int);
//m elemente
int m ;
//qe jane

//int elems[]={23,24,25,26,45,52};
int elems[MAXSIZE];
printf("Numri i elementeve  ");
scanf("%d", &m);
int ii=0;
while (ii<m){

        scanf("%d",&elems[ii++]);
}
//numri i nenbashkesive eshte 2^n
int noofsubsets = 1<<m;

printf("m :%d 2m :%d \n",m,noofsubsets);
//qe duan bredhur me radhe
for(int i=0;i<noofsubsets;i++){
        //mjafton te shikosh paraqitjen binare te i per te pare se cilet elemente jane ne nenbashkesine e i
        printf("{");
        for(int j=0;j<intsize*8 && j<m;j++){
                if((i & (1<<j))!=0)
                        printf("%d,",elems[j]);

        }
        printf("}\n");

}
```

----------


## 3rror21

ej noop faleminderit per pergjigjen.
Kur e pashe programin per here te pare si vura shume rendesi se nuk kuptoja  simbolin "<<" ...
megjithate pastaj e provova dhe e bera ne menyre te allocuar
faleminderit edhe cuna ve te tjere jeni te gjithe 1-sha..
shpresoj te behem edhe une si ju...
ja kalofshi mire dhe urime....
bye bye

----------

