使用Java 8函數式編程生成字母序列

2015-09-28 14:54:08

在 Java 8 中使用函數式編程生成字母序列是一個很大的挑戰。Lukas Eder 愉快地接受了這個挑戰，他將告訴我們如何使用 Java 8 來生成ABC的序列——當然，肯定不是一種蹩腳的方式。

我被 Stack Overflow 上網友“mip”提的一個有趣的問題給難住了。該問題是：

我正在尋找一種生成下列字母序列的方式：
 
A, B, C, ..., Z, AA, AB, AC, ..., ZZ.

大家應該能夠很快認出這是 Excel spreadsheet 的頭部，準確的樣子如下：

到現在為止，沒有一個答案是使用 Java 8 的函數式編程實現的，因此我接受此挑戰。我將使用 jOOλ，因為 Java 8 的 Stream API 提供的功能不足以完成該任務（我承認我錯了——非常感謝 Sebastian 對這個問題的有趣解答）。

首先，我們用函數的方式分解這個算法。我們所需要的組件有：

1、一個（可重復）的字母表。

2、一個上界，例如想生成多少個字母。如要求生成序列ZZ，那上界就是2。

3、一種將字母表中的字母與先前生成的字母聯合成一個笛卡爾積（cartesian product）的方法。

讓我們看一下代碼：

1、生成字母表

我們可以這樣寫入字母表，如：

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

但這很差勁。我們使用 jOOλ 代替：

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

上面的代碼生成從字符 A 到 Z 的封閉區間（Java-8-Stream-speak 是包含上邊界的），然后將字符映射成字符串，***將其轉換為列表。

目前為止，一切都很好。現在：

2、使用上邊界：

要求的字符序列包括：

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

但是我們應該很容易想到擴展該需求，能生成如下字符序列，或者更多：

1	`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() 的本質與命令式編程（imperative programming）中的嵌套循環類似。

3、合并字母到一個笛卡爾積中

這是最棘手的部分：我們需要合并字符及出現的次數。因此，我們將使用如下的流：

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() 保證在流中的順序是從“左至右”的，不需要 fold 函數來關聯。

另一方面，這是一個共容易懂的詞匯：foldLeft() 僅代表一條循環的命令。循環的“起源”（即循環的初始化值）是一個完整的字母表（Seq.seq(alphabet)）。現在，在范圍 [1..length-1] 中的值生成一個笛卡爾積（crossJoin()），產生一個新的字母表，然后我們將每個合并的字母再組成一個單獨的字符串（t.v1 與 t.v2）。

這就是整個過程。

將上面的內容合并到一起

下面是一個簡單的打印 A .. Z, AA .. ZZ, AAA .. ZZZ 到控制臺的程序：

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

不用說，這個算法比之前的函數式算法會快很多。

原文鏈接： jaxenter 翻譯： ImportNew.com - paddx
譯文鏈接： http://www.importnew.com/16727.html

責任編輯：王雪燕來源： ImportNew - paddx

Java 函數式編程