Prolog: Comparing Lists from Lists of Lists-CodePudding

I am now quite a while trying to figure out what my mistake is, but I am not able to.

Task: We have to figure out how to find three permutations of a List containing 9 elements in the form of List of Lists. Each List of Lists should contain three sublists, each containing three elements. But no element is allowed to be together with another element in two different sublists.

The following output for the three permutations A, B, C with the given List= [1,2,3,4,5,6,7,8,9] could be:

predicate(A, B, C , [1,2,3,4,5,6,7,8,9]).

A = [[1,2,3],[4,5,6],[7,8,9]],
B = [[1,4,7],[2,5,8],[3,6,9]],
C = [[1,5,9],[2,6,7],[3,4,8]].

My Code so far (first my helper predicates) :

To split a list into a List of Lists ( N is always 3 ):

split_list(List, N, Splitted_List) :-
    split_helper(List, N, [], Splitted_List).

split_helper([], _, Acc, Acc).

split_helper(List, N, Acc, Splitted_List) :-
    my_append(H, T, List),
    my_length(H, N),
    split_helper(T, N, [H|Acc], Splitted_List).

A possible query:

split_list([1,2,3,4,5,6,7,8,9], 3, X).

X = [[1,2,3],[4,5,6],[7,8,9]].

To check wether all sublists of a List of lists contains at most one same element:

max_one_common_element(List1, List2) :-
    max_one_common_element(List1, List2, 0).

max_one_common_element([], _, Count) :-
    Count =< 1.
max_one_common_element([H|T], List2, Count) :-
    (my_member(H, List2) ->
        NewCount is Count   1,
        max_one_common_element(T, List2, NewCount)
    ;
        max_one_common_element(T, List2, Count)
    ).

A possible query:

max_one_common_element([[1,2,3],[4,5,6],[7,8,9]], [[1,4,7],[2,5,8],[3,6,9]]).

True.

To change order of sublists, for comparing purposes (important later on):

swap_lists(List, Result):-
    select(Selected, List, Rest),
    append(Rest, [Selected], Result).

A possible query:

swap_list([[1,2,3],[4,5,6],[7,8,9]], X).

X =  [[4,5,6],[7,8,9],[1,2,3]].

My main predicate, which instantiates A, B and C. The one making me issues is C, A and B are properly instantiated.

I was thinking to take all permutations of the input List and check with max_one_common_element/2 wether each sublists has at most one common element. Since max_one_common_element/2 is only able to check both lists at the current index ( e.g. [[1,2],[3,4]], [[3,4],[1,2]] would return True, even though it is False) my idea was to change the order of the sublists from A and B two times and check again with C after the first and second change, so all 3 sublists of A and B should be covered.

main_predicate(A, B, C, List):- 

    /* instantiates A as the input list but seqmented */

    split_list(List, 3 , A),

    /* instantiates B as a permutation of A, taking every nth element in a sublist*/

    %This part is unimportant since it works properly

    /* instantiates C as a permutation from the input list, test that each Sub-List contains at most one same element */

    permutation(List, Permuted),
    split_list(Permuted, Size, Dessert),
    max_one_common_element(A, C),
    max_one_common_element(A, C),

    /* first swap A and B two times */

    swap_lists(A, A1),
    swap_lists(A1, A2),
    swap_lists(B, B1),
    swap_lists(B1, B2),

    /* Check again with C */

    max_one_common_element(A1, C),
    max_one_common_element(A2, C),
    max_one_common_element(B1, C),
    max_one_common_element(B2, C).

When I make a query of:

predicate(A, B ,C, [1,2,3,4,5,6,7,8,9] ).

My output is:
A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ,
B = [[1, 4, 7], [2, 5, 8], [3, 6, 9]] ,
C = [[7, 8, 9], [4, 5, 6], [1, 2, 3]] .

Prolog just do not seem to consider every call of max_one_common_element/2. Since deleting some seem to change the output, but in my mind I have considered all cases and everything should be fine. I also considered changing max_one_common_element/2, but nothing works. Thank you really much for your help in advance.

CodePudding user response：

How about:

list_perm3(L, P) :-
    % Define length, for convenient [Head|Tail] notation
    length(P, 3),
    perm3_lists(P, L).
    
perm3_lists([], []).
perm3_lists([H|T], L) :-
    perm3(L, H, R),
    perm3_lists(T, R).

% L = input list, P = permutation, R = remainder
perm3(L, P, R) :-
    length(P, 3),
    perm3_(P, L, R).

perm3_([], R, R).
perm3_([H|T], L, R) :-
    % Take 1 element from L
    select(H, L, L0),
    perm3_(T, L0, R).

Results in swi-prolog:

?- list_perm3([1,2,3,4,5,6,7,8,9], P).
P = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ;
P = [[1, 2, 3], [4, 5, 6], [7, 9, 8]] ;
P = [[1, 2, 3], [4, 5, 6], [8, 7, 9]] ;
P = [[1, 2, 3], [4, 5, 6], [8, 9, 7]] ;
P = [[1, 2, 3], [4, 5, 6], [9, 7, 8]] ;
P = [[1, 2, 3], [4, 5, 6], [9, 8, 7]] ;
P = [[1, 2, 3], [4, 5, 7], [6, 8, 9]] ;
etc...

?- bagof(P, list_perm3([1,2,3,4,5,6,7,8,9], P), Ps), length(Ps, Len).
Len = 362880.

% First 3 solutions
?- limit(3, list_perm3([1,2,3,4,5,6,7,8,9], P)).
P = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ;
P = [[1, 2, 3], [4, 5, 6], [7, 9, 8]] ;
P = [[1, 2, 3], [4, 5, 6], [8, 7, 9]].

CodePudding user response：

Controlling the backtracking was interesting (to enforce member_count_inc_le over all the solution sublists):

:- dynamic p/2.

list_perm3(L, P) :-
    retractall(p(_, _)),
    list_perm3_loop(L, P).

list_perm3_loop(L, P) :-
    % Keeping backtracking to this top-level
    (list_perm3_(L, P) -> true ; !, fail).
list_perm3_loop(L, P) :-
    list_perm3_loop(L, P).

list_perm3_(L, P) :-
    length(P, 3),
    perm3_lists(P,  1, L),
    assert_p(P, 1).

% Add the new solution via assert
assert_p([], _).
assert_p([H|T], N) :-
    (p(N, L) -> true ; L = []),
    append(L, H, L1),
    sort(L1, LU),
    retractall(p(N, _)),
    assertz(p(N, LU)),
    N1 is N   1,
    assert_p(T, N1).

perm3_lists([], _, []).
perm3_lists([H|T], N, L) :-
    perm3(L, H, N, R),
    N1 is N   1,
    perm3_lists(T, N1, R).

perm3(L, P, N, R) :-
    (p(N, PS) -> true ; PS = []),
    length(P, 3),
    perm3_(P, L, N, 0, PS, R).

perm3_([], R, _, _, _, R).
perm3_([H|T], L, N, C, PS, R) :-
    select(H, L, L0),
    member_count_inc_le(PS, H, 1, C, C1),
    perm3_(T, L0, N, C1, PS, R).

member_count_inc_le([], _, _, C, C).
member_count_inc_le([H|T], E, Max, C, C1) :-
    (   H = E
    ->  C1 is C   1,
        C1 @=< Max
    ;   member_count_inc_le(T, E, Max, C, C1)
    ).

Results in swi-prolog:

?- time(list_perm3([1,2,3,4,5,6,7,8,9], P)).
% 89 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 964425 Lips)
P = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ;
% 1,044 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 3652751 Lips)
P = [[1, 4, 5], [2, 7, 8], [3, 6, 9]] ;
% 214 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 2242740 Lips)
P = [[1, 6, 7], [2, 3, 9], [4, 5, 8]] ;
% 23,772 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 7899160 Lips)
false.