Я наткнулся на интересный вопрос переполнения стека пользователем «mip» . Вопрос был:
Я ищу способ генерации буквенной последовательности:
1A, B, C, ..., Z, AA, AB, AC, ..., ZZ.
Это можно быстро распознать как заголовки электронной таблицы Excel, которая делает именно это:
До сих пор ни один из ответов не использовал функциональное программирование на Java 8, которое я принял за вызов. Мы собираемся использовать jOOλ , потому что Java 8 Stream API не предлагает достаточно функциональных возможностей для этой задачи .
Но сначала давайте разберем алгоритм функциональным образом. Нам нужны эти компоненты:
- (Воспроизводимое) представление алфавита
- Верхняя граница, т.е. сколько букв мы хотим произвести. Запрошенная последовательность переходит к
ZZ
, что означает, что верхняя граница будет 2 - Способ объединения каждой буквы алфавита с ранее созданными комбинированными буквами в декартовом произведении
Давайте посмотрим на некоторый код:
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 . |