3

セットのリストを生成する方法を理解しようとしています。各セットの長さはNで、各セットの合計はXです。

私はこのコードを見つけました：

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

そして、それを使用して、合計Xのセットのリストを取得できます。

num_split(6,List),length(List,5).
List = [1, 1, 1, 1, 2] ;
List = [1, 1, 1, 2, 1] ;
List = [1, 1, 2, 1, 1] ;
List = [1, 2, 1, 1, 1] ;
List = [2, 1, 1, 1, 1] ;
false.

問題は、それらがすべて順列であり、私が組み合わせを探しているということです。私が探している出力は次のようになりますget_combos(Sum,Length,List)：

get_combos(6,2,List).
List = [5,1];
List = [4,2];
List = [3,3];
false.

ポインタはありますか？

4

2 に答える 2

3

CLP（FD）ライブラリにアクセスできる場合は、次のコードを使用できます。

:- [library(clpfd)].

get_combos(Sum, Length, List) :-
    length(List, Length),
    List ins 1 .. Sum,
%   all_distinct(List), not really useful here
    sum(List, #=, Sum),
    chain(List, #<),
    label(List).

テスト：

?- get_combos(10,3,L).
L = [1, 2, 7] ;
L = [1, 3, 6] ;
L = [1, 4, 5] ;
L = [2, 3, 5] ;

多分私はあなたの質問を誤解しました。このチェーンを使用する

...
chain(List, #=<),
....

重複する可能性のある値を取得するには：

?- get_combos(10,3,L).
L = [1, 1, 8] ;
L = [1, 2, 7] ;
L = [1, 3, 6] ;
L = [1, 4, 5] ;
L = [2, 2, 6] ;
L = [2, 3, 5] ;
L = [2, 4, 4] ;
L = [3, 3, 4] ;
false.
于 2012-05-16T07:04:58.523 に答える
1

配列内の連続する値の間に「等しいかそれ以上」の制限を適用します。

別の述語として追加できます。

is_combination([]).
is_combination([_]).
is_combination([A,B|List]) :- A =< B, is_combination([B|List]).

get_combos(Sum, Length, List) :-
    num_split(Sum, Length, List),
    is_combination(List).

残念ながら、num_split / 3の最後に追加しても、必ずしもパフォーマンスが向上するわけではないため、アルゴリズムに直接追加する方がわずかに優れています。

get_combos(_, 0, []).
get_combos(Sum, 1, [Sum]).
get_combos(Sum, Length, [A, B|List]) :-
    between(1, Sum, A),
    plus(A, NextSum, Sum),
    plus(1, NextLength, Length),
    get_combos(NextSum, NextLength, [B|List]),
    A =< B.

以下の演算子（= <）を使用するには、両方のオペランドを完全にインスタンス化する必要があるため、再帰後に比較する必要があるため、これがどれだけパフォーマンスを向上させるかはわかりません。

于 2012-05-16T03:41:55.143 に答える