Find the minimun length of a SubList that contains

问题:

The problem is "Find the min length of a List that has all numbers from 1 to K". Input : List, K , N where N is the length of the List

---

My algorithm (it's obviously a bit C oriented) :

1. Set Min= N+1
2. find the first subList (FSub) that has all numbers from 1 to K
3. if there isn't one then Min=0 and finish
4. if there is create a list C that has all the elements of the starting list except the first length(FSub) elements.

FUNCTION THAT FINDS THE MIN (arguments: FSub, C , NewList , Min )

5. if length(Fsub)=K then we don't have to continue searching since we found the min length of sublist
6. If Head of FSub is in Tail of Fsub then we remove Head from the FSub, update min and recurce,
7. If it isn't then we append to FSub the Head of the list C (created above) and recurse.

This stops if C is equal to the empty list

This algorithm seems time-consuming and in some cases of big lists it will propably run out of stack.

---

I asked about the First sublist part and got this code.

findFirstSubListHavingAllColors( NumList, List ,SubList, Len):-
    once((
         append(SubList, _, List),        % get SubList
         subtract(NumList, SubList, []),  % test whether NumList is contained in SubList
         length(SubList, Len)
  )).

I can't connect the dots to find the solution.

---

EXAMPLE

List=[1,3,1,3,1,3,3,2,2,1] , K=3 , N=10

Answer should be 4 because the min SubList that contains numbers 1,2,3 is [1,3,3,2] or [3,2,2,1].

回答1:

I think that this works :

sublist(NumList, In, Out):-
    append([_, Out, _], In),
    forall(member(X, NumList), member(X, Out)).

minSubList(NumList, In, Out) :-
    aggregate_all(min(Len, Out1),(sublist(NumList, In, Out1), length(Out1, Len)), Out).

For example :

?- minSubList([1,2,3], [1,3,1,3,1,3,3,2,2,1], Out).
Out = min(4, [1, 3, 3, 2]).

CAUTION I didn't try for very large lists.

回答2:

Here's another solution that tests for sublists of increasing length (K to len(L)):

min_len(L, K, M):-
  length(L, N),
  numlist(1, K, LK),
  once((
    between(K, N, M),
    length(SubL, M),
    append([_, SubL, _], L),
    subset(LK, SubL)
  )).

test case:

?- min_len([1,3,1,3,1,3,3,2,2,1], 3, Min).
Min = 4