java - 通过从数组中选择来创建排列

Question

我有一个二维数组，用于存储与您在电话键盘上看到的内容相对应的不同字母。

char [][] convert = 
    {   {},
        {'A','B','C'},
        {'D','E','F'},      
        {'G','H','I'},
        {'J','K','L'},
        {'M','N','O'},
        {'P','R','S'},
        {'T','U','V'},
        {'W','X','Y'}
    };

如果我想从二维数组的前 5 行中各取 1 个字母，找出 5 个字母单词的所有可能排列，我该怎么做？我正在考虑递归，但这让我感到困惑。

为了让这个问题更容易理解，这里有一个例子:

一个 3 字母单词的第一个字母来自第 1 行，{'A','B','C'}，第二个字母来自第 3 行，{'G' ,'H','I'}，以及第 6 行的第三个字母 {'P','R','S'}。总共会有 27 种可能的结果:AGP AGR AGS AHP AHR AHS AIP AIR AIS BGP BGR BGS BHP BHR BHS BIP BIR BIS CGP CGR CGS CHP CHR CHS CIP CIR CIS。

Answer 1

首先要观察的是，如果您通过从 5 行中的每一行中选择 3 个字符中的一个来造词，那么您将以总共 3⁵ = 243 个单词结束。无论您如何实现该程序，它最终都必须构建这 243 个单词中的每一个。

递归是一个很好的实现策略，因为它清楚地表明您正在选择第一行中的三个字符之一，并且对于这些选择中的每一个，您继续选择第二行中的三个字符中的一个，等等。

在下面的 Java 程序中，makeWord 的第一个版本是一个递归函数，它在 currentRowIndex 索引的行中选择一个字符并将该字符附加到 字缓冲区。如果这是最后一行，则该单词是完整的，并且会附加到单词列表中。否则，该函数调用自身以处理 currentRowIndex + 1 行。

请注意，wordBuffer 的当前状态一直延续到递归调用。只有从递归调用返回后，我们才会从 wordBuffer 中删除最后一个字符。

makeWord 的第二个版本允许您传递一个行索引数组，指定您要从哪些行中选择字符。例如，要从第 1、3 和 6 行中选择字符，您可以调用:

permuter.makeWord(new int[]{ 1, 3, 6 }, 0);

您可以在 main 方法而不是当前行中替换该调用，这会导致使用第 1 行到第 5 行的字符构建单词:

permuter.makeWord(1, 5);

如果仔细查看 makeWord 方法，您会发现第一个方法在字符串完成时不会递归，而第二个方法会递归一次然后提前返回，因为位置 == indices.length。后一种方法效率稍低，因为它多了一次递归调用，但你可能会发现它更清楚地表达了递归的概念。这是一个品味问题。

import java.util.*;

public class PermuteCharacters {
  char[][] rows = { 
    {},
    {'A','B','C'},
    {'D','E','F'},    
    {'G','H','I'},
    {'J','K','L'},
    {'M','N','O'},
    {'P','R','S'},
    {'T','U','V'},
    {'W','X','Y'}
  };

  StringBuffer wordBuffer = new StringBuffer();
  ArrayList<String> words = new ArrayList<String>();

  void makeWord(int currentRowIndex, int endRowIndex) {
    char[] row = rows[currentRowIndex];
    for (int i = 0; i < row.length; ++i) {
      wordBuffer.append(row[i]);
      if (currentRowIndex == endRowIndex) {
        words.add(wordBuffer.toString());
      } else {
        makeWord(currentRowIndex + 1, endRowIndex);
      }
      wordBuffer.deleteCharAt(wordBuffer.length() - 1);
    }
  }

  void makeWord(int[] indices, int position) {
    if (position == indices.length) {
      words.add(wordBuffer.toString());
      return;
    }
    char[] row = rows[indices[position]];
    for (int i = 0; i < row.length; ++i) {
      wordBuffer.append(row[i]);
      makeWord(indices, position + 1);
      wordBuffer.deleteCharAt(wordBuffer.length() - 1);
    }
  }

  void displayWords() {
    if (words.size() != 0) {
      System.out.print(words.get(0));
      for (int i = 1; i < words.size(); ++i) {
        System.out.print(" " + words.get(i));
      }
      System.out.println();
    }
    System.out.println(words.size() + " words");
  }

  public static void main(String[] args) {
    PermuteCharacters permuter = new PermuteCharacters();
    permuter.makeWord(1, 5);
    permuter.displayWords();
  }
}