找到一个不包含随机数列表数量的大间隔
假设我有一个随机整数的列表[x1,..,xn]
。
此列表没有排序,我想避免使用
的算法 分类,或与排序具有相同的复杂性。
我如何找到一个Interval a..b
,带有min(xi)< a
和b< max(xi)
,
因此,间隔不包含列表中的任何数字? 是
有一些原始算法,可以避免分类
复杂性吗?它不必是最大的间隔。
示例:
?- find([3,17,5,13], I)
I = 14..16
对于每个3
,17
,5
和13
我们有这些整数数字不是
在间隔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 技术交流群。

发布评论
评论(3)
似乎是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.
这是一个答案,表明平均长度
发现的间隔可能会因
算法。结果是:
/* 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).
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
导致SWI-Prolog:
找到最大的间隔。然后,您可以使用该间隔列表来创建较小间隔,例如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。
Result in swi-prolog:
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.