在prolog中生成n位数字w/o 1s和0s
Generate n-digit number w/o 1s and 0s in prolog
我是 prolog 的初学者。
任务是在不使用 1 和 0 的情况下生成 n 位数字。这将如何完成？你生成随机数然后删除 1 和 0（听起来效率低下）？
您描述的绝对是一种方法。正如您提到的，这并不是一种特别 好的 方法，因为它是如此 低效。
然而，您提到的方法非常普遍，以至于它有自己的名字：它通常被称为 generate and test，因为我们首先 generate ，然后 拒绝 或 接受 解决方案，或者进一步修改它以满足所有约束。
通常更有效的方法是首先约束整个解决方案，以便所有的要求都表达出来，然后让系统只在已经约束的范围内搜索space。这在 Prolog 中特别容易做到，因为它提供了内置的 约束 ，您甚至可以在开始搜索解决方案之前 post，它们将是 在搜索之前和期间自动考虑。
例如，您可以按如下方式进行，使用您的 Prolog 系统的 CLP(FD) 约束 来表达对 整数[=65= 的期望要求]:
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 2..9,
reverse(Ds, Rs),
foldl(pow10, Rs, 0-0, _-Num).
pow10(D, Pow0-S0, Pow-S) :-
Pow #= Pow0 + 1,
S #= D*10^Pow0 + S0.
因此，我们将数字表示为数字的列表，并使用适当的约束将此列表与相应的整数相关联。关键是所有这一切都发生在之前实际生成单个解决方案，并且找到的所有解决方案都将满足规定的约束。而且，这是一个非常通用的relation，对各个方向都有效，我们可以用它来test，generate 和 完成 个解决方案。
这是一个示例查询，询问具有 3 位数字的此类数字如何看起来像一般:
?- n_digits(3, Ds, N).
作为响应，我们得到：
Ds = [_11114, _11120, _11126],
_11114 in 2..9,
_11114*100#=_11182,
_11182 in 200..900,
_11182+_11236#=N,
_11236 in 22..99,
_11282+_11126#=_11236,
_11282 in 20..90,
_11120*10#=_11282,
_11120 in 2..9,
_11126 in 2..9,
N in 222..999.
我们可以使用label/1获得具体解决方案：
?- n_digits(3, Ds, N), label(Ds).
Ds = [2, 2, 2],
N = 222 ;
Ds = [2, 2, 3],
N = 223 ;
Ds = [2, 2, 4],
N = 224 ;
Ds = [2, 2, 5],
N = 225 ;
etc.
在描述涉及 整数 的任务时，CLP(FD) 约束通常非常适合并且允许非常通用的解决方案。
例如，很容易合并额外的要求：
?- n_digits(3, Ds, N),
N #> 300,
label(Ds).
Ds = [3, 2, 2],
N = 322 ;
Ds = [3, 2, 3],
N = 323 ;
Ds = [3, 2, 4],
N = 324 ;
etc.
我们不在斯巴达了。有关详细信息，请参阅 clpfd！
clp(fd) 解决方案中肯定有很多优雅之处。如果你只是想要一个N位2..9的随机数，还有更直接的方法
n_digits(N, Ds, Num) :-
length(Ds, N),
maplist(random_between(0'2, 0'9), Ds),
number_codes(Num, Ds).
如果您使用 between 而不是 random_between，您将生成上述数字。我在http://swish.swi-prolog.org/p/JXELeTrX.swinb做了一个对比，我们可以看到
?- time(n_digits(1000, _Ds, N)).
6,010 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1814820 Lips)
比。使用 42 秒后内存不足 (256Mb) 的 clp(fd) 解决方案。
?- time((n_digits(1000, _Ds, N), label(_Ds))).
62,143,001 inferences, 42.724 CPU in 42.723 seconds (100% CPU, 1454531 Lips)
Out of global stack
我想用一个我认为值得单独研究的附加版本来补充现有答案。
请考虑以下事项：
n_digits(N, Ds, Expr) :-
length(Ds, N),
Ds ins 2..9,
foldl(pow10, Ds, 0, Expr).
pow10(D, S, S*10+D).
示例查询：
?- time((n_digits(1000, Ds, Expr), label(Ds))).
% 104,063 inferences, 0.013 CPU in 0.017 seconds (75% CPU, 8214635 Lips)
Ds = [2, 2, 2, 2, 2, 2, 2, 2, 2|...],
Expr = ((((... * ... + 2)*10+2)*10+2)*10+2)*10+2 .
在这里，我们还使用 约束 声明性地描述列表，此外还构建了一个算术 CLP(FD) 表达式， 计算 为结果数字。
与其他基于 CLP(FD) 的版本一样，这让我们可以 轻松地 post number 的附加约束]本身。
例如：
?- n_digits(1000, Ds, Expr),
Expr #> 5*10^999,
label(Ds).
Ds = [5, 2, 2, 2, 2, 2, 2, 2, 2|...],
Expr = ((((... * ... + 2)*10+2)*10+2)*10+2)*10+2 .
当您发现基于 CLP(FD) 的版本对于您的用例而言太慢时，我的建议是寻找方法来提高 其效率。我不能——至少不能板着脸——建议转而采用较低级别的方法。我已经看到太多有才华的 Prolog 程序员陷入低级语言结构的泥潭，却从未找到真正改进更高级别方面的方法，以至于他们成为 both general 和 对于在实践中相关的所有用例都足够有效。这是最需要他们才能的地方！
我想添加一个进一步的答案来从另一个角度考虑这个任务。
这一次，我想从简的回答开始：
n_digits(N, Ds, Num) :-
length(Ds, N),
maplist(random_between(0'2, 0'9), Ds),
number_codes(Num, Ds).
它的主要优点是非常简单，而且 快速:
?- time(n_digits(1000, Ds, Num)).
% 6,007 inferences, 0.002 CPU in 0.002 seconds (92% CPU, 2736674 Lips)
事实上，它是如此之快以至于它只在某些时候有效:
?- length(_, N), n_digits(3, Ds, 345).
N = 548,
Ds = [51, 52, 53] ;
N = 1309,
Ds = [51, 52, 53] ;
N = 1822,
Ds = [51, 52, 53] .
然而，此时我们已经习惯了一个众所周知的事实，即与性能相比，解决方案的正确性只是次要关注点，所以让我们继续好像解决方案是正确的。
我们可以直接将其映射到CLP(FD)约束，通过修改粗体部分如下：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
有没有人理解这个问题？请告诉我，我会尽我所能让所有有兴趣的人都明白。如果有人想了解更多，最好的方法是简单地提出一个新问题。
为了比较，这里又是之前的查询，它说明了这个谓词的行为与我们对 关系 的预期一样：
?- length(_, N), n_digits(3, Ds, 345).
N = 0,
Ds = [51, 52, 53] ;
N = 1,
Ds = [51, 52, 53] ;
N = 2,
Ds = [51, 52, 53] .
在这个具体案例中，使用 CLP(FD) 约束的 成本 在性能上大约是一个数量级，使用的约束求解器 不是 针对性能进行了优化，请注意：
?- time(n_digits(1000, Ds, Num)).
% 134,580 inferences, 0.023 CPU in 0.026 seconds (87% CPU, 5935694 Lips)
我几乎不敢说基于 CLP(FD) 的版本工作起来更可靠，因为这在实践中几乎没有价值。因此，根据您的用例，开销可能会令人望而却步。让我们假设对于这个具体案例，我们愿意牺牲 2% 的秒来使用 CLP(FD) 约束。
在许多可能的示例中，现在让我们考虑任务的以下轻微变化：
Let us describe lists of digits that satisfy all constraints, and are also palindromes.
这里是一个可能的回文描述：
palindrome --> [].
palindrome --> [_].
palindrome --> [P], palindrome, [P].
使用基于 CLP(FD) 的版本，我们可以轻松地将此约束与已经陈述的约束相结合：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
phrase(palindrome, Ds),
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
示例查询：
?- time(n_digits(1000, Ds, Num)).
% 12,552,433 inferences, 1.851 CPU in 1.943 seconds (95% CPU, 6780005 Lips)
为了比较，我们如何将这个直接 附加约束合并到 Jan 的版本中？这样做很诱人：
n_digits(N, Ds, Num) :-
length(Ds, N),
phrase(palindrome, Ds),
maplist(random_between(0'2, 0'9), Ds),
number_codes(Num, Ds).
也很简单，对吧？唯一的问题是它产生：
?- time(n_digits(1000, Ds, Num)).
% 4,013 inferences, 0.041 CPU in 0.046 seconds (88% CPU, 97880 Lips)
false.
为什么会这样？
现在祝您好运，向任何语言新手解释这个！在反对解释基于 CLP(FD) 的版本所声称的复杂性时，请考虑解释这种纯粹 程序性 的 高得多的复杂性 ]现象，单靠陈述性推理是无法理解的。
此外，使用低级特征完全解决任务的效果很好，仍然可以轻松添加额外的约束。
对了，有时，查询居然会成功！
?- length(_, N), time(n_digits(3, Ds, Num)).
% 28 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 848485 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1400000 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 1166667 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 1473684 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 1473684 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 1473684 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1473684 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1473684 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 1473684 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1473684 Lips)
% 26 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 1444444 Lips)
N = 10,
Ds = [52, 50, 52],
Num = 424 .
我只能说：老实说不能推荐这种方法，可以吗？
如果回文对您来说太不切实际，请考虑以下任务：
Let us describe lists of digits without 0, 1 and 5.
同样，使用 CLP(FD)，这很简单：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
maplist(#\=(0'5), Ds),
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
示例查询：
?- time(n_digits(1000, Ds, Num)).
% 203,529 inferences, 0.036 CPU in 0.038 seconds (93% CPU, 5662707 Lips)
为了比较，在没有 CLP(FD) 约束的情况下你会怎么做？
现在让我们合并两个要求：
Let us describe lists of digits without 0, 1 and 5 that are also palindromes.
同样，使用 CLP(FD) 版本，我们可以简单地陈述要求：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
maplist(#\=(0'5), Ds),
phrase(palindrome, Ds),
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
示例查询：
?- time(n_digits(1000, Ds, Num)).
% 20,117,000 inferences, 2.824 CPU in 2.905 seconds (97% CPU, 7123594 Lips)
这些示例说明，使用 约束 的一般机制，您实际上 有待改进 以防您需要对先前解决方案。代码非常容易适应，并且扩展性 相当好。
如果有什么太难理解的地方，请提出问题！
现在，作为最后一句话：我之前 post 编辑的两个基于 CLP(FD) 的版本都为您提供了 方式 超越这种直接翻译的东西。对于其他版本，您可以 post 附加约束，不仅可以对数字 列表 进行约束，还可以 对数字本身 进行约束！对于 不 使用约束的任何版本，这 完全无法实现 ！在搜索解决方案 开始 !
之前，这些限制条件 也 已被考虑在内
我是 prolog 的初学者。 任务是在不使用 1 和 0 的情况下生成 n 位数字。这将如何完成？你生成随机数然后删除 1 和 0（听起来效率低下）？
您描述的绝对是一种方法。正如您提到的，这并不是一种特别 好的 方法，因为它是如此 低效。
然而，您提到的方法非常普遍，以至于它有自己的名字：它通常被称为 generate and test，因为我们首先 generate ，然后 拒绝 或 接受 解决方案，或者进一步修改它以满足所有约束。
通常更有效的方法是首先约束整个解决方案，以便所有的要求都表达出来，然后让系统只在已经约束的范围内搜索space。这在 Prolog 中特别容易做到，因为它提供了内置的 约束 ，您甚至可以在开始搜索解决方案之前 post，它们将是 在搜索之前和期间自动考虑。
例如，您可以按如下方式进行，使用您的 Prolog 系统的 CLP(FD) 约束 来表达对 整数[=65= 的期望要求]:
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 2..9,
reverse(Ds, Rs),
foldl(pow10, Rs, 0-0, _-Num).
pow10(D, Pow0-S0, Pow-S) :-
Pow #= Pow0 + 1,
S #= D*10^Pow0 + S0.
因此，我们将数字表示为数字的列表，并使用适当的约束将此列表与相应的整数相关联。关键是所有这一切都发生在之前实际生成单个解决方案，并且找到的所有解决方案都将满足规定的约束。而且，这是一个非常通用的relation，对各个方向都有效，我们可以用它来test，generate 和 完成 个解决方案。
这是一个示例查询，询问具有 3 位数字的此类数字如何看起来像一般:
?- n_digits(3, Ds, N).
作为响应，我们得到：
Ds = [_11114, _11120, _11126], _11114 in 2..9, _11114*100#=_11182, _11182 in 200..900, _11182+_11236#=N, _11236 in 22..99, _11282+_11126#=_11236, _11282 in 20..90, _11120*10#=_11282, _11120 in 2..9, _11126 in 2..9, N in 222..999.
我们可以使用label/1获得具体解决方案：
?- n_digits(3, Ds, N), label(Ds). Ds = [2, 2, 2], N = 222 ; Ds = [2, 2, 3], N = 223 ; Ds = [2, 2, 4], N = 224 ; Ds = [2, 2, 5], N = 225 ; etc.
在描述涉及 整数 的任务时，CLP(FD) 约束通常非常适合并且允许非常通用的解决方案。
例如，很容易合并额外的要求：
?- n_digits(3, Ds, N), N #> 300, label(Ds). Ds = [3, 2, 2], N = 322 ; Ds = [3, 2, 3], N = 323 ; Ds = [3, 2, 4], N = 324 ; etc.
我们不在斯巴达了。有关详细信息，请参阅 clpfd！
clp(fd) 解决方案中肯定有很多优雅之处。如果你只是想要一个N位2..9的随机数，还有更直接的方法
n_digits(N, Ds, Num) :-
length(Ds, N),
maplist(random_between(0'2, 0'9), Ds),
number_codes(Num, Ds).
如果您使用 between 而不是 random_between，您将生成上述数字。我在http://swish.swi-prolog.org/p/JXELeTrX.swinb做了一个对比，我们可以看到
?- time(n_digits(1000, _Ds, N)).
6,010 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1814820 Lips)
比。使用 42 秒后内存不足 (256Mb) 的 clp(fd) 解决方案。
?- time((n_digits(1000, _Ds, N), label(_Ds))).
62,143,001 inferences, 42.724 CPU in 42.723 seconds (100% CPU, 1454531 Lips)
Out of global stack
我想用一个我认为值得单独研究的附加版本来补充现有答案。
请考虑以下事项：
n_digits(N, Ds, Expr) :-
length(Ds, N),
Ds ins 2..9,
foldl(pow10, Ds, 0, Expr).
pow10(D, S, S*10+D).
示例查询：
?- time((n_digits(1000, Ds, Expr), label(Ds))). % 104,063 inferences, 0.013 CPU in 0.017 seconds (75% CPU, 8214635 Lips) Ds = [2, 2, 2, 2, 2, 2, 2, 2, 2|...], Expr = ((((... * ... + 2)*10+2)*10+2)*10+2)*10+2 .
在这里，我们还使用 约束 声明性地描述列表，此外还构建了一个算术 CLP(FD) 表达式， 计算 为结果数字。
与其他基于 CLP(FD) 的版本一样，这让我们可以 轻松地 post number 的附加约束]本身。
例如：
?- n_digits(1000, Ds, Expr), Expr #> 5*10^999, label(Ds). Ds = [5, 2, 2, 2, 2, 2, 2, 2, 2|...], Expr = ((((... * ... + 2)*10+2)*10+2)*10+2)*10+2 .
当您发现基于 CLP(FD) 的版本对于您的用例而言太慢时，我的建议是寻找方法来提高 其效率。我不能——至少不能板着脸——建议转而采用较低级别的方法。我已经看到太多有才华的 Prolog 程序员陷入低级语言结构的泥潭，却从未找到真正改进更高级别方面的方法，以至于他们成为 both general 和 对于在实践中相关的所有用例都足够有效。这是最需要他们才能的地方！
我想添加一个进一步的答案来从另一个角度考虑这个任务。
这一次，我想从简的回答开始：
n_digits(N, Ds, Num) :-
length(Ds, N),
maplist(random_between(0'2, 0'9), Ds),
number_codes(Num, Ds).
它的主要优点是非常简单，而且 快速:
?- time(n_digits(1000, Ds, Num)). % 6,007 inferences, 0.002 CPU in 0.002 seconds (92% CPU, 2736674 Lips)
事实上，它是如此之快以至于它只在某些时候有效:
?- length(_, N), n_digits(3, Ds, 345). N = 548, Ds = [51, 52, 53] ; N = 1309, Ds = [51, 52, 53] ; N = 1822, Ds = [51, 52, 53] .
然而，此时我们已经习惯了一个众所周知的事实，即与性能相比，解决方案的正确性只是次要关注点，所以让我们继续好像解决方案是正确的。
我们可以直接将其映射到CLP(FD)约束，通过修改粗体部分如下：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
有没有人理解这个问题？请告诉我，我会尽我所能让所有有兴趣的人都明白。如果有人想了解更多，最好的方法是简单地提出一个新问题。
为了比较，这里又是之前的查询，它说明了这个谓词的行为与我们对 关系 的预期一样：
?- length(_, N), n_digits(3, Ds, 345). N = 0, Ds = [51, 52, 53] ; N = 1, Ds = [51, 52, 53] ; N = 2, Ds = [51, 52, 53] .
在这个具体案例中，使用 CLP(FD) 约束的 成本 在性能上大约是一个数量级，使用的约束求解器 不是 针对性能进行了优化，请注意：
?- time(n_digits(1000, Ds, Num)). % 134,580 inferences, 0.023 CPU in 0.026 seconds (87% CPU, 5935694 Lips)
我几乎不敢说基于 CLP(FD) 的版本工作起来更可靠，因为这在实践中几乎没有价值。因此，根据您的用例，开销可能会令人望而却步。让我们假设对于这个具体案例，我们愿意牺牲 2% 的秒来使用 CLP(FD) 约束。
在许多可能的示例中，现在让我们考虑任务的以下轻微变化：
Let us describe lists of digits that satisfy all constraints, and are also palindromes.
这里是一个可能的回文描述：
palindrome --> []. palindrome --> [_]. palindrome --> [P], palindrome, [P].
使用基于 CLP(FD) 的版本，我们可以轻松地将此约束与已经陈述的约束相结合：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
phrase(palindrome, Ds),
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
示例查询：
?- time(n_digits(1000, Ds, Num)). % 12,552,433 inferences, 1.851 CPU in 1.943 seconds (95% CPU, 6780005 Lips)
为了比较，我们如何将这个直接 附加约束合并到 Jan 的版本中？这样做很诱人：
n_digits(N, Ds, Num) :-
length(Ds, N),
phrase(palindrome, Ds),
maplist(random_between(0'2, 0'9), Ds),
number_codes(Num, Ds).
也很简单，对吧？唯一的问题是它产生：
?- time(n_digits(1000, Ds, Num)). % 4,013 inferences, 0.041 CPU in 0.046 seconds (88% CPU, 97880 Lips) false.
为什么会这样？
现在祝您好运，向任何语言新手解释这个！在反对解释基于 CLP(FD) 的版本所声称的复杂性时，请考虑解释这种纯粹 程序性 的 高得多的复杂性 ]现象，单靠陈述性推理是无法理解的。
此外，使用低级特征完全解决任务的效果很好，仍然可以轻松添加额外的约束。
对了，有时，查询居然会成功！
?- length(_, N), time(n_digits(3, Ds, Num)). % 28 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 848485 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1400000 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 1166667 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 1473684 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 1473684 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 1473684 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1473684 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1473684 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 1473684 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 1473684 Lips) % 26 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 1444444 Lips) N = 10, Ds = [52, 50, 52], Num = 424 .
我只能说：老实说不能推荐这种方法，可以吗？
如果回文对您来说太不切实际，请考虑以下任务：
Let us describe lists of digits without 0, 1 and 5.
同样，使用 CLP(FD)，这很简单：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
maplist(#\=(0'5), Ds),
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
示例查询：
?- time(n_digits(1000, Ds, Num)). % 203,529 inferences, 0.036 CPU in 0.038 seconds (93% CPU, 5662707 Lips)
为了比较，在没有 CLP(FD) 约束的情况下你会怎么做？
现在让我们合并两个要求：
Let us describe lists of digits without 0, 1 and 5 that are also palindromes.
同样，使用 CLP(FD) 版本，我们可以简单地陈述要求：
n_digits(N, Ds, Num) :-
length(Ds, N),
Ds ins 0'2..0'9,
maplist(#\=(0'5), Ds),
phrase(palindrome, Ds),
labeling([random_value(0)], Ds),
number_codes(Num, Ds).
示例查询：
?- time(n_digits(1000, Ds, Num)). % 20,117,000 inferences, 2.824 CPU in 2.905 seconds (97% CPU, 7123594 Lips)
这些示例说明，使用 约束 的一般机制，您实际上 有待改进 以防您需要对先前解决方案。代码非常容易适应，并且扩展性 相当好。
如果有什么太难理解的地方，请提出问题！
现在，作为最后一句话：我之前 post 编辑的两个基于 CLP(FD) 的版本都为您提供了 方式 超越这种直接翻译的东西。对于其他版本，您可以 post 附加约束，不仅可以对数字 列表 进行约束，还可以 对数字本身 进行约束！对于 不 使用约束的任何版本，这 完全无法实现 ！在搜索解决方案 开始 !
之前，这些限制条件 也 已被考虑在内