使用电话键盘生成 10 位数字

Question

给定一个如下所示的手机键盘：

1 2 3
4 5 6
7 8 9
  0

从1开始可以组成多少个不同的10位数字？限制是从一位数字到下一位数字的移动类似于国际象棋游戏中马的移动。

例如。如果我们是 1 那么下一个数字可以是 6 或 8 如果我们位于 6，则下一个数字可以是 1、7 或 0。

允许重复数字 - 1616161616 是有效数字。

有没有多项式时间算法可以解决这个问题？该问题要求我们只给出 10 位数字的个数，而不一定列出数字。

编辑：我尝试将其建模为一个图表，每个数字都有 2 或 3 个数字作为其邻居。然后我使用 DFS 导航到 10 个节点的深度，然后每次达到 10 的深度时增加数字的计数。这显然不是多项式时间。假设每个数字只有 2 个邻居，则这至少需要 2^10 次迭代。

这里的变量是位数。我已经采取了例如。 10 位数字。它也可以是 n 位数字。

Answer 1

当然可以在多项式时间内完成。这是动态编程或记忆。

在此示例中，我们假设 N（位数）等于 10。

像这样递归地思考：使用从1开始的10位数字可以构造多少个数字？

答案是

[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].

有多少个“从8开始的9位数字” “有吗？嗯，

[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]

等等。当您得到问题“从 X 开始有多少个 1 位数字”（答案显然是 1）时，就达到了基本情况。

当谈到复杂性时，关键的观察是您重用以前计算的解决方案。例如，回答“有多少个从 3 开始的 5 位数字” 可以在回答“有多少个 6-”时使用。从8开始的数字”和“从4开始有多少个6位数字”。这种重用使得复杂性从指数级下降到多项式级。

让我们仔细看看动态编程解决方案的复杂性：

这种实现将按以下方式填充矩阵：

num[1][i] = 1, for all 0<=i<=9   -- there are one 1-digit number starting from X.

for digits = 2...N
    for from = 0...9
        num[digits][from] = num[digits-1][successor 1 of from] +
                            num[digits-1][successor 2 of from] +
                            ...
                            num[digits-1][successor K of from]

return num[N][1]                 -- number of N-digit numbers starting from 1.

该算法只是一次填充一个单元格，并且该矩阵的维度为 10*N，因此以线性时间运行。

---

我凭空写下来的，如有错别字请指正。

Answer 2

我决定解决这个问题并使其尽可能可扩展。该解决方案允许您：

定义您自己的棋盘（手机键盘、棋盘等）

定义您自己的棋子（马、车、象等）；您必须编写具体的类并从工厂生成它。

通过一些有用的实用方法检索几条信息。

这些类如下：

PadNumber：定义电话垫上按钮的类。可以重命名为“Square”以代表棋盘正方形。

ChessPiece：定义所有棋子字段的抽象类。

运动：定义运动方法并允许工厂生成零件的接口。

PieceFactory：生成棋子的工厂类。

Knight：继承自ChessPiece并实现Movement的具体类

PhoneChess：入口类。

驱动程序：驱动程序代码。

好的，代码如下：）

package PhoneChess;

import java.awt.Point;

public class PadNumber {

private String number = "";
private Point coordinates = null;

public PadNumber(String number, Point coordinates)
{
    if(number != null && number.isEmpty()==false)
        this.number = number;
    else
        throw new IllegalArgumentException("Input cannot be null or empty.");

    if(coordinates == null || coordinates.x < 0 || coordinates.y < 0)
        throw new IllegalArgumentException();
    else
        this.coordinates = coordinates;

}

public String getNumber()
{
    return this.number;
}
public Integer getNumberAsNumber()
{
    return Integer.parseInt(this.number);
}

public Point getCoordinates()
{
    return this.coordinates;
}
public int getX()
{
    return this.coordinates.x;
}
public int getY()
{
    return this.coordinates.y;
}

}

ChessPiece

package PhoneChess;

import java.util.HashMap;
import java.util.List;

public abstract class ChessPiece implements Movement {

protected String name = "";
protected HashMap<PadNumber, List<PadNumber>> moves = null;
protected Integer fullNumbers = 0;
protected int[] movesFrom = null;
protected PadNumber[][] thePad = null;
}

移动接口：

package PhoneChess;

import java.util.List;

public interface Movement 
{
public Integer findNumbers(PadNumber start, Integer digits);
public abstract boolean canMove(PadNumber from, PadNumber to);
public List<PadNumber> allowedMoves(PadNumber from);
public Integer countAllowedMoves(PadNumber from);
}

PieceFactory

package PhoneChess;

public class PieceFactory 
{
    public ChessPiece getPiece(String piece, PadNumber[][] thePad)
    {
    if(thePad == null || thePad.length == 0 || thePad[0].length == 0)
        throw new IllegalArgumentException("Invalid pad");
    if(piece == null)
        throw new IllegalArgumentException("Invalid chess piece");

    if(piece.equalsIgnoreCase("Knight"))
        return new Knight("Knight", thePad);
    else
        return null;
}
}

Knight 类

package PhoneChess;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public final class Knight extends ChessPiece implements Movement {

/**Knight movements
 * One horizontal, followed by two vertical
 * Or 
 * One vertical, followed by two horizontal
 * @param name
 */

public Knight(String name, PadNumber[][] thePad)
{
    if(name == null || name.isEmpty() == true)
        throw new IllegalArgumentException("Name cannot be null or empty");

    this.name = name;
    this.thePad = thePad;
    this.moves = new HashMap<>();
}


private Integer fullNumbers = null;

@Override
public Integer findNumbers(PadNumber start, Integer digits) 
{
    if(start == null || "*".equals(start.getNumber()) || "#".equals(start.getNumber()) ) { throw new IllegalArgumentException("Invalid start point"); }
    if(start.getNumberAsNumber() == 5) { return 0; } //Consider adding an 'allowSpecialChars' condition
    if(digits == 1) { return 1; };

    //Init
    this.movesFrom = new int[thePad.length * thePad[0].length];
    for(int i = 0; i < this.movesFrom.length; i++)
        this.movesFrom[i] = -1;

    fullNumbers = 0;
    findNumbers(start, digits, 1);      
    return fullNumbers;
}

private void findNumbers(PadNumber start, Integer digits, Integer currentDigits)
{
    //Base condition
    if(currentDigits == digits)
    {
        //Reset
        currentDigits = 1; 
        fullNumbers++; 
        return; 
    }
    if(!this.moves.containsKey(start))
        allowedMoves(start);

    List<PadNumber> options = this.moves.get(start);
    if(options != null)
    {
        currentDigits++; //More digits to be got
        for(PadNumber option : options)
            findNumbers(option, digits, currentDigits);
    }
}

@Override
public boolean canMove(PadNumber from, PadNumber to) 
{
    //Is the moves list available?
    if(!this.moves.containsKey(from.getNumber()))
    {
        //No? Process.
        allowedMoves(from);
    }
    if(this.moves.get(from) != null)
    {
        for(PadNumber option : this.moves.get(from))
        {
            if(option.getNumber().equals(to.getNumber()))
                return true;
        }
    }
    return false;

}

/***
 * Overriden method that defines each Piece's movement restrictions.
 */
@Override
public List<PadNumber> allowedMoves(PadNumber from) 
{
    //First encounter
    if(this.moves == null)
        this.moves = new HashMap<>();


    if(this.moves.containsKey(from))
        return this.moves.get(from);
    else
    {
        List<PadNumber> found = new ArrayList<>();
        int row = from.getY();//rows
        int col = from.getX();//columns

        //Cases:
        //1. One horizontal move each way followed by two vertical moves each way
        if(col-1 >= 0 && row-2 >= 0)//valid
        {
            if(thePad[row-2][col-1].getNumber().equals("*") == false && 
                    thePad[row-2][col-1].getNumber().equals("#") == false)
            {
                found.add(thePad[row-2][col-1]);
                this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
            }

        }
        if(col-1 >= 0 && row+2 < thePad.length)//valid
        {
            if(thePad[row+2][col-1].getNumber().equals("*") == false && 
                    thePad[row+2][col-1].getNumber().equals("#") == false)
            {
                found.add(thePad[row+2][col-1]);
                this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
            }
        }
        if(col+1 < thePad[0].length && row+2 < thePad.length)//valid
        {
            if(thePad[row+2][col+1].getNumber().equals("*") == false && 
                    thePad[row+2][col+1].getNumber().equals("#") == false)
            {
                found.add(thePad[row+2][col+1]);
                this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
            }
        }
        if(col+1 < thePad[0].length && row-2 >= 0)//valid
        {
            if(thePad[row-2][col+1].getNumber().equals("*") == false && 
                    thePad[row-2][col+1].getNumber().equals("#") == false)
            found.add(thePad[row-2][col+1]);
        }
        //Case 2. One vertical move each way follow by two horizontal moves each way

        if(col-2 >= 0 && row-1 >= 0)
        {
            if(thePad[row-1][col-2].getNumber().equals("*") == false && 
                    thePad[row-1][col-2].getNumber().equals("#") == false)
            found.add(thePad[row-1][col-2]);
        }
        if(col-2 >= 0 && row+1 < thePad.length)
        {
            if(thePad[row+1][col-2].getNumber().equals("*") == false && 
                    thePad[row+1][col-2].getNumber().equals("#") == false)
            found.add(thePad[row+1][col-2]);
        }

        if(col+2 < thePad[0].length && row-1 >= 0)
        {
            if(thePad[row-1][col+2].getNumber().equals("*") == false && 
                    thePad[row-1][col+2].getNumber().equals("#") == false)
            found.add(thePad[row-1][col+2]);
        }
        if(col+2 < thePad[0].length && row+1 < thePad.length)
        {
            if(thePad[row+1][col+2].getNumber().equals("*") == false && 
                    thePad[row+1][col+2].getNumber().equals("#") == false)
            found.add(thePad[row+1][col+2]);
        }

        if(found.size() > 0)
        {
            this.moves.put(from, found);
            this.movesFrom[from.getNumberAsNumber()] = found.size();
        }
        else
        {
            this.moves.put(from, null); //for example the Knight cannot move from 5 to anywhere
            this.movesFrom[from.getNumberAsNumber()] = 0;
        }
    }

    return this.moves.get(from);


}

@Override
public Integer countAllowedMoves(PadNumber from) 
{
    int start = from.getNumberAsNumber();

    if(movesFrom[start] != -1)
        return movesFrom[start];
    else
    {
        movesFrom[start] = allowedMoves(from).size();
    }
    return movesFrom[start];
}

@Override
public String toString()
{
    return this.name;
}

}

PhoneChess 入口类

package PhoneChess;


public final class PhoneChess 
{
private ChessPiece thePiece = null;
private PieceFactory factory = null;

public ChessPiece ThePiece()
{
    return this.thePiece;
}

public PhoneChess(PadNumber[][] thePad, String piece)
{
    if(thePad == null || thePad.length == 0 || thePad[0].length == 0)
        throw new IllegalArgumentException("Invalid pad");
    if(piece == null)
        throw new IllegalArgumentException("Invalid chess piece");

    this.factory = new PieceFactory();
    this.thePiece = this.factory.getPiece(piece, thePad);
}

public Integer findPossibleDigits(PadNumber start, Integer digits)
{
    if(digits <= 0)
        throw new IllegalArgumentException("Digits cannot be less than or equal to zero");

    return thePiece.findNumbers(start, digits);
}

public boolean isValidMove(PadNumber from, PadNumber to)
{
    return this.thePiece.canMove(from, to);
}

}

Driver 代码：

public static void main(String[] args) {


    PadNumber[][] thePad = new PadNumber[4][3];
    thePad[0][0] = new PadNumber("1", new Point(0,0));
    thePad[0][1] = new PadNumber("2", new Point(1,0));
    thePad[0][2] = new PadNumber("3",new Point(2,0));
    thePad[1][0] = new PadNumber("4",new Point(0,1));
    thePad[1][1] = new PadNumber("5",new Point(1,1));
    thePad[1][2] = new PadNumber("6", new Point(2,1));
    thePad[2][0] = new PadNumber("7", new Point(0,2));
    thePad[2][1] = new PadNumber("8", new Point(1,2));
    thePad[2][2] = new PadNumber("9", new Point(2,2));
    thePad[3][0] = new PadNumber("*", new Point(0,3));
    thePad[3][1] = new PadNumber("0", new Point(1,3));
    thePad[3][2] = new PadNumber("#", new Point(2,3));

    PhoneChess phoneChess = new PhoneChess(thePad, "Knight");
    System.out.println(phoneChess.findPossibleDigits(thePad[0][1],4));
}

}

