找到一个不包含随机数列表数量的大间隔

发布于 01-24 01:45 字数 521 浏览 3 评论 0原文

假设我有一个随机整数的列表[x1,..,xn]
此列表没有排序,我想避免使用
的算法 分类,或与排序具有相同的复杂性。

我如何找到一个Interval a..b,带有min(xi)< ab< max(xi)
因此,间隔不包含列表中的任何数字? 是
有一些原始算法,可以避免分类

复杂性吗?它不必是最大的间隔。

示例:

  ?- find([3,17,5,13], I)
  I = 14..16

对于每个317513我们有这些整数数字不是
在间隔14..16中包含。但是4..4也可能是解决方案,
6..12或较小的间隔。

Suppose I have a list of random integer numbers [x1,..,xn].
This list is not sorted, and I want to avoid an algorithm that
sorts, or has the same complexity as sorting.

How would I find an interval a..b with min(xi)<a and b<max(xi),
so that the interval does not contain any numbers from the list?
Is
there some Prolog algorithm for that, that avoids sorting

complexity? It need not be the greatest interval.

Example:

  ?- find([3,17,5,13], I)
  I = 14..16

For each 3,17,5 and 13 we have that these integer numbers are not
contained in the interval 14..16. But 4..4 could also be a solution,
or 6..12 or smaller intervals.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

对你而言2025-01-31 01:45:30
large_interval(Lst, Lower, Upper) :-
    % Select 2 numbers
    select(Int1, Lst, Lst1),
    select(Int2, Lst1, Lst2),
    Lower is Int1 + 1,
    Upper is Int2 - 1,
    % Break symmetry by imposing order
    Upper >= Lower,
    % Ensure rest of list allows this range
    outside_range(Lst2, Lower, Upper).

outside_range([], _, _).
outside_range([H|T], Lower, Upper) :-
    once(H > Upper ; H < Lower),
    outside_range(T, Lower, Upper).

导致SWI-Prolog:

?- findall(Lower-Upper, large_interval([3,17,5,13], Lower, Upper), Pairs).
Pairs = [4-4,6-12,14-16].

找到最大的间隔。然后,您可以使用该间隔列表来创建较小间隔,例如6-12可以分为:

7-12
8-12
9-12
10-12
11-12
12-12
7-11
8-11
9-11
10-11
11-11
ETC。

large_interval(Lst, Lower, Upper) :-
    % Select 2 numbers
    select(Int1, Lst, Lst1),
    select(Int2, Lst1, Lst2),
    Lower is Int1 + 1,
    Upper is Int2 - 1,
    % Break symmetry by imposing order
    Upper >= Lower,
    % Ensure rest of list allows this range
    outside_range(Lst2, Lower, Upper).

outside_range([], _, _).
outside_range([H|T], Lower, Upper) :-
    once(H > Upper ; H < Lower),
    outside_range(T, Lower, Upper).

Result in swi-prolog:

?- findall(Lower-Upper, large_interval([3,17,5,13], Lower, Upper), Pairs).
Pairs = [4-4,6-12,14-16].

That finds the biggest intervals. Then you can use that list of intervals to create the smaller intervals, e.g. 6-12 can split into:

7-12
8-12
9-12
10-12
11-12
12-12
7-11
8-11
9-11
10-11
11-11
etc.

时光沙漏2025-01-31 01:45:30

似乎是O( n )的解决方案是:

find(List, Low-High) :-
    min_list(List, Min),
    max_list(List, Max),
    find(List, Min, Max, Low0, High0),
    Low0 + 1 =< High0 - 1,
    !,
    Low is Low0 + 1,
    High is High0 - 1.

find([], Low, High, Low, High).
find([X|Xs], Low0, High0, Low, High) :-
    (   between(Low0, High0, X)        % split interval
    ->  (   find(Xs, X, High0, Low, High)
        ;   find(Xs, Low0, X, Low, High) )
    ;   find(Xs, Low0, High0, Low, High) ).

test(Length) :-
    Max is 10*Length,
    randseq(Length, Max, List),
    time(find(List, Low-High)),        % check efficiency
    forall(member(X, List),            % check answer correctness
           not(between(Low, High, X))). 

示例:

?- find([1,2,1,1,3], I).
false.

?- find([1,2,1,9,1,3], I).
I = 4-8.

?- find([3,17,5,13], I).
I = 14-16.

经验复杂性结果:当列表长度加倍时,运行时间也会增加一倍。

?- test(1000000).
% 8,533,279 inferences, 0.328 CPU in 0.344 seconds (95% CPU, 26006184 Lips)
true.

?- test(2000000).
% 18,483,177 inferences, 0.656 CPU in 0.687 seconds (95% CPU, 28164841 Lips)
true.

?- test(4000000).
% 39,679,989 inferences, 1.328 CPU in 1.337 seconds (99% CPU, 29876698 Lips)
true.

A solution that seems to be O(n) is:

find(List, Low-High) :-
    min_list(List, Min),
    max_list(List, Max),
    find(List, Min, Max, Low0, High0),
    Low0 + 1 =< High0 - 1,
    !,
    Low is Low0 + 1,
    High is High0 - 1.

find([], Low, High, Low, High).
find([X|Xs], Low0, High0, Low, High) :-
    (   between(Low0, High0, X)        % split interval
    ->  (   find(Xs, X, High0, Low, High)
        ;   find(Xs, Low0, X, Low, High) )
    ;   find(Xs, Low0, High0, Low, High) ).

test(Length) :-
    Max is 10*Length,
    randseq(Length, Max, List),
    time(find(List, Low-High)),        % check efficiency
    forall(member(X, List),            % check answer correctness
           not(between(Low, High, X))). 

Examples:

?- find([1,2,1,1,3], I).
false.

?- find([1,2,1,9,1,3], I).
I = 4-8.

?- find([3,17,5,13], I).
I = 14-16.

Empirical complexity results: when list length doubles, running time also doubles.

?- test(1000000).
% 8,533,279 inferences, 0.328 CPU in 0.344 seconds (95% CPU, 26006184 Lips)
true.

?- test(2000000).
% 18,483,177 inferences, 0.656 CPU in 0.687 seconds (95% CPU, 28164841 Lips)
true.

?- test(4000000).
% 39,679,989 inferences, 1.328 CPU in 1.337 seconds (99% CPU, 29876698 Lips)
true.
聊慰2025-01-31 01:45:30

这是一个答案,表明平均长度
发现的间隔可能会因
算法。结果是:

/* distance algorithm = slago with heuristic algorithm */
?- aggregate_all((sum(D), count),
        (between(1,1000,_), list(L), find(L, Lo-Hi), D is Hi-Lo+1), (R,C)),
   S is R/1000.
R = 29988, C = 1000, S = 29.988.

/* bisection algorithm */
?- aggregate_all((sum(D), count),
         (between(1,1000,_), list(L), find(L, Lo-Hi), D is Hi-Lo+1), (R,C)),
    S is R/1000.
R = 14162, C = 999, S = 14.162.

/* slago algorithm */
?- aggregate_all((sum(D), count),
          (between(1,1000,_), list(L), find(L, Lo-Hi), D is Hi-Lo+1), (R,C)),
     S is R/1000.
R = 10094, C = 1000, S = 10.094.

这是slago算法;

% find(+List, -Interval)
find(L, R) :-
   find(L, 0-999, R), !.

% find(+List, +Interval, -Interval)
find([X|L], Lo-Hi, R) :-
   X < Lo, !, find(L, Lo-Hi, R).
find([X|L], Lo-Hi, R) :-
   X > Hi, !, find(L, Lo-Hi, R).
find([X|L], Lo-_, R) :-
   Lo < X,
   Y is X-1, find(L, Lo-Y, R).
find([X|L], _-Hi, R) :-
   X < Hi,
   Y is X+1, find(L, Y-Hi, R).
find([], R, R).

% list(-List)
list(L) :-
   findall(X, (between(1,100,_), random(1000, X)), L).

然后是一分配算法,替换了3。和4。子句:

find([X|L], Lo-Hi, R) :-
   M is (Lo+Hi)//2, X < M, M =< Hi, !,
   find(L, M-Hi, R).
find([_|L], Lo-Hi, R) :-
   M is (Lo+Hi)//2-1, Lo =< M,
   find(L, Lo-M, R).

然后距离距离算法,该算法是slago的启发式:

find([X|L], Lo-Hi, R) :-
   X-Lo > Hi-X, Lo < X, !,
   Y is X-1, find(L, Lo-Y, R).
find([X|L], _-Hi, R) :-
   X < Hi,
   Y is X+1, find(L, Y-Hi, R).

Here is an answer, that shows that the average length of the
found interval can vary considerably depending on the
algorithm. The results are:

/* distance algorithm = slago with heuristic algorithm */
?- aggregate_all((sum(D), count),
        (between(1,1000,_), list(L), find(L, Lo-Hi), D is Hi-Lo+1), (R,C)),
   S is R/1000.
R = 29988, C = 1000, S = 29.988.

/* bisection algorithm */
?- aggregate_all((sum(D), count),
         (between(1,1000,_), list(L), find(L, Lo-Hi), D is Hi-Lo+1), (R,C)),
    S is R/1000.
R = 14162, C = 999, S = 14.162.

/* slago algorithm */
?- aggregate_all((sum(D), count),
          (between(1,1000,_), list(L), find(L, Lo-Hi), D is Hi-Lo+1), (R,C)),
     S is R/1000.
R = 10094, C = 1000, S = 10.094.

Here is the slago algorithm;

% find(+List, -Interval)
find(L, R) :-
   find(L, 0-999, R), !.

% find(+List, +Interval, -Interval)
find([X|L], Lo-Hi, R) :-
   X < Lo, !, find(L, Lo-Hi, R).
find([X|L], Lo-Hi, R) :-
   X > Hi, !, find(L, Lo-Hi, R).
find([X|L], Lo-_, R) :-
   Lo < X,
   Y is X-1, find(L, Lo-Y, R).
find([X|L], _-Hi, R) :-
   X < Hi,
   Y is X+1, find(L, Y-Hi, R).
find([], R, R).

% list(-List)
list(L) :-
   findall(X, (between(1,100,_), random(1000, X)), L).

Then a bisection algorithm, replace the 3. and 4. clause by:

find([X|L], Lo-Hi, R) :-
   M is (Lo+Hi)//2, X < M, M =< Hi, !,
   find(L, M-Hi, R).
find([_|L], Lo-Hi, R) :-
   M is (Lo+Hi)//2-1, Lo =< M,
   find(L, Lo-M, R).

And then distance algorithm, which is slago with heuristic:

find([X|L], Lo-Hi, R) :-
   X-Lo > Hi-X, Lo < X, !,
   Y is X-1, find(L, Lo-Y, R).
find([X|L], _-Hi, R) :-
   X < Hi,
   Y is X+1, find(L, Y-Hi, R).
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文