Program Permutasi dan Kombinasi dalam bahasa Java

Sedih itu adalah.. Lupa menyimpan program-program lama, yang ternyata  masih diperlukan untuk pekerjaan/penelitian terkini. Mau nangis, masak harus dikoding ulang semua? Koq bisa sih lupa. Rasanya saya rajin back up ke drive, atau dicopy ke hdd. Tapi dicari, ga ada. Programnya mungkin sederhana, anak tingkat II juga pasti bisa. Yaitu tentang Knapsack’s Problem, solusi dengan Brute Force dan Dynamic Programming. Sudah dicustom untuk persoalan Combinatorial Spectrum Auction.  Akan saya gunakan sebagai acuan dasar sebelum masuk ke algoritma Heuristic/Metaheuristic.

Baiklah, saya ulangi kodinganya. Untuk Brute Force, artinya kita harus membangkitkan semua ruang solusi. Dalam hal ini, seluruh kombinasi solusi yang mungkin. Saya awali dengan program kombinasi dasar, sebelum dikustom menjadi kombinasi untuk seluruh bidding dalam spectrum auction.

Bicara kombinasi, apa coba bedanya dengan permutasi? Hayo :). Kalo begitu, saya sajikan kedua program tersebut ya; semoga bermanfaat.  Maaf, semua komentar dalam program dihapus heuheu.. Dan maaf itu indentasinya hilang, jadi rata kiri semua heuheu.. jangan dibully ya! Salah wordpressnya koq.

package Combination;

/**
*
* @author pbasari
*/
public class Permutation {
public static void main(String[] args) {
String str = “ABC”;
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n-1);
}

private void permute(String str, int l, int r) {
if (l == r)
System.out.println(str);
else {
for (int i = l; i <= r; i++) {
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}

public String swap(String a, int i, int j) {
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}

}

package Combination;

/**
*
* @author pbasari
*/
class Combination {

static void Combinatorial(String arr[], String data[], int start,
int end, int index, int r) {
if (index == r) {
for (int j=0; j<r; j++)
System.out.print(data[j]+” “);
System.out.println(“”);
return;
}

for (int i=start; i<=end && end-i+1 >= r-index; i++) {
data[index] = arr[i];
Combinatorial(arr, data, i+1, end, index+1, r);
}
}

static void print(String arr[], int n, int r) {
String data[]= new String [r];
Combinatorial(arr, data, 0, n-1, 0, r);
}

public static void main (String[] args) {
String arr[] = {“A”, “B”, “C”};
for (int r = 1; r <= arr.length; r++) {
int n = arr.length;
print(arr, n, r);
}
}
}