Answer 3

这可以在 O(log N) 内完成。将键盘及其上可能的移动视为一个图G(V, E)，其中顶点是可用的数字，边表示哪些数字可以跟随哪个数字。现在，对于每个输出位置i，我们可以形成一个向量Paths(i)，其中包含每个顶点可以到达的不同路径的数量。现在很容易看出给定位置i和数字v，它可以到达的可能路径是可能到达的前面数字的不同路径的总和，或者Paths(i)[v] = sum(Paths(i-1)[v2] * (1 if (v,v2) in E else 0) for v2 in V )。现在，这是前面向量的每个位置乘以邻接矩阵列中的相应位置的总和。因此我们可以将其简化为Paths(i) = Paths(i-1) · A，其中A是图的邻接矩阵。摆脱递归并利用矩阵乘法的结合性，这变成Paths(i) = Paths(1) · A^(i-1)。我们知道路径（1）：我们只有一条路径，到数字1。n

位数字的路径总数是每个数字的路径总和，所以最终算法变成: TotalPaths(n) = sum( [1,0,0,0,0,0,0,0,0,0] · A^(n-1) )

可以计算幂通过在 O(log(n)) 时间内进行平方，给定常数时间乘法，否则 O(M(n) * log(n)) 其中 M( n) 是您最喜欢的 n 位数字的任意精度乘法算法的复杂度。

Answer 4

一个更简单的答案。

#include<stdio.h>

int a[10] = {2,2,2,2,3,0,3,2,2,2};
int b[10][3] = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};

int count(int curr,int n)
{
    int sum = 0;
    if(n==10)
        return 1;
    else
    {
        int i = 0;
        int val = 0;
        for(i = 0; i < a[curr]; i++)
        {
            val = count(b[curr][i],n+1);
            sum += val;
        }
        return sum;
    }
}

int main()
{
    int n = 1;
    int val = count(1,0);
    printf("%d\n",val);
}

庆祝！！

Answer 5

运行时间常数时间解：

#include <iostream>

constexpr int notValid(int x, int y) {
return !(( 1 == x && 3 == y ) || //zero on bottom.
         ( 0 <= x && 3 > x && //1-9
           0 <= y && 3 > y ));
}

class Knight {
    template<unsigned N > constexpr int move(int x, int y) {
        return notValid(x,y)? 0 : jump<N-1>(x,y);
    }

    template<unsigned N> constexpr int jump( int x, int y ) {
        return  move<N>(x+1, y-2) +
            move<N>(x-1, y-2) +
            move<N>(x+1, y+2) +
            move<N>(x-1, y+2) +
            move<N>(x+2, y+1) +
            move<N>(x-2, y+1) +
            move<N>(x+2, y-1) +
            move<N>(x-2, y-1);
    }

public:
    template<unsigned N> constexpr int count() {
        return move<N-1>(0,1) + move<N-1>(0,2) +
            move<N-1>(1,0) + move<N-1>(1,1) + move<N-1>(1,2) +
            move<N-1>(2,0) + move<N-1>(2,1) + move<N-1>(2,2);
    }
};

template<> constexpr int Knight::move<0>(int x, int y) { return notValid(x,y)? 0 : 1; }
template<> constexpr int Knight::count<0>() { return 0; } //terminal cases.
template<> constexpr int Knight::count<1>() { return 8; }


int main(int argc, char* argv[]) {
    static_assert( ( 16 == Knight().count<2>() ), "Fail on test with 2 lenght" );  // prof of performance
    static_assert( ( 35 == Knight().count<3>() ), "Fail on test with 3 lenght" );

    std::cout<< "Number of valid Knight phones numbers:" << Knight().count<10>() << std::endl;
    return 0;
}

Answer 6

方法返回从 1 开始的 10 位数字的列表。计数再次为 1424。

  public ArrayList<String> getList(int digit, int length, String base ){
    ArrayList<String> list = new ArrayList<String>();
    if(length == 1){
        list.add(base);
        return list;
    }
    ArrayList<String> temp;

    for(int i : b[digit]){
        String newBase = base +i;
        list.addAll(getList(i, length -1, newBase ));
    }
    return list;
}

Answer 7

我不确定我是否错过了什么，但阅读问题的描述后我找到了这个解决方案。它的时间复杂度为 O(n)，空间复杂度为 O(1)。

我认为 1 号在拐角处，对吧？在每个角落，您可以移动到其中一侧（从 9 和 3 移动到 4，或从 7 到 1 移动到 6）或“垂直”边之一（从 3 和 1 移动到 8，或从 9 和 7 移动到 2）。因此，角球增加了两个移动：侧向移动和“垂直”移动。这对于所有四个角 (1,3,9,7) 都是如此。

从每一侧，您可以移动到两个角（从 6 移动到 7 和 1，从 4 移动到 9 和 3），也可以到达底部的键 (0)。就这样三个动作。两个角和一个底部。

在底部的键 (0) 上，您可以移动到两侧（4 和 6）。因此，在每一步中，您都会检查先前长度的路径的所有可能结局（即，有多少个结束于角、边、“垂直”或“底部”零键），然后生成新的结局根据前面所说的生成规则进行计数。

• 每个角末端都会添加一条边和一条垂直线。
• 每个侧面末端都会添加 2 个角和一个底部。
• 每个垂直末端都会添加 2 个角。
• 每个底端都会增加 2 个边。

如果您从“1”键开始，则从一个可能的角解决方案开始，在每一步中，您计算​​上一步的角、边、垂直和底部末端的数量，然后应用生成下一个计数的规则。

在纯 JavaScript 代码中。

function paths(n) {
    //Index to 0
    var corners = 1;
    var verticals = 0;
    var bottom = 0;
    var sides = 0;

    if (n <= 0) {
        //No moves possible for paths without length 
        return 0;
    }

    for (var i = 1; i < n; i++) {
        var previousCorners = corners;
        var previousVerticals = verticals;
        var previousBottom = bottom;
        var previousSides = sides;

        sides = 1 * previousCorners + 2 * previousBottom;
        verticals = 1 * previousCorners;
        bottom = 1 * previousSides;
        corners = 2 * previousSides + 2 * previousVerticals;
        //console.log("Moves: %d, Length: %d, Sides: %d, Verticals: %d, Bottom: %d, Corners: %d, Total: %d", i, i + 1, sides, verticals, bottom, corners, sides+verticals+bottom+corners);  
    }

    return sides + verticals + bottom + corners;

}

for (var i = 0; i <= 10; i++) {
    console.log(paths(i));  
}

Answer 8

此问题也可以建模为约束满足问题（简称为CSP）。

我建议使用 Minion 求解器（快速且可扩展），您可以在此处找到它。

建模可能很乏味且耗时（学习曲线陡峭）。

我的建议是使用独立于求解器的建模语言（例如 ESSENCE 并相应地找到转换器。

Answer 9

//Both the iterative and recursive with memorize shows count as 1424 for 10 digit numbers starting with 1. 
int[][] b = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};
public int countIterative(int digit, int length) {
    int[][] matrix = new int[length][10];
    for(int dig =0; dig <=9; dig++){
          matrix[0][dig] = 1;
    }
    for(int len = 1; len < length; len++){
        for(int dig =0; dig <=9; dig++){
          int sum = 0;
          for(int i : b[dig]){
            sum += matrix[len-1][i];
          }
          matrix[len][dig] = sum;
        }
    }
    return matrix[length-1][digit];
}

public int count(int index, int length, int[][] matrix ){
    int sum = 0;
    if(matrix[length-1][index] > 0){
        System.out.println("getting value from memoize:"+index + "length:"+ length);
        return matrix[length-1][index];
    }
    if( length == 1){
        return 1;
    }
    for(int i: b[index] )  {
         sum += count(i, length-1,matrix);
    }
    matrix[length-1][index] = sum;
    return sum;
}

Answer 10

递归记忆方法：

vector<vector<int>> lupt = { {4, 6}, {6, 8}, {9, 7}, {4, 8}, {3, 9, 0},
                             {},     {1,7,0}, {6, 2}, {1, 3}, {2, 4} };

int numPhoneNumbersUtil(int startdigit, int& phonenumberlength, int currCount, map< pair<int,int>,int>& memT)
{
    int noOfCombs = 0;
    vector<int> enddigits;

    auto it = memT.find(make_pair(startdigit,currCount));
    if(it != memT.end())
    {
        noOfCombs = it->second;
        return noOfCombs;
    }

    if(currCount == phonenumberlength)
    {
        return 1;
    }

    enddigits = lupt[startdigit];
    for(auto it : enddigits)
    {
        noOfCombs += numPhoneNumbersUtil(it, phonenumberlength, currCount + 1, memT);
    }

    memT.insert(make_pair(make_pair(startdigit,currCount), noOfCombs));
    return memT[make_pair(startdigit,currCount)];

}

int numPhoneNumbers(int startdigit, int phonenumberlength)
{
    map<pair<int,int>,int> memT;
    int currentCount = 1; //the first digit has already been added
    return  numPhoneNumbersUtil(startdigit, phonenumberlength, currentCount, memT);
}

Answer 11

我实现了暴力和动态编程模型

import queue


def chess_numbers_bf(start, length):
    if length <= 0:
        return 0
    phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
    total = 0
    q = queue.Queue()
    q.put((start, 1))

    while not q.empty():
        front = q.get()
        val = front[0]
        len_ = front[1]
        if len_ < length:
            for elm in phone[val]:
                q.put((elm, len_ + 1))
        else:
            total += 1
    return total


def chess_numbers_dp(start, length):
    if length <= 0:
        return 0

    phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
    memory = {}

    def __chess_numbers_dp(s, l):
        if (s, l) in memory:
            return memory[(s, l)]
        elif l == length - 1:
            memory[(s, l)] = 1
            return 1
        else:
            total_n_ways = 0
            for number in phone[s]:
                total_n_ways += __chess_numbers_dp(number, l+1)
            memory[(s, l)] = total_n_ways
            return total_n_ways
    return __chess_numbers_dp(start, 0)


# bf
for i in range(0, 10):
    print(i, chess_numbers_bf(3, i))
print('\n')

for i in range(0, 10):
    print(i, chess_numbers_bf(9, i))
print('\n')

# dp
for i in range(0, 10):
    print(i, chess_numbers_dp(3, i))
print('\n')

# dp
for i in range(0, 10):
    print(i, chess_numbers_dp(9, i))
print('\n')

Answer 12

Java中的递归函数：

public static int countPhoneNumbers (int n, int r, int c) {
        if (outOfBounds(r,c)) {
            return 0;
        } else {
            char button = buttons[r][c];
            if (button  == '.') {
                // visited
                return 0;
            }  else {
                buttons[r][c] = '.'; // record this position so don't revisit.
                // Count all possible phone numbers with one less digit starting
                int result=0;
                result = countPhoneNumbers(n-1,r-2,c-1)
                                         + countPhoneNumbers(n-1,r-2,c+1)
                                         + countPhoneNumbers(n-1,r+2,c-1)
                                         + countPhoneNumbers(n-1,r+2,c+1)
                                         + countPhoneNumbers(n-1,r-1,c-2)
                                         + countPhoneNumbers(n-1,r-1,c+2)
                                         + countPhoneNumbers(n-1,r+1,c-2)
                                         + countPhoneNumbers(n-1,r+1,c+2);
                }
                buttons[r][c] = button; // Remove record from position.
                return result; 
            }
        }
    }