Hasilkan Kombinasi di Java

1. Perkenalan

Dalam tutorial ini, kita akan membahas solusi dari masalah k-kombinasi di Java .

Pertama, kita akan membahas dan menerapkan algoritma rekursif dan iteratif untuk menghasilkan semua kombinasi dengan ukuran tertentu. Kemudian kami akan meninjau solusi menggunakan pustaka Java yang umum.

2. Ringkasan Kombinasi

Sederhananya, kombinasi adalah bagian dari elemen dari himpunan tertentu .

Tidak seperti permutasi, urutan di mana kita memilih elemen individu tidak menjadi masalah. Sebaliknya, kami hanya peduli apakah elemen tertentu ada dalam pemilihan.

Misalnya dalam permainan kartu, kita harus membagikan 5 kartu dari paket yang terdiri dari 52 kartu. Kami tidak tertarik dengan urutan 5 kartu yang dipilih. Sebaliknya, kami hanya peduli kartu mana yang ada di tangan.

Beberapa masalah mengharuskan kami mengevaluasi semua kemungkinan kombinasi. Untuk melakukan ini, kami menghitung berbagai kombinasi.

Banyaknya cara berbeda untuk memilih elemen “r” dari himpunan elemen “n” dapat diekspresikan secara matematis dengan rumus berikut:

Oleh karena itu, jumlah cara untuk memilih elemen dapat bertambah secara eksponensial dalam kasus terburuk. Oleh karena itu, untuk populasi besar, tidak mungkin untuk menghitung pilihan yang berbeda.

Dalam kasus seperti itu, kami dapat secara acak memilih beberapa pilihan perwakilan. Proses tersebut dinamakan sampling .

Selanjutnya, kami akan meninjau berbagai algoritme untuk mencantumkan kombinasi.

3. Algoritma Rekursif untuk Menghasilkan Kombinasi

Algoritme rekursif biasanya bekerja dengan mempartisi masalah menjadi masalah serupa yang lebih kecil. Proses ini terus berlanjut hingga kita mencapai kondisi penghentian yang juga merupakan kasus dasar. Kemudian kami menyelesaikan kasus dasar secara langsung.

Kami akan membahas dua cara untuk membagi tugas memilih elemen dari satu set. Pendekatan pertama membagi masalah dalam hal elemen dalam himpunan. Pendekatan kedua membagi masalah dengan melacak elemen yang dipilih saja.

3.1. Partisi berdasarkan Elemen di Seluruh Set

Mari bagi tugas memilih elemen "r" dari item "n" dengan memeriksa item satu per satu. Untuk setiap item dalam set, kita bisa memasukkannya ke dalam pemilihan atau mengecualikannya.

Jika kita memasukkan item pertama, maka kita perlu memilih elemen “r - 1 ″ dari item “ n - 1 ″ yang tersisa . Di sisi lain, jika kita membuang item pertama, maka kita perlu memilih elemen "r" dari sisa item " n - 1" .

Ini dapat diekspresikan secara matematis sebagai:

Sekarang, mari kita lihat implementasi rekursif dari pendekatan ini:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else if (start <= end) { data[index] = start; helper(combinations, data, start + 1, end, index + 1); helper(combinations, data, start + 1, end, index); } }

The helper Metode membuat dua panggilan rekursif untuk dirinya sendiri. Panggilan pertama menyertakan elemen saat ini. Panggilan kedua membuang elemen saat ini.

Selanjutnya, mari kita tulis generator kombinasi menggunakan metode helper ini :

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n-1, 0); return combinations; }

Dalam kode di atas, metode generate menyiapkan panggilan pertama ke metode helper dan meneruskan parameter yang sesuai.

Selanjutnya, panggil metode ini untuk menghasilkan kombinasi:

List combinations = generate(N, R); for (int[] combination : combinations) { System.out.println(Arrays.toString(combination)); } System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);

Saat menjalankan program, kami mendapatkan output berikut:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generated 10 combinations of 2 items from 5

Akhirnya, mari kita tulis kasus uji:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() { SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Sangat mudah untuk mengamati bahwa ukuran tumpukan yang dibutuhkan adalah jumlah elemen dalam set. Jika jumlah elemen dalam kumpulan besar, katakanlah, lebih besar dari kedalaman tumpukan panggilan maksimum, kami akan meluap tumpukan dan mendapatkan StackOverflowError .

Oleh karena itu, pendekatan ini tidak berfungsi jika set input besar.

3.2. Partisi berdasarkan Elemen dalam Kombinasi

Alih-alih melacak elemen dalam set input, kami akan membagi tugas dengan melacak item dalam pemilihan .

Pertama, mari kita urutkan item dalam set input menggunakan indeks "1" hingga " n" . Sekarang, kita dapat memilih item pertama dari item “ n-r + 1 ″ pertama .

Mari kita asumsikan bahwa kita memilih item ke- k . Kemudian, kita perlu memilih item “ r - 1 ″ dari sisa item“ n - k ” yang diindeks“ k + 1 ″ hingga “ n” .

Kami mengekspresikan proses ini secara matematis sebagai:

Selanjutnya, mari kita tulis metode rekursif untuk mengimplementasikan pendekatan ini:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else { int max = Math.min(end, end + 1 - data.length + index); for (int i = start; i <= max; i++) { data[index] = i; helper(combinations, data, i + 1, end, index + 1); } } }

Pada kode di atas, loop for memilih item berikutnya, Kemudian, memanggil metode helper () secara rekursif untuk memilih item yang tersisa . Kami berhenti ketika jumlah item yang dibutuhkan telah dipilih.

Selanjutnya, mari gunakan metode helper untuk menghasilkan pilihan:

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n - 1, 0); return combinations; }

Terakhir, mari kita tulis kasus uji:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() { SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Ukuran tumpukan panggilan yang digunakan oleh pendekatan ini sama dengan jumlah elemen yang dipilih. Oleh karena itu, pendekatan ini dapat bekerja untuk input besar selama jumlah elemen yang akan dipilih kurang dari kedalaman tumpukan panggilan maksimum.

Jika jumlah elemen yang akan dipilih juga banyak, metode ini tidak akan berfungsi.

4. Algoritma Iteratif

Dalam pendekatan iteratif, kita mulai dengan kombinasi awal. Kemudian, kami terus membuat kombinasi berikutnya dari kombinasi saat ini hingga kami membuat semua kombinasi .

Mari kita buat kombinasi dalam urutan leksikografik. Kami mulai dengan kombinasi leksikografi terendah.

Untuk mendapatkan kombinasi berikutnya dari kombinasi saat ini, kami mencari lokasi paling kanan dalam kombinasi saat ini yang dapat ditambah. Kemudian, kami menaikkan lokasi dan membuat kombinasi leksikografik serendah mungkin di sebelah kanan lokasi itu.

Mari tulis kode yang mengikuti pendekatan ini:

public List generate(int n, int r) { List combinations = new ArrayList(); int[] combination = new int[r]; // initialize with lowest lexicographic combination for (int i = 0; i < r; i++) { combination[i] = i; } while (combination[r - 1] < n) { combinations.add(combination.clone()); // generate next combination in lexicographic order int t = r - 1; while (t != 0 && combination[t] == n - r + t) { t--; } combination[t]++; for (int i = t + 1; i < r; i++) { combination[i] = combination[i - 1] + 1; } } return combinations; }

Selanjutnya, mari kita tulis kasus uji:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() { IterativeCombinationGenerator generator = new IterativeCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Sekarang, mari kita gunakan beberapa pustaka Java untuk menyelesaikan masalah.

5. Library Java Menerapkan Kombinasi

Sejauh mungkin, kita harus menggunakan kembali implementasi perpustakaan yang ada daripada meluncurkan milik kita sendiri. Di bagian ini, kita akan menjelajahi pustaka Java berikut yang mengimplementasikan kombinasi:

  • Apache Commons
  • Jambu biji
  • CombinatoricsLib

5.1. Apache Commons

The CombinatoricsUtils class from Apache Commons provides many combination utility functions. In particular, the combinationsIterator method returns an iterator that will generate combinations in lexicographic order.

First, let's add the Maven dependency commons-math3 to the project:

 org.apache.commons commons-math3 3.6.1 

Next, let's use the combinationsIterator method to print the combinations:

public static void generate(int n, int r) { Iterator iterator = CombinatoricsUtils.combinationsIterator(n, r); while (iterator.hasNext()) { final int[] combination = iterator.next(); System.out.println(Arrays.toString(combination)); } }

5.2. Google Guava

The Sets class from Guava library provides utility methods for set-related operations. The combinations method returns all subsets of a given size.

First, let's add the maven dependency for the Guava library to the project:

 com.google.guava guava 27.0.1-jre 

Next, let's use the combinations method to generate combinations:

Set
    
      combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
    

Here, we are using the ImmutableSet.of method to create a set from the given numbers.

5.3. CombinatoricsLib

CombinatoricsLib is a small and simple Java library for permutations, combinations, subsets, integer partitions, and cartesian product.

To use it in the project, let's add the combinatoricslib3 Maven dependency:

 com.github.dpaukov combinatoricslib3 3.3.0 

Next, let's use the library to print the combinations:

Generator.combination(0, 1, 2, 3, 4, 5) .simple(3) .stream() .forEach(System.out::println);

This produces the following output on execution:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]

More examples are available at combinatoricslib3-example.

6. Conclusion

In this article, we implemented a few algorithms to generate combinations.

Kami juga meninjau beberapa implementasi perpustakaan. Biasanya, kami akan menggunakan ini alih-alih menggulung milik kami sendiri.

Seperti biasa, kode sumber lengkap dapat ditemukan di GitHub.