Prolog：高效实现Luhn算法

Question

我尝试在 SWI-Prolog 中应用 Luhn 算法。但是我在运行中遇到了一些问题。当我用像 123 这样的简单数字进行测试时，它会很快给出结果。如果我用 5379173895860200 这样更长的数字进行测试，它运行的时间太长了，我只能中止这次执行。需要帮助才能找到问题。代码：

luhn(N):-
    spliter(N,Y),
    reverse(Y, Z),
    check(Z,X),
    sum_all(X, Res),
    T is Res mod 10,
    T is 0.

spliter(0,[]).
spliter(N,L):-
    N1 is floor(N/10),
    X is N mod 10,
    spliter(N1, L2),
    L = [X|L2].

check(A,B):-
    double(A,B,_).

double([],[],0).
double([H|T], [H1|T1], C):-
    double(T,T1, C1),
    C is C1 +1,
    H1 is H*(1+ C mod 2).

sum_all([],0).
sum_all([H|T],Sum):-
    sum_all(T,Subsum),
    X is floor(H/10),
    Y is H mod 10,
    Sum is (Subsum + X + Y).

Answer 1

这是我从 Wikipedia

翻译的 Python

is_luhn_valid(Card_number):-
    luhn_checksum(Card_number, 0).

luhn_checksum(Card_number, Checksum) :-
    digits_of(Card_number, Digits),
    findall(D, (nth0(I, Digits, D), I mod 2 =:= 0), Odd_digits),
    findall(D, (nth0(I, Digits, D), I mod 2 =:= 1), Even_digits),
    sum_list(Odd_digits, Checksum_t),
    findall(S, (
        member(T, Even_digits),
        T1 is T * 2,
        digits_of(T1, D1),
        sum_list(D1, S)
    ), St),
    sum_list(St, St1),
    Checksum is (Checksum_t + St1) mod 10.

digits_of(Number, Digits) :-
    number_codes(Number, Cs),
    maplist(code_digit, Cs, Digits).
code_digit(C, D) :- D is C - 0'0.

除了更冗长之外，它似乎是正确的 wrt 来自上面页面的测试用例。但是：

?- is_luhn_valid(123).
false.

而您的代码：

?- luhn(123).
true ;
true ;
...

当然还有

?- luhn(124).
....

不会终止。所以，你陷入了一个失败循环，Prolog 每次都被要求尝试证明一个无法解决的目标......

痕迹片段：

?- leash(-all),trace.
true.

[trace] ?- luhn(124).
   Call: (7) so:luhn(124)
   Call: (8) so:spliter(124, _G9437)
...
   Exit: (8) 2 is 12 mod 10
   Call: (8) 2 is 0
   Fail: (8) 2 is 0
   Redo: (11) so:spliter(0, _G9461)
   Call: (12) _G9465 is floor(0/10)
...

问题似乎是 spliter/2 一直在序列前面添加 0，而它应该会失败。

关于效率：我的代码片段可以改写为

luhn_checksum(Card_number, Checksum) :-
    digits_of(Card_number, Digits),
    aggregate_all(sum(V), (
        nth0(I, Digits, D),
        (   I mod 2 =:= 0
        ->  V = D           % Odd_digits
        ;   Dt is D * 2,    % Even_digits
            digits_of(Dt, Ds),
            sum_list(Ds, V)
        )),
        Checksum_t),
    Checksum is Checksum_t mod 10.

利用图书馆(aggregate)

编辑

我认为spliter/2应该检查N>0，否则它将永远递归... 尝试

spliter(N,L):- N>0,
    N1 is floor(N/10),
    ...

Answer 2

不用取大号就能看出你代码的问题。考虑循环的 luhn(1) 和 "efficient" luhn(0).

就足够了

您遇到的问题不是效率问题，而是终止问题。终止在 Prolog 中是一个非常微妙的概念。如果您通过顶层循环使用 Prolog，许多系统只会向您显示第一个答案。如果查询不包含变量，有些甚至不会显示任何进一步的答案。通过这种方式，您很容易产生错误的印象，认为您的程序可以正常运行并终止，而实际上却没有。

有一种非常简单的方法，可以在任何系统中测试终止。只需将目标 false 添加到您的查询中。现在甚至 luhn(0),false 循环。

您可以更进一步，将此类 false 目标添加到您的计划中 ¹，从而减少你必须理解的文字。在你的情况下，考虑就足够了：

luhn(N):-
    spliter(N,Y), false,
    reverse(Y, Z),
    check(Z,X),
    sum_all(X, Res),
    T is Res mod 10,
    T is 0.

spliter(0,[]) :- false.
spliter(N,L):-
    N1 is floor(N/10),
    X is N mod 10,
    spliter(N1, L2), false,
    L = [X|L2].

程序的这一小部分（称为 failure-slice）足以理解非终止。事实上，任何整数 N 都会导致循环。你需要的是直接添加N > 0作为spliter/2的第一个目标。

有关更多信息，请参阅 failure-slice

^{Fine Print
1 实际上，这仅适用于像您的程序这样的纯单调程序。}

Prolog：高效实现Luhn算法

Prolog: implement Luhn algorithm with efficiency

algorithm

prolog

luhn

failure-slice