如何创建加起来等于特定数字的数字列表

发布于 2024-11-26 03:53:48 字数 256 浏览 0 评论 0原文

我需要一些帮助，在 Prolog 中编写一个谓词，给定一个数字作为输入，返回一个列表列表，其中的数字相加。

让我们调用谓词 addUpList/2，它应该像这样工作：

?- addUpList(3,P).
P = [[1,2], [2,1], [1,1,1]].       % expected result

我很难弄清楚这一点，我开始认为这是不可能的。有什么想法吗？提前致谢。

原文

I need some help writing a predicate in Prolog that, given a number as input, returns a list of lists with numbers that add up to it.

Let's call the predicate addUpList/2, it should work like this:

?- addUpList(3,P).
P = [[1,2], [2,1], [1,1,1]].       % expected result

I'm having so much trouble figuring this out I'm beginning to think it's impossible. Any ideas? Thanks in advance.

分享到QQ

分享到微博

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

发布评论

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

_失温 2024-12-03 03:53:48

试试这个：

condense([], Rs, Rs).
condense([X|Xs], Ys, Zs) :-
    condense(Xs, [X|Ys], Zs).
condense([X, Y|Xs], Ys, Zs) :-
    Z is X + Y,
    condense([Z|Xs], Ys, Zs).

condense(Xs, Rs) :-
    condense(Xs, [], Rs).

expand(0, []).
expand(N, [1|Ns]) :-
    N > 0,
    N1 is N - 1,
    expand(N1, Ns).

addUpList(N, Zs) :-
    expand(N, Xs),
    findall(Ys, condense(Xs, Ys), Zs).

让我知道我得到的分数。 :-)

Try this:

condense([], Rs, Rs).
condense([X|Xs], Ys, Zs) :-
    condense(Xs, [X|Ys], Zs).
condense([X, Y|Xs], Ys, Zs) :-
    Z is X + Y,
    condense([Z|Xs], Ys, Zs).

condense(Xs, Rs) :-
    condense(Xs, [], Rs).

expand(0, []).
expand(N, [1|Ns]) :-
    N > 0,
    N1 is N - 1,
    expand(N1, Ns).

addUpList(N, Zs) :-
    expand(N, Xs),
    findall(Ys, condense(Xs, Ys), Zs).

Let me know what marks I get. :-)

回复收藏 0 原文

山人契 2024-12-03 03:53:48

规则 num_split/2 生成将数字拆分为列表的方法，其中第一个元素 X 是 1 和 之间的任意数字N 和列表的其余部分是 NX 的拆分。

num_split(0, []).
num_split(N, [X | List]) :-
    between(1, N, X),
    plus(X, Y, N),
    num_split(Y, List).

为了获得所有此类拆分，只需对 num_split/2 调用 findall/3 即可。

add_up_list(N, Splits) :-
    findall(Split, num_split(N, Split), Splits).

用法示例：

?- add_up_list(4, Splits).
Splits =
   [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]].

另请参阅@hardmath 的帖子，它给出了相同的答案，但有更多的解释。

The rule num_split/2 generates ways of splitting a number into a list, where the first element X is any number between 1 and N and the rest of the list is a split of N-X.

num_split(0, []).
num_split(N, [X | List]) :-
    between(1, N, X),
    plus(X, Y, N),
    num_split(Y, List).

In order to get all such splits, just call findall/3 on num_split/2.

add_up_list(N, Splits) :-
    findall(Split, num_split(N, Split), Splits).

Usage example:

?- add_up_list(4, Splits).
Splits =
   [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]].

See also the post by @hardmath which gives the same answer with a bit more explanation.

回复收藏 0 原文

余罪 2024-12-03 03:53:48

问题中给出的示例表明需要任何正整数 N ≤ 10 的组合（有序分区）。但请注意，N=3 的解决方案 [3] 似乎已被省略/忽略。 N 的组合数是 2^(N-1)，所以 N =10 给出了一个很长的列表，但并不是一个难以管理的列表。

还希望将所有此类解决方案收集到一个列表中，这是在我们编写生成它们的谓词 composition/2 后 findall/3 可以通用执行的操作。

这个想法是选择第一个被加数（1 到 N 之间的任何值），从总数中减去它并递归（当总数达到零时以空列表停止）。 SWI-Prolog 提供了一个谓词 Between/3 可以生成那些可能的第一个被加数，还有 Amzi！ Prolog 提供了类似的谓词for/4。为了可移植性，我们在这里编写自己的版本。

summand(Low,High,_) :-
    Low > High,
    !,
    fail.
summand(Low,High,Low).
summand(Low,High,Val) :-
    Now is Low + 1,
    summand(Now,High,Val).

composition(0,[ ]).
composition(N,[H|T]) :-
    summand(1,N,H),
    M is N - H,
    composition(M,T).

给定上述经过编译或解释的 Prolog 源代码，可以通过以下方式获得所有解决方案的列表：

?- findall(C,composition(3,C),L).

C = H126
L = [[1, 1, 1], [1, 2], [2, 1], [3]]

当然，您的特定应用程序可能需要对此类解决方案列表进行某种安排或省略单例列表，但这由于问题目前的措辞尚不清楚。

The example given in the Question suggests that compositions (ordered partitions) of any positive integer N ≤ 10 are wanted. Note however that the solution [3] for N=3 seems to have been omitted/overlooked. The number of compositions of N is 2^(N-1), so N=10 gives a long list but not an unmanageable one.

It is also desired to collect all such solutions into a list, something that findall/3 can do generically after we write a predicate composition/2 that generates them.

The idea is to pick the first summand, anything between 1 and N, subtract it from the total and recurse (stopping with an empty list when the total reaches zero). SWI-Prolog provides a predicate between/3 that can generate those possible first summands, and Amzi! Prolog provides a similar predicate for/4. For the sake of portability we write our own version here.

summand(Low,High,_) :-
    Low > High,
    !,
    fail.
summand(Low,High,Low).
summand(Low,High,Val) :-
    Now is Low + 1,
    summand(Now,High,Val).

composition(0,[ ]).
composition(N,[H|T]) :-
    summand(1,N,H),
    M is N - H,
    composition(M,T).

Given the above Prolog source code, compiled or interpreted, a list of all solutions can be had in this way:

?- findall(C,composition(3,C),L).

C = H126
L = [[1, 1, 1], [1, 2], [2, 1], [3]]

Of course some arrangement of such a list of solutions or the omission of the singleton list might be required for your specific application, but this isn't clear as the Question is currently worded.

回复收藏 0 原文

怎会甘心 2024-12-03 03:53:48

这个问题已经有很多很好的答案，但这里有另一个解决方案供您考虑。该程序与其他程序的不同之处在于它非常高效，并生成列表的非冗余解决方案，这些列表被假定表示集合加起来达到指定数字的整数集。

gen(N, L) :-
    gen(N-1, N, N, FL),
    dup_n(FL, L).
gen(C-F, M, M, [C-F]).
gen(C-F, S, M, [C-F|R]) :-
    S < M, C > 1,
    C0 is C - 1,
    F0 is floor(M / C0),
    S0 is S + (C0 * F0),
    gen(C0-F0, S0, M, R).
gen(C-F, S, M, R) :-
    F > 0,
    F0 is F - 1,
    S0 is S - C,
    gen(C-F0, S0, M, R).

dup_n([], []).
dup_n([_-0|R], L) :-
    !, dup_n(R, L).
dup_n([V-F|R], [V|L]) :-
    F0 is F - 1,
    dup_n([V-F0|R], L).

您可以通过以下方式实现 addUpList/2 ：

addUpList(N, P) :-
    findall(L, gen(N, L), P).

这应该为您提供以下行为：

?- addUpList(4,L).
L = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]].

请注意，列表包含一个 2 和两个 1 s 在此结果集中仅出现一次；这是因为 gen/4 计算加起来达到指定数字的唯一整数集。

There are plenty of great answers to this question already, but here is another solution to this problem for you to consider. This program differs from the others in that it is very efficient, and generates non-redundant solutions of lists which are assumed to represent sets of integers which add up to the specified number.

gen(N, L) :-
    gen(N-1, N, N, FL),
    dup_n(FL, L).
gen(C-F, M, M, [C-F]).
gen(C-F, S, M, [C-F|R]) :-
    S < M, C > 1,
    C0 is C - 1,
    F0 is floor(M / C0),
    S0 is S + (C0 * F0),
    gen(C0-F0, S0, M, R).
gen(C-F, S, M, R) :-
    F > 0,
    F0 is F - 1,
    S0 is S - C,
    gen(C-F0, S0, M, R).

dup_n([], []).
dup_n([_-0|R], L) :-
    !, dup_n(R, L).
dup_n([V-F|R], [V|L]) :-
    F0 is F - 1,
    dup_n([V-F0|R], L).

Your implementation of addUpList/2 can be achieved by:

addUpList(N, P) :-
    findall(L, gen(N, L), P).

Which should give you the following behaviour:

?- addUpList(4,L).
L = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]].

Note that the list containing one 2 and two 1s only appears once in this result set; this is because gen/4 computes unique sets of integers which add up to the specified number.

回复收藏 0 原文

你丑哭了我 2024-12-03 03:53:48

这个答案介于两者之间
@Kaarel 的回答和
@sharky 的“高效”答案。

就像@sharky 的代码一样，我们在相邻列表项之间施加排序关系来限制解决方案空间的大小——知道如何在需要时对其进行膨胀。因此 @sharky 的 break_down/2 和 gen/2 的解集是相等的（不考虑列表反转）。

至于性能，请考虑：

?- time((break_down(40,_),false)).
% 861,232 inferences, 0.066 CPU in 0.066 seconds (100% CPU, 13127147 Lips)
false.

?- time((gen(40,_),false)).
% 8,580,839 inferences, 0.842 CPU in 0.842 seconds (100% CPU, 10185807 Lips)
false.

This answer is somewhere between
@Kaarel's answer and
@sharky's "efficient" answer.

Like @sharky's code, we impose an ordering relation between adjacent list items to restrict the size of the solution space---knowing how to inflate it if we ever need to. So the solution sets of break_down/2 and gen/2 by @sharky are equal (disregarding list reversal).

And as for performance, consider:

?- time((break_down(40,_),false)).
% 861,232 inferences, 0.066 CPU in 0.066 seconds (100% CPU, 13127147 Lips)
false.

?- time((gen(40,_),false)).
% 8,580,839 inferences, 0.842 CPU in 0.842 seconds (100% CPU, 10185807 Lips)
false.

回复收藏 0 原文

~没有更多了~