Generating Combination in Lexicograph Order

Tulisan ini saya buat dalam rangka mempublish tugas yang telah saya buat pada mata kuliah Math diskrit. Saya berharap saran dan tanggapan dari pembaca ^_^.

kombinasi adalah banyaknya cara memilih k buah dari himpunan yang memiliki n elemen tanpa memperhatikan urutan. Suatu subhimpunan yang terbentuk baik secara kombinasi maupun permutasi dapat berupa subhimpunan yang berurutan mulai dari subhimpunan dengan nilai terkecil hingga terbesar, penggolongan Lexicographic, ({123},{132}..{321}) ataupun sebaliknya dan dapat pula tidak teratur.

Sebuah algoritma dapat dibentuk untuk menggenerate permutasi dan kombinasi dari himpunan {1,2,3,…,n} yang dapat didasarkan pada sebuah prosedur untuk membangun subhimpunan dari permutasi dan kombinasi selanjutnya, sehingga subhimpunan pertama tidak mendahului subhimpunan selanjutnya atau dapat dikatakan penggolongan berdasarkan Lexicographic.

Algoritma untuk menggenerate kombinasi r dari sebuah himpunan {1,2,3,..,n} dapat direpresentasikan dengan rangkaian yang berisi elemen didalam subhimpunan yang menaik.Kombinasi r dapat diurutkan menggunakan pengurutan Lexicographic pada rangkaian tersebut.

Kombinasi selanjutnya setelah a 1 ,a 2 ,a 3 ..,a n dihasilkan dengan :

• Letakkan elemen terakhir a i pada rangkaian dimana a i ? n – r + i.
• Kemudian ubah posisi a i dengan a i+1 dan a j dengan a i + j – i +1, untuk j = i +1, i+2, ….,r.

Contoh :
Kombinasi 4 unsur lanjutan yang lebih besar
dari {1,2,5,6} dari himpunan {1,2,3,4,5,6} ?

Jawab :
Syarat terakhir diantara syarat a i dengan a 1 =
1, a 2 = 2 , a 3 = 5, dan a 4 = 6 yaitu a i ? 6 – 4 + i adalah
a 2 = 2. untuk menghasilkan kombinasi-4 selanjutnya
yang lebih besar, tambahkan a 2 dengan 1 unutku
menghasilkan a 2 =3. kemudian a 2 = 3+1 =4 dan a 4 =
3+2 = 5. sehingga kombinasi 4 unsur selanjutnya yang
lebih besar adalah {1,3,4,5}.

Algorithm 2: Generating the Next Largest r-Combination in Lexicographic Order

Procedure next r-combination({a 1 ,a 2 ,a 3 ..,a r } :
proper subset of {1,2,..,n} not equal to {n – r +1,…,n} dengan a 1 < a 2 <…..< a r
i = r
while a i = n – r +1
i = i – 1
a i = a i + 1

 

Ini bentuk source code yang coba saya buat, dengan memakai logika yang hampir sama tetapi tidak menggunakan algoritma yang ada diatas.

#include
#include

main()
{
int pilih,s;
char karakter;
awal:
clrscr();
puts(” ******************************”);
puts(” * PROGRAM GENERATING *”);
puts(” * COMBINATION *”);
puts(” ******************************\n”);

puts(“Dalam program ini anda akan menghitung dan membangkitkan KOMBINASI”);
puts(“r(r=1,2,..,8)suku dari sebuah himpunan s={1,2,3,…,n}”);
puts(” “);
printf(“Masukan Jumlah elemen himpunan S = “);
scanf(“%d”, &s);
printf(“\nMasukan nilai dari r = “);
scanf(“%d”, &pilih);
if(pilih>s)
{
printf(“Maaf pilihan anda tak dilayani. karena nilai r, seharusnya rMaaf permintaan anda tak dilayani “);
printf(“\n karena kelebihan nilai r dari yang sudah ditentukan”);
printf(“\n Anda ingin mengulang(y/t)?\n”);
karakter=getch();
if(karakter==’y’||karakter==’Y’)
goto awal;
else
puts(“\nTerima Kasih ^-^”);
}
}
printf(“\n Anda ingin mengulang(y/t)?\n”);
karakter=getch();
if(karakter==’y’||karakter==’Y’)
goto awal;
else
puts(“\nTerima Kasih ^-^”);
akhir:
getch();
}

kombinasi1n(int x)
{
int a=1;
while(a<=x)
{printf(“\n%d) {%d}”,a,a);
a++;
}
printf(“\nJadi jumlah kombinasi 1 dari %d atau C(%d,1)= %d”,x,x,a-1);

}

 

kombinasi2n(int x)
{
int a,b,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
if(a<b&&a!=b)
{printf(“\n%d) {%d, %d}”,jumlah+1,a,b);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 2 dari %d atau C(%d,2)= %d”,x,x,jumlah);
}

kombinasi3n(int x)
{
int a,b,c,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
for(c=1;c<=x;c++)
if((a<b&&a!=b)&&(a<c&&a!=c)&&(b<c&&b!=c))
{printf(“\n%d) {%d, %d, %d}”,jumlah+1,a,b,c);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 3 dari %d atau C(%d,3)= %d”,x,x,jumlah);
}

kombinasi4n(int x)
{
int a,b,c,d,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
for(c=1;c<=x;c++)
for(d=1;d<=x;d++)
if((a<b&&a!=b)&&(a<c&&a!=c)&&(a<d&&a!=d)&&(b<c&&b!=c)&&(b<d&&b!=d)&&(c<d&&c!=d))
{printf(“\n%d) {%d, %d, %d, %d}”,jumlah+1,a,b,c,d);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 4 dari %d atau C(%d,4)= %d”,x,x,jumlah);
}

kombinasi5n(int x)
{
int a,b,c,d,e,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
for(c=1;c<=x;c++)
for(d=1;d<=x;d++)
for(e=1;e<=x;e++)
if((a<b&&a!=b)&&(a<c&&a!=c)&&(a<d&&a!=d)&&(a<e&&a!=e)&&(b<c&&b!=c)&&(b<d&&b!=d)&&(b<e&&b!=e)&&(c<d&&c!=d)&&(c<e&&c!=e)&&(d<e&&d!=e))
{printf(“\n%d) {%d, %d, %d, %d, %d}”,jumlah+1,a,b,c,d,e);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 5 dari %d atau C(%d,5)= %d”,x,x,jumlah);
}

 

kombinasi6n(int x)
{
int a,b,c,d,e,f,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
for(c=1;c<=x;c++)
for(d=1;d<=x;d++)
for(e=1;e<=x;e++)
for(f=1;f<=x;f++)
if((a<b&&a!=b)&&(a<c&&a!=c)&&(a<d&&a!=d)&&(a<e&&a!=e)&&(a<f&&a!=f)&&(b<c&&b!=c)&&(b<d&&b!=d)&&(b<e&&b!=e)&&(b<f&&b!=f)&&(c<d&&c!=d)&&(c<e&&c!=e)&&(c<f&&c!=f)&&(d<e&&d!=e)&&(d<f&&d!=f)&&(e<f&&e!=f))
{printf(“\n%d) {%d, %d, %d, %d, %d, %d}”,jumlah+1,a,b,c,d,e,f);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 6 dari %d atau C(%d,6)= %d”,x,x,jumlah);
}

kombinasi7n(int x)
{
int a,b,c,d,e,f,g,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
for(c=1;c<=x;c++)
for(d=1;d<=x;d++)
for(e=1;e<=x;e++)
for(f=1;f<=x;f++)
for(g=1;g<=x;g++)
if((a<b&&a!=b)&&(a<c&&a!=c)&&(a<d&&a!=d)&&(a<e&&a!=e)&&(a<f&&a!=f)&&(a<g&&a!=g)&&(b<c&&b!=c)&&(b<d&&b!=d)&&(b<e&&b!=e)&&(b<f&&b!=f)&&(b<g&&b!=g)&&(c<d&&c!=d)&&(c<e&&c!=e)&&(c<f&&c!=f)&&(c<g&&c!=g)&&(d<e&&d!=e)&&(d<f&&d!=f)&&(d<g&&d!=g)&&(e<f&&e!=f)&&(e<g&&e!=g)&&(f<g&&f!=g))
{printf(“\n%d) {%d, %d, %d, %d, %d, %d, %d}”,jumlah+1,a,b,c,d,e,f,g);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 7 dari %d atau C(%d,7)= %d”,x,x,jumlah);
}

kombinasi8n(int x)
{
int a,b,c,d,e,f,g,h,jumlah=0;

for(a=1;a<=x;a++)
for(b=1;b<=x;b++)
for(c=1;c<=x;c++)
for(d=1;d<=x;d++)
for(e=1;e<=x;e++)
for(f=1;f<=x;f++)
for(g=1;g<=x;g++)
for(h=1;h<=x;h++)
if((a<b&&a!=b)&&(a<c&&a!=c)&&(a<d&&a!=d)&&(a<e&&a!=e)&&(a<f&&a!=f)&&(a<g&&a!=g)&&(a<h&&a!=h)&&(b<c&&b!=c)&&(b<d&&b!=d)&&(b<e&&b!=e)&&(b<f&&b!=f)&&(b<g&&b!=g)&&(b<h&&b!=h)&&(c<d&&c!=d)&&(c<e&&c!=e)&&(c<f&&c!=f)&&(c<g&&c!=g)&&(c<h&&c!=h)&&(d<e&&d!=e)&&(d<f&&d!=f)&&(d<g&&d!=g)&&(d<h&&d!=h)&&(e<f&&e!=f)&&(e<g&&e!=g)&&(e<h&&e!=h)&&(f<g&&f!=g)&&(f<h&&f!=h)&&(g<h&&g!=h))
{printf(“\n%d) {%d, %d, %d, %d, %d, %d, %d, %d}”,jumlah+1,a,b,c,d,e,f,g,h);
jumlah++;
}
printf(“\nJadi jumlah kombinasi 8 dari %d atau C(%d,8)= %d”,x,x,jumlah);
}

atau untuk bentuk dalam notepadnya bisa di download disini {combination}

Source code ini mungkin terlalu sederhana, maka dari itu penulis mengharapkan pengembangan dan tanggapan dari para pembaca supaya source code ini lebih sempurna

By : spyn3t

 

 

2 pemikiran pada “Generating Combination in Lexicograph Order

  1. dah bagus.
    cuma, jangan lupa cantumkan source code yang kamu buat itu pake bahasa pemrograman apa?
    C,C++ ato Java ato Vb ato pascal or something else.
    kan g semua tau klo yang d atas pake bahasa C.
    sekalian kasih orang download dari Tubo C biar orang bisa compile n execute program sendiri.
    ok.thanx.maap klo da salah.
    askum

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s