Статьи

Как использовать функциональное программирование Java 8 для генерации буквенной последовательности

Март 7, 2019

Я наткнулся на интересный вопрос переполнения стека пользователем «mip» . Вопрос был:

Я ищу способ генерации буквенной последовательности:

1
A, B, C, ..., Z, AA, AB, AC, ..., ZZ.

Это можно быстро распознать как заголовки электронной таблицы Excel, которая делает именно это:

превосходить

До сих пор ни один из ответов не использовал функциональное программирование на Java 8, которое я принял за вызов. Мы собираемся использовать jOOλ , потому что Java 8 Stream API не предлагает достаточно функциональных возможностей для этой задачи .

jool-черный Но сначала давайте разберем алгоритм функциональным образом. Нам нужны эти компоненты:

  1. (Воспроизводимое) представление алфавита
  2. Верхняя граница, т.е. сколько букв мы хотим произвести. Запрошенная последовательность переходит к ZZ , что означает, что верхняя граница будет 2
  3. Способ объединения каждой буквы алфавита с ранее созданными комбинированными буквами в декартовом произведении

Давайте посмотрим на некоторый код:

1. Генерация алфавита

Мы могли бы написать алфавит так:

1
List<String> alphabet = Arrays.asList("A", "B", ..., "Z");

но это было бы хромым. Давайте сгенерируем его, используя jOOλ:

1
2
3
4
List<String> alphabet = Seq
    .rangeClosed('A', 'Z')
    .map(Object::toString)
    .toList();

Выше генерирует «закрытый» диапазон ( Java-8-Stream-говорят для диапазона с включительно верхней границей ) символов между A и Z , отображает символы в строки и собирает их в список.

Все идет нормально. Теперь:

2. Использование верхней границы

Запрашиваемая последовательность символов включает в себя:

1
A .. Z, AA, AB, .. ZZ

Но мы могли бы легко представить, чтобы расширить это требование в целом, чтобы произвести следующее или даже больше.

1
A .. Z, AA, AB, .. ZZ, AAA, AAB, .. ZZZ

Для этого мы снова будем использовать rangeClosed() :

1
2
3
4
// 1 = A .. Z, 2 = AA .. ZZ, 3 = AAA .. ZZZ
Seq.rangeClosed(1, 2)
   .flatMap(length -> ...)
   .forEach(System.out::println);

Идея здесь состоит в том, чтобы создать новый поток для каждой отдельной длины в диапазоне [1 .. 2] и объединить эти потоки в один отдельный поток. flatMap() по сути то же самое, что и вложенный цикл в императивном программировании.

3. Объединить буквы в декартовом произведении

Это самая сложная часть: нам нужно объединить каждую букву с каждой length буквы. Для этого мы будем использовать следующий поток:

1
2
3
4
5
Seq.rangeClosed(1, length - 1)
   .foldLeft(Seq.seq(alphabet), (s, i) ->
       s.crossJoin(Seq.seq(alphabet))
        .map(t -> t.v1 + t.v2))
    );

Мы снова используем rangeClosed() для получения значений в диапазоне [1 .. length-1] . foldLeft() — это то же самое, что и foldLeft() reduce() , за исключением того, что foldLeft() гарантированно будет идти «слева направо» в потоке, не требуя ассоциативной функции сворачивания. Уф.

Другими, более понятными словами: foldLeft() — это не что иное, как императивный цикл. «Семя» цикла, то есть начальное значение цикла, представляет собой полный алфавит ( Seq.seq(alphabet) ). Теперь для каждого значения в диапазоне [1 .. length-1] мы производим декартово произведение ( crossJoin() ) между «сложенными» до сих пор буквами и новым алфавитом, и мы объединяем каждую комбинацию в одну новую строку ( t.v1 и t.v2 ).

Это оно!

Объединяя все

Следующая простая программа выводит на консоль все значения из A .. Z, AA .. ZZ, AAA .. ZZZ :

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.List;
 
import org.jooq.lambda.Seq;
 
public class Test {
    public static void main(String[] args) {
        int max = 3;
 
        List<String> alphabet = Seq
            .rangeClosed('A', 'Z')
            .map(Object::toString)
            .toList();
 
        Seq.rangeClosed(1, max)
           .flatMap(length ->
               Seq.rangeClosed(1, length - 1)
                  .foldLeft(Seq.seq(alphabet), (s, i) ->
                      s.crossJoin(Seq.seq(alphabet))
                       .map(t -> t.v1 + t.v2)))
           .forEach(System.out::println);
    }
}

отказ

Это, конечно, не самый оптимальный алгоритм для этого конкретного случая. Одна из лучших реализаций была предоставлена ​​неназванным пользователем в переполнении стека :

01
02
03
04
05
06
07
08
09
10
11
import static java.lang.Math.*;
 
private static String getString(int n) {
    char[] buf = new char[(int) floor(log(25 * (n + 1)) / log(26))];
    for (int i = buf.length - 1; i >= 0; i--) {
        n--;
        buf[i] = (char) ('A' + n % 26);
        n /= 26;
    }
    return new String(buf);
}

Нет необходимости говорить, что последний работает намного быстрее, чем предыдущий функциональный алгоритм.

Ссылка: Как использовать функциональное программирование на Java 8 для генерации буквенной последовательности от нашего партнера по JCG Лукаса Эдера из блога JAVA, SQL и AND JOOQ .
53
Share: