Генериране на комбинации в Java

1. Въведение

В този урок ще обсъдим решението на проблема с k-комбинациите в Java .

Първо ще обсъдим и внедрим рекурсивни и итеративни алгоритми, за да генерираме всички комбинации от даден размер. След това ще прегледаме решенията, използвайки общи библиотеки на Java.

2. Общ преглед на комбинациите

Най-просто казано, комбинацията е подмножество от елементи от даден набор .

За разлика от пермутациите, редът, в който избираме отделните елементи, няма значение. Вместо това ни интересува само дали даден елемент е в селекцията.

Например, в игра на карти, ние трябва да раздадем 5 карти от пакета, състоящ се от 52 карти. Ние не се интересуваме от реда, в който са избрани 5-те карти. По-скоро ни интересува само кои карти присъстват в ръката.

Някои проблеми изискват да оценим всички възможни комбинации. За да направим това, ние изброяваме различните комбинации.

Броят на различните начини за избор на „r“ елементи от набора от „n“ елементи може да бъде изразен математически със следната формула:

Следователно броят на начините за избор на елементи може да нарасне експоненциално в най-лошия случай. Следователно за големи популации може да не е възможно да се изброят различните селекции.

В такива случаи можем на случаен принцип да изберем няколко представителни селекции. Процесът се нарича вземане на проби .

След това ще разгледаме различните алгоритми, за да изброим комбинации.

3. Рекурсивни алгоритми за генериране на комбинации

Рекурсивните алгоритми обикновено работят, като разделят даден проблем на подобни по-малки проблеми. Този процес продължава, докато достигнем крайното състояние, което е и основният случай. След това решаваме директно базовия случай.

Ще обсъдим два начина за подразделяне на задачата за избор на елементи от набор. Първият подход разделя проблема по отношение на елементите в множеството. Вторият подход разделя проблема, като проследява само избраните елементи.

3.1. Разделяне по елементи в целия комплект

Нека разделим задачата за избор на елементи „ r“ от „ n“ елементи, като инспектираме елементите един по един. За всеки елемент от набора можем или да го включим в селекцията, или да го изключим.

Ако включим първия елемент, тогава трябва да изберем „r - 1 - елементи от останалите„ n - 1 ″ елементи . От друга страна, ако изхвърлим първия елемент, тогава трябва да изберем елементите „ r“ от останалите елементи „ n - 1“ .

Това може да се изрази математически като:

Сега нека да разгледаме рекурсивното изпълнение на този подход:

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); } }

Най- помощник метод дава два рекурсивни повиквания към себе си. Първото повикване включва текущия елемент. Второто повикване отхвърля текущия елемент.

След това нека напишем генератора на комбинации, използвайки този помощен метод:

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

В горния код методът генерира първото извикване на помощния метод и предава съответните параметри.

След това нека извикаме този метод за генериране на комбинации:

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);

При изпълнение на програмата получаваме следния изход:

[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

И накрая, нека напишем тестовия случай:

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

Лесно е да се забележи, че необходимият размер на стека е броят на елементите в комплекта. Когато броят на елементите в набора е голям, да речем, по-голям от максималната дълбочина на стека на повикванията, ние ще препълним стека и ще получим StackOverflowError .

Следователно този подход не работи, ако входният набор е голям.

3.2. Разделяне по елементи в комбинацията

Вместо да проследяваме елементите от набора от входни данни, ще разделим задачата, като проследим елементите в селекцията .

Първо, нека да подредим елементите във входящия набор, като използваме индекси „1“ до „ n“ . Сега можем да изберем първия елемент от първите „ n-r + 1 ″ елементи.

Нека приемем, че сме избрали k-тия елемент. След това трябва да изберем " r - 1" елементи от останалите " n - k" елементи, индексирани " k + 1" до " n" .

Ние изразяваме този процес математически като:

След това нека напишем рекурсивния метод за изпълнение на този подход:

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); } } }

В горния код цикълът for формира следващия елемент, след което извиква метода helper () рекурсивно, за да избере останалите елементи . Спираме, когато е избран необходимия брой елементи.

След това нека използваме помощния метод за генериране на селекции:

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

И накрая, нека напишем тестов случай:

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

Размерът на стека повиквания, използван от този подход, е същият като броя на елементите в селекцията. Следователно този подход може да работи за големи входове, стига броят на елементите, които трябва да бъдат избрани, да е по-малък от максималната дълбочина на стека на повикванията.

Ако броят на елементите, които трябва да бъдат избрани, също е голям, този метод няма да работи.

4. Итеративен алгоритъм

При итеративния подход започваме с първоначална комбинация. След това продължаваме да генерираме следващата комбинация от текущата, докато генерираме всички комбинации .

Нека генерираме комбинациите в лексикографски ред. Започваме с най-ниската лексикографска комбинация.

За да получим следващата комбинация от текущата, ние намираме най-дясното местоположение в текущата комбинация, която може да бъде увеличена. След това увеличаваме местоположението и генерираме възможно най-ниската лексикографска комбинация вдясно от това местоположение.

Нека напишем кода, който следва този подход:

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; }

След това нека напишем тестовия случай:

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

Сега, нека използваме някои Java библиотеки за решаване на проблема.

5. Java библиотеки, изпълняващи комбинации

Доколкото е възможно, трябва да използваме повторно съществуващите библиотечни внедрения, вместо да пускаме собствените си. В този раздел ще разгледаме следните библиотеки на Java, които изпълняват комбинации:

  • Apache Commons
  • Гуава
  • 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.

Прегледахме и няколко внедрения на библиотеки. Обикновено бихме ги използвали, вместо да търкаляме свои.

Както обикновено, пълният изходен код може да бъде намерен в GitHub.