序言递归

发布于 2024-10-09 23:28:43 字数 805 浏览 1 评论 0原文

我正在制作一个函数，该函数将向我发送所有可能元素的列表..在每次迭代中它都会给我最后一个答案..但是在递归之后我只能得到最后一个答案..我怎样才能让它返回每个答案..

谢谢你，

问题是我试图找到一个列表到其他列表的所有可能的分布..

addIn(_,[],Result,Result).
addIn(C,[Element|Rest],[F|R],Result):-
    member( Members , [F|R]),
    sumlist( Members, Sum),
    sumlist([Element],ElementLength),
    Cap is Sum + ElementLength,
       (Cap =< Ca,
    append([Element], Members,New)....

通过调用测试来获取代码..我正在取回所有可能答案的列表..现在如果我尝试做一些事情失败，就像

bp(3,11,[8,2,4,6,1,8,4],Answer).

   bp(NB,C,OL,A):-
            addIn(C,OL,[[],[],[]],A);
            bp(NB,C,_,A).

它只会进入一个 while 循环.. 如果我将改为and 而不是 Or ..

，我会收到错误：
错误：is/2：参数不是充分实例化

感谢帮助..

非常感谢@hardmath

原文

am making a function that will send me a list of all possible elemnts .. in each iteration its giving me the last answer .. but after the recursion am only getting the last answer back .. how can i make it give back every single answer ..

thank you

the problem is that am trying to find all possible distributions for a list into other lists .. the code

addIn(_,[],Result,Result).
addIn(C,[Element|Rest],[F|R],Result):-
    member( Members , [F|R]),
    sumlist( Members, Sum),
    sumlist([Element],ElementLength),
    Cap is Sum + ElementLength,
       (Cap =< Ca,
    append([Element], Members,New)....

by calling test .. am getting back all the list of possible answers .. now if i tried to do something that will fail like

bp(3,11,[8,2,4,6,1,8,4],Answer).

it will just enter a while loop .. more over if i changed the

   bp(NB,C,OL,A):-
            addIn(C,OL,[[],[],[]],A);
            bp(NB,C,_,A).

to and instead of Or .. i get error :

ERROR: is/2: Arguments are not
sufficiently instantiated

appreciate the help ..

Thanks alot @hardmath

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

筱果果 2024-10-16 23:28:43

听起来您正在尝试编写自己的 findall/3 版本，可能仅限于潜在目标的特殊情况。如果不借助断言/撤回的副作用。

然而，许多有用的特殊情况可以在没有这些“技巧”的情况下实现。因此，了解什么谓词定义了“所有可能的元素”会很有帮助。 [说明您正在使用哪种 Prolog 实现也可能会有所帮助，只要回复可能包含该版本文档的链接即可。]

一个重要的特殊情况是潜在候选者的“宇宙”已经作为列表存在。在这种情况下，我们实际上要求找到满足特定目标的“所有可能元素”的子列表。

    findSublist([ ],_,[ ]).
    findSublist([H|T],Goal,[H|S]) :-
        Goal(H),
        !,
        findSublist(T,Goal,S).
    findSublist([_|T],Goal,S) :-
        findSublist(T,Goal,S).

许多 Prolog 允许您将谓词 Goal 的名称作为“原子”传递，但如果您心中有一个特定的目标，您可以省略中间参数，并将您的特定条件硬编码到类似的中间子句中执行。

添加以响应发布的代码：

我想我对您正在尝试做的事情有一丝了解。这很难理解，因为你没有以正确的方式去做。您的谓词 bp/4 有一个递归子句，尝试使用 AND 或 OR 语法将对 addIn/4 的调用与对 bp/ 的调用关联起来。 4本身。

显然，您希望以这种方式将 bp/4 包裹在 addIn/4 周围，从而以某种方式导致 addIn/4 累积或迭代其解决方案。不会的。如果我们分析 bp/4 的参数发生了什么，可能会帮助您理解这一点。

您正在使用绑定到 NB 和 C 的简单整数、绑定到 OL 的整数列表以及 A 作为未绑定的“输出”答案来调用形式参数 bp(NB,C,OL,A)。请注意，值 NB 不会执行任何操作，因为它不会传递给 addIn/4，而是原封不动地传递给 bp/4 的递归调用。

根据 addIn/4 使用的变量名称和支持谓词 insert/4，我的猜测是 NB 的意思是“垃圾箱数量”。一方面，您在 test/0 子句中设置 NB = 3，然后在调用 addIn/4 时在第三个参数中“硬编码”三个空列表。无论您从 bp/4 得到什么答案，都来自于 addIn/4 能够利用从 bp/ 传入的前两个参数（C 和 OL）执行的操作4.正如我们所指出的，C 是一个整数，OL 是一个整数列表（至少以 test/0 调用 bp/4 的方式）。

因此，让我们尝试说明 addIn/4 应该如何处理这些参数。从表面上看，addIn/4似乎是以一种合理的方式构建自递归的。它的第一个子句是一个简单的终止条件，当第二个参数变成空列表时，统一第三个和第四个参数，并向调用者提供“答案”A。

addIn/4 的第二个子句似乎与该方法相协调。正如所写的，它将“head”元素从第二个参数中的列表中取出，并尝试在第三个参数中找到可以插入元素的“bin”，同时将该bin的总和保持在C给出的“cap”之下。如果一切顺利，最终 OL 中的所有数字都会被分配到一个 bin，所有 bin 的总数都低于上限 C，并且答案 A 会传回调用者。 addIn/4 的编写方式在基本清晰度方面留下了很大的改进空间，但它可能正在做您需要它做的事情。

这让我们回到了应该如何收集 addIn/4 生成的答案的问题。也许您很乐意一次打印一张。也许您打算将 addIn/4 生成的所有解决方案收集到一个列表中。为了完成这个练习，我需要你澄清你真正想用 addIn/4 的答案做什么。

假设您想将它们全部打印出来然后停止，特殊情况是如果传入的参数不允许解决方案，则不打印任何内容。那么您可能想要这种性质的东西：

newtest :-
    addIn(12,[7, 3, 5, 4, 6, 4, 5, 2], Answer),
    format("Answer = ~w\n",[Answer]),
    fail.
newtest.

这是让谓词 addIn/4 尝试所有可能的解决方案的标准方法，然后以第二个子句的“失败”成功结束newtest/0。

（已添加）关于addIn/4编码的建议：

如果变量名称清晰，将使代码更具可读性和可维护性。当您获取分配给“bin”的项目的总和时，我建议使用 Cap 而不是 C 作为 addIn/4 和 BinSum 的第一个参数。同样，当您使用成员时，Bin 会更好。在 addIn/4 的第三个参数中（在第二个子句的开头），您不需要显式列表结构 [F|R]，因为您从不单独引用 F 或 R 部分。所以我会使用 Bins。
您的某些谓词调用并不能完成很多您无法轻松完成的任务。例如，您对 sumlist/2 的第二次调用涉及包含一项的列表。因此，总和与该项目相同，即 ElementLength 与 Element 相同。在这里，您可以将对 sumlist/2 的两个调用替换为一个这样的调用：
sumlist([元素|Bin],BinSum)
然后进行比较 BinSum 和 Cap 的测试。类似地，您对 append/3 的调用只是将单个项目 Element 邻接到列表的前面（我正在调用）Bin，因此您可以将您所谓的 New 替换为 [Element|Bin] 。
您在最后四个子目标周围使用了一对额外的括号（在 addIn/4 的第二个子句中）。由于 AND 隐含于此子句的所有子目标，因此无需使用额外的一对括号。
现在未显示 insert/4 的代码，但在特殊情况下它可能是一些意外“回溯”的根源。更好的方法是让第一个调用（当前是 member/2）成为唯一的不确定点，即当您选择其中一个 bin 时，通过将其替换为一个自由变量来实现在最后一步与 [Element|Bin] 统一。

It sounds like you are trying to write your own version of findall/3, perhaps limited to a special case of an underlying goal. Doing it generally (constructing a list of all solutions to a given goal) in a user-defined Prolog predicate is not possible without resorting to side-effects with assert/retract.

However a number of useful special cases can be implemented without such "tricks". So it would be helpful to know what predicate defines your "all possible elements". [It may also be helpful to state which Prolog implementation you are using, if only so that responses may include links to documentation for that version.]

One important special case is where the "universe" of potential candidates already exists as a list. In that case we are really asking to find the sublist of "all possible elements" that satisfy a particular goal.

    findSublist([ ],_,[ ]).
    findSublist([H|T],Goal,[H|S]) :-
        Goal(H),
        !,
        findSublist(T,Goal,S).
    findSublist([_|T],Goal,S) :-
        findSublist(T,Goal,S).

Many Prologs will allow you to pass the name of a predicate Goal around as an "atom", but if you have a specific goal in mind, you can leave out the middle argument and just hardcode your particular condition into the middle clause of a similar implementation.

Added in response to code posted:

I think I have a glimmer of what you are trying to do. It's hard to grasp because you are not going about it in the right way. Your predicate bp/4 has a single recursive clause, variously attempted using either AND or OR syntax to relate a call to addIn/4 to a call to bp/4 itself.

Apparently you expect wrapping bp/4 around addIn/4 in this way will somehow cause addIn/4 to accumulate or iterate over its solutions. It won't. It might help you to see this if we analyze what happens to the arguments of bp/4.

You are calling the formal arguments bp(NB,C,OL,A) with simple integers bound to NB and C, with a list of integers bound to OL, and with A as an unbound "output" Answer. Note that nothing is ever done with the value NB, as it is not passed to addIn/4 and is passed unchanged to the recursive call to bp/4.

Based on the variable names used by addIn/4 and supporting predicate insert/4, my guess is that NB was intended to mean "number of bins". For one thing you set NB = 3 in your test/0 clause, and later you "hardcode" three empty lists in the third argument in calling addIn/4. Whatever Answer you get from bp/4 comes from what addIn/4 is able to do with its first two arguments passed in, C and OL, from bp/4. As we noted, C is an integer and OL a list of integers (at least in the way test/0 calls bp/4).

So let's try to state just what addIn/4 is supposed to do with those arguments. Superficially addIn/4 seems to be structured for self-recursion in a sensible way. Its first clause is a simple termination condition that when the second argument becomes an empty list, unify the third and fourth arguments and that gives "answer" A to its caller.

The second clause for addIn/4 seems to coordinate with that approach. As written it takes the "head" Element off the list in the second argument and tries to find a "bin" in the third argument that Element can be inserted into while keeping the sum of that bin under the "cap" given by C. If everything goes well, eventually all the numbers from OL get assigned to a bin, all the bins have totals under the cap C, and the answer A gets passed back to the caller. The way addIn/4 is written leaves a lot of room for improvement just in basic clarity, but it may be doing what you need it to do.

Which brings us back to the question of how you should collect the answers produced by addIn/4. Perhaps you are happy to print them out one at a time. Perhaps you meant to collect all the solutions produced by addIn/4 into a single list. To finish up the exercise I'll need you to clarify what you really want to do with the Answers from addIn/4.

Let's say you want to print them all out and then stop, with a special case being to print nothing if the arguments being passed in don't allow a solution. Then you'd probably want something of this nature:

newtest :-
    addIn(12,[7, 3, 5, 4, 6, 4, 5, 2], Answer),
    format("Answer = ~w\n",[Answer]),
    fail.
newtest.

This is a standard way of getting predicate addIn/4 to try all possible solutions, and then stop with the "fall-through" success of the second clause of newtest/0.

(Added) Suggestions about coding addIn/4:

It will make the code more readable and maintainable if the variable names are clear. I'd suggest using Cap instead of C as the first argument to addIn/4 and BinSum when you take the sum of items assigned to a "bin". Likewise Bin would be better where you used Members. In the third argument to addIn/4 (in the head of the second clause) you don't need an explicit list structure [F|R] since you never refer to either part F or R by itself. So there I'd use Bins.
Some of your predicate calls don't accomplish much that you cannot do more easily. For example, your second call to sumlist/2 involves a list with one item. Thus the sum is just the same as that item, i.e. ElementLength is the same as Element. Here you could just replace both calls to sumlist/2 with one such call:
sumlist([Element|Bin],BinSum)
and then do your test comparing BinSum with Cap. Similarly your call to append/3 just adjoins the single item Element to the front of the list (I'm calling) Bin, so you could just replace what you have called New with [Element|Bin].
You have used an extra pair of parentheses around the last four subgoals (in the second clause for addIn/4). Since AND is implied for all the subgoals of this clause, using the extra pair of parentheses is unnecessary.
The code for insert/4 isn't shown now, but it could be a source of some unintended "backtracking" in special cases. The better approach would be to have the first call (currently to member/2) be your only point of indeterminacy, i.e. when you choose one of the bins, do it by replacing it with a free variable that gets unified with [Element|Bin] at the next to last step.