sorry I am new to Prolog and logic programming. I was wondering if the following is possible in Prolog:

Given j lists of size n = k*j, how do I rearrange them into m lists, each containing the first k elements of each of the j lists?

For example, given a list of lists of 12 elements, such as

[
  [  1,  2,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 , 10 , 11 , 12 ],
  [ 13, 14, 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 ],
  [ 25, 26, 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 ]
]

How do I transform it to

[
  [ 1,  2,  3,   4, 13, 14, 15, 16, 25, 26, 27, 28 ],
  [ 5,  6,  7,   8, 17, 18, 19, 20, 29, 30, 31, 32 ],
  [ 9, 10,  11, 12, 21, 22, 23, 24, 33, 34, 35, 36 ]
]

???

I can extract the first k elements of each list in the list.

getFirstK(List, K, FirstK, Remainder) :-
        length(FirstK, K),
        append(FirstK, Remainder, List).

And I thought I could get at least [1,2,3,4,13,14,15,16,25,26,27,28] with the following,

GetLists([], K, []).
GetLists([FirstList|RestOfLists], K, Result) :-
        getFirstK(FirstList, K, FirstK, Remainder),
        GetLists(RestOfLists, K, [FirstK|Result]).

However, when I run getLists to get Result, I get false instead. Is there a way to get the list of lists?

CodePudding user response：

You can write a procedure that takes the first K elements of a list, then append all the resulting lists and recursively apply this procedure until there are only empty lists in your input:

get_lists(LL, _, []):-
  maplist(=([]), LL).
get_lists(LL, K, [R|LR]):-
  maplist(split(K), LL, LChunks, LRest),
  append(LChunks, R),
  get_lists(LRest, K, LR).

split(K, L, Chunk, Rest):-
  length(Chunk, K),
  append(Chunk, Rest, L).

Sample run:

?- get_lists( [[1,2,3,4,5,6,7,8,9,10,11,12], [13,14,15,16,17,18,19,20,21,22,23,24],[25,26,27,28,29,30,31,32,33,34,35,36]], 4, LR).
LR = [[1, 2, 3, 4, 13, 14, 15, 16, 25, 26, 27, 28], [5, 6, 7, 8, 17, 18, 19, 20, 29, 30, 31, 32], [9, 10, 11, 12, 21, 22, 23, 24, 33, 34, 35, 36]] ;
false.

CodePudding user response：

Using difference lists, for performance:

rearrange_lists([H|T], BiteLen, RLs) :-
    % Populate the heads, leaving the tails
    spread_list(H, BiteLen, RLs, Tails),
    % Loop through populating the tails
    rearrange_lists_(T, BiteLen, Tails).

rearrange_lists_([], _, Tails) :-
    % Close the tails
    maplist(=([]), Tails).
rearrange_lists_([H|T], BiteLen, Heads) :-
    spread_list(H, BiteLen, Heads, Tails),
    rearrange_lists_(T, BiteLen, Tails).

spread_list([], _BL, [], []).
spread_list([H|T], BiteLen, [BiteH|BiteHs], [BiteT|BiteTs]) :-
    copy_list_to_dl_len(BiteLen, [H|T], _HS, HR, BiteH, BiteT),
    spread_list(HR, BiteLen, BiteHs, BiteTs).

% Generic, reusable predicate
copy_list_to_dl_len(Len, Lst, LstH, LstT, SubLstH, SubLstT) :-
    (   nonvar(Len)
    ->  integer(Len),
        Len @>= 0,
        % Only once
        copy_list_to_dl_len_inc_(Lst, LstH, LstT, 0, Len, SubLstH, SubLstT), !
    ;   copy_list_to_dl_len_inc_(Lst, LstH, LstT, 0, Len, SubLstH, SubLstT)
    ).
    
copy_list_to_dl_len_inc_(Lst, Lst, Lst, Len, Len, SubLst, SubLst).
copy_list_to_dl_len_inc_([H|T], [H|HT], LT, Len, FLen, [H|ST], SLT) :-
    Len1 is Len   1,
    copy_list_to_dl_len_inc_(T, HT, LT, Len1, FLen, ST, SLT).

Result in swi-prolog:

?- time(rearrange_lists([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], [25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]], 4, RLs)).
% 87 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 1429182 Lips)
RLs = [[1, 2, 3, 4, 13, 14, 15, 16, 25, 26, 27, 28], [5, 6, 7, 8, 17, 18, 19, 20, 29, 30, 31, 32], [9, 10, 11, 12, 21, 22, 23, 24, 33, 34, 35, 36]].