用java8函数编程生成字母序列

java jax伦敦 教程
2021-01-21 13:42:33
18 0 0

我偶然发现了用户提出的一个有趣的堆栈溢出问题。问题是:我正在寻找一种生成字母序列的方法:

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

这可以很快被识别为Excel电子表格的标题,它正好做到:

到目前为止,没有一个答案使用任何java8函数式编程,我认为这是一个挑战。我们将使用jOOλ,因为java8流API没有为这个任务提供足够的功能。

但是首先,让我们以函数的方式分解算法。我们需要的是这些组件:

  1. 字母的(可再现)表示

  2. 上限,即我们要产生多少个字母。请求的序列转到ZZ,这意味着上限为2

  3. 一种将笛卡尔积中的每个字母与先前生成的组合字母进行组合的方法

让我们看一些代码:

1.生成字母

我们可以这样写字母:

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

但这很low。让我们使用jOOλ生成它:

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

上述产生一“关闭”范围(java8-流发言与包容上限的范围内)的字符之间A和Z,映射字符串和收集它们到一个列表中。

2.使用上限

请求的字符序列包括:

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

但是我们可以轻易地想象将这一要求扩展到产生以下甚至更多的需求。

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

为此,我们将再次使用rangeClosed()

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

这里的想法是为该范围内的每个长度生成一个新的流[1 .. 2],并将这些流展平为一个单个流。flatMap()本质上与命令式编程中的嵌套循环相同。

3.将字母组合成笛卡尔积

这是最棘手的部分:我们需要将每个字母与每个字母组合length一次。为此,我们将使用以下流:

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()与相同reduce(),不同之处在于foldLeft()可以保证在流中从左向右移动,而无需折叠功能具有关联性。

换句话说,更容易理解的词foldLeft()是:命令循环。循环的“种子”,即循环的初始值,是完整的字母(Seq.seq(alphabet))。现在,对于该范围内的每个值[1 .. length-1],我们crossJoin()在到目前为止“已折叠”的字母和一个新字母之间产生一个笛卡尔乘积(),并将每个组合连接成一个新的字符串(t.v1和t.v2)。

结合一切

以下简单程序将所有值从中打印A .. Z, AA .. ZZ, AAA .. ZZZ到控制台:

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

免责声明

对于这种特殊情况,这当然不是最佳算法。一名不知名的用户在Stack Overflow上给出了最好的实现之一:

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

不必说后者比以前的功能算法快得多。

作者介绍

用微信扫一扫

收藏