Нахождение минимального подсписка, содержащего все элементы K

Question

Допустим, у меня есть список: [1,3,1,3,1,3,3,2,2,1] и N=3 (разные числа) в качестве входных данных. Что я хочу, это найти размер минимального подсписка в этом, который имеет все N элементов. Для этого примера этобудет [1,3,3,2] или [3,2,2,1] с размером = 4;Что я сделал до сих пор, так это для K=[1,2,3] и List=[1,3,1,3,1,3,3,2,2,1]:

append(Subl,_,List),
subset(K,Subl),!,
append(_,Subl2,Subl),
length(Subl2,L),
subset(K,Subl2).

Первое добавление с первым подмножеством находит первый подсписок, который имеет все K элементов, в данном случае [1,3, 1,3,1,3,3,2]. После этого мы стараемся максимально уменьшить размер этого списка, чтобы он не переставал содержать все K различных чисел. В этом случае конечный результат будет [1,3,3,2] и L = 4. Мои вопросы таковы: После нахождения [1,3,1,3,1,3,3,2] L начнется с 8 и приведет к 4. Как я могу обновить (может быть, каким-то образом хранить?) это значение каждый раз, когда я нахожу меньший подсписок, содержащий все K чисел?, 3,2]). Как я могу добавить оставшиеся элементы Списка в [3,3,2] (эти элементы будут [2,2,1]) и начать процесс заново?

PS: я нашел некоторые другие решения для предыдущих сообщений S / O, но они нашли все возможные подсписки, начиная с размера 3 до размера 10, и проверили для каждого из них, содержит ли он все элементы K. Это длябольшие входные данные терпят неудачу, и я думаю, что мы должны использовать подход скользящего окна здесь

Answer 1

Я попробовал другой подход для больших списков.

Я использую список поисковых номеров и указатель последнего появления в списке.

getValue(In, Ind, V) :-
    nth0(Ind, In, V).


% create the list of the numbers with the index of there last appearance
% -1 if not
% the list is sorted in decreasing order of the index of the numbers 
make_indice(U, -1 - U).

minSubList(Min, Max, In, Out) :-
    numlist(Min, Max, NL),
    maplist(make_indice, NL, Il),

    % at the beginning, the length of the sublist is the length of the input !
    length(In, Len),

    % main predicate of the process
    walk(In, 0, Len, Il, 0, Len, VMin, VMax),

    % now we get the result
    numlist(VMin, VMax, NL1),
    maplist(getValue(In), NL1, Out).

% if the list is empty process is finished
walk([], _, _, _IL, Min, Max, Min, Max).

% @arg1 current input to process
% @arg2 index of the head of the input in the initial input
% @arg3 current len of sublist containing all of the numbers
% @arg4 current list of the numbers with there index in the initial list
% @arg5 current first index where we find all the numbers 
% @arg6 current last index where we find all the numbers 
% @arg7 final first index where we find all the numbers 
% @arg8 final last index where we find all the numbers 

walk([H|T], N, Len, Il,  CurMin, CurMax, Min, Max) :-
    % we remove the element of the index list concerning H
    select(_-H, Il, IlTemp),
    % we build the new list of index H is the first lement of the list
    % because he is the last seen !
    LstInd = [N-H | IlTemp],
    % we need to know the index of the first number seen, 
    % it is the last of the list
    last(LstInd, V - _),
    N1 is N+1,
    (   V = -1
    ->  % at least one number is not seen 
        % we keep on this way
        walk(T, N1, Len, LstInd, CurMin, CurMax, Min, Max)
    ;   % all the numbers are seen
        % we must update the lentgh of the sublist
        Len1 is N-V+1,
        (   Len1 < Len
        ->  NewLen = Len1,
            NewMin = V,
            NewMax = N
        ;   NewLen = Len,
            NewMin = CurMin,
            NewMax = CurMax),
        walk(T, N1, NewLen, LstInd, NewMin, NewMax, Min, Max)).

Я получаю почти такие же результаты Simvio Lago

?- length(L, 500000), maplist(random(1,5),L), time(minSubList(1,4,L, S)).
% 8,750,508 inferences, 0.922 CPU in 0.922 seconds (100% CPU, 9486338 Lips)
L = [2, 2, 2, 2, 1, 1, 4, 2, 4|...],
S = [3, 2, 1, 4] .

?- length(L, 1000000), maplist(random(1,5),L), time(minSubList(1,4,L, S)).
% 17,502,632 inferences, 3.017 CPU in 3.017 seconds (100% CPU, 5800726 Lips)
L = [4, 3, 3, 4, 1, 1, 4, 4, 3|...],
S = [4, 3, 2, 1] .

?- length(L, 2000000), maplist(random(1,5),L), time(minSubList(1,4,L, S)).
% 34,999,875 inferences, 6.836 CPU in 6.836 seconds (100% CPU, 5119639 Lips)
L = [2, 1, 2, 1, 3, 3, 3, 1, 3|...],
S = [4, 3, 2, 1] .

Вместо использования nth0 для получения результирующего списка, я попытался append / 2 с этим кодом

minSubList(Min, Max, In, Out) :-
    numlist(Min, Max, NL),
    maplist(make_indice, NL, Il),

    length(In, Len),
    walk(In, 0, Len, Il, 0, Len, VMin, VMax),

    Len2 is VMax - VMin +1,
    length(W, VMin),
    length(Out, Len2),
    append([W, Out, _], In).

Это длится немного дольше. Я получаю эти результаты:

?- length(L, 500000), maplist(random(1,5),L), time(minSubList(1,4,L, S)).
% 9,749,203 inferences, 0.982 CPU in 0.982 seconds (100% CPU, 9930743 Lips)
L = [1, 2, 2, 3, 1, 1, 3, 3, 2|...],
S = [2, 3, 1, 4] .

?- length(L, 1000000), maplist(random(1,5),L), time(minSubList(1,4,L, S)).
% 19,498,491 inferences, 3.136 CPU in 3.136 seconds (100% CPU, 6217658 Lips)
L = [1, 2, 3, 2, 2, 2, 2, 3, 3|...],
S = [2, 1, 3, 4] .

?- length(L, 2000000), maplist(random(1,5),L), time(minSubList(1,4,L, S)).
% 39,001,785 inferences, 7.053 CPU in 7.053 seconds (100% CPU, 5529799 Lips)
L = [3, 4, 3, 2, 2, 1, 1, 3, 2|...],
S = [2, 4, 3, 1] .

Answer 2

Я думаю, что следующий код может быть полезен для вас. Я не доказал его правильность, но, похоже, он работает нормально (даже для очень больших входов). В любом случае, вы можете использовать его как отправную точку для правильной реализации.

shortest_length(List, K, ShortestLength) :-
    shortest_sublist(List, K, Sublist),
    length(Sublist, ShortestLength).

shortest_sublist(List, K, Sublist) :-
    split(List, K, Prefix, Suffix),              % find minimum prefix with all K items
    shrink(Prefix, [First|Rest]),                % shrink that prefix to get a sublist
    append(Rest, Suffix, NewList),
    (   shortest_sublist(NewList, K, NewSublist) % find a new sublist in the rest of the list
    ->  (   length([First|Rest], Len1),
            length(NewSublist, Len2),
            (   Len1 < Len2
            ->  Sublist = [First|Rest])          % new sublist is not shorter than the previous
            ;   Sublist = NewSublist )           % new sublist is shorter than the previous
    ;   Sublist = [First|Rest]  ).               % a new sublist was not found


split(List, K, Prefix, Suffix) :-
    append(Prefix, Suffix, List),
    has(Prefix, K), !.

has(List, K) :-
    forall( between(1, K, Item),
            memberchk(Item, List) ).

shrink([First|Rest], ShrunkList) :-
    (   memberchk(First, Rest)
    ->  shrink(Rest, ShrunkList)
    ;   ShrunkList = [First|Rest] ).

Некоторые результаты для небольших вводов:

?- shortest_length([1,3,1,3,1,3,3,2,2,1], 3, N).
N = 4.

?- shortest_sublist([1,3,1,3,1,3,3,2,2,1], 3, S).
S = [3, 2, 2, 1].

?- shortest_sublist([1,3,1,3,1,3,3,2,2,1,3,3], 3, S).
S = [2, 1, 3].

Некоторые результаты для больших входов:

?- length(L, 500000), maplist(random(1,5),L), time(shortest_sublist(L, 4, S)).
% 11,153,796 inferences, 1.766 CPU in -712561273706905600.000 seconds (?% CPU, 6317194 Lips)
L = [2, 1, 3, 4, 2, 2, 4, 4, 3|...],
S = [4, 1, 2, 3].

?- length(L, 1000000), maplist(random(1,5),L), time(shortest_sublist(L, 4, S)).
% 22,349,463 inferences, 3.672 CPU in -657663431226163200.000 seconds (?% CPU, 6086662 Lips)
L = [2, 2, 4, 3, 2, 2, 3, 1, 2|...],
S = [2, 1, 4, 3].

?- length(L, 2000000), maplist(random(1,5),L), time(shortest_sublist(L, 4, S)).
% 44,655,878 inferences, 6.844 CPU in 919641833393356800.000 seconds (0% CPU, 6525060 Lips)
L = [4, 1, 3, 3, 4, 3, 3, 3, 2|...],
S = [2, 1, 3, 4].

Для малых значений K алгоритм, по-видимому, потребляет время, пропорциональное O (n). Обратите внимание, что, когда длина списка удваивается, время выполнения также удваивается (то есть 500000 → ~ 1,8 с, 1000000 → ~ 3,7 с, 2000000 → ~ 6,9 с).

Я думаю, что узкое место находится в предикате has/1. Таким образом, для более эффективной реализации (для больших значений K) вам нужна более эффективная стратегия проверки членства в списке.

Улучшение: Я понял, что, когда найден подсписок длины K, мы можем заключить, что не существует более короткого списка, который бы содержал все элементы K, и, следовательно, мы можем остановить поиск. Таким образом, предикат shortest_sublist/3 можно изменить следующим образом:

shortest_sublist(List, K, Sublist) :-
    split(List, K, Prefix, Suffix),              % find minimum prefix with all K items
    shrink(Prefix, [First|Rest]),                % shrink that prefix to get a sublist
    length([First|Rest], Len1),
    (   Len1 = K                                 % there is no shorter sublist
    ->  Sublist = [First|Rest]
    ;   append(Rest, Suffix, NewList),
        (   shortest_sublist(NewList, K, NewSublist) % find a new sublist in the rest of the list
        ->  (   length(NewSublist, Len2),
                (   Len1 < Len2
                ->  Sublist = [First|Rest])          % new sublist is not shorter than the previous
                ;   Sublist = NewSublist )           % new sublist is shorter than the previous
        ;   Sublist = [First|Rest]  ) ).             % a new sublist was not found

Вот некоторые результаты, полученные с помощью этой новой версии предиката:

?- shortest_sublist([1,3,1,3,1,3,3,2,2,1], 3, S).
S = [3, 2, 2, 1].

?- shortest_sublist([1,3,1,3,1,3,3,2,2,1,3,3], 3, S).
S = [2, 1, 3].

?- length(L, 500000), maplist(random(1,5),  L), time(shortest_sublist(L, 4, S)).
% 1,041 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [2, 3, 2, 2, 4, 1, 2, 1, 1|...],
S = [3, 2, 4, 1].

?- length(L, 1000000), maplist(random(1,5), L), time(shortest_sublist(L, 4, S)).
% 880 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [3, 2, 1, 1, 4, 4, 3, 1, 1|...],
S = [1, 3, 2, 4].

?- length(L, 2000000), maplist(random(1,5), L), time(shortest_sublist(L, 4, S)).
% 125 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [2, 1, 1, 4, 3, 2, 2, 2, 3|...],
S = [1, 4, 3, 2].