Функция голубя: куда вставить x в отсортированный список

Question

Предположим, у меня есть отсортированный список вещей

{thing1, thing2, thing3, ...}

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

Теперь я ищу функцию, которая принимает

• отсортированный список вещей,
• функция сравнения и
• вещь

и возвращает первую пару соседних объектов в списке, между которыми должна быть вставлена ​​новая вещь. То есть вернуть первую смежную пару {a, b} так, чтобы comp (a, x) и comp (x, b) были истинными, где comp () - функция сравнения.

Например,

pigeon[{1,3,5,7}, Less, 4]

должен вернуть

{3,5}

(РЕДАКТИРОВАТЬ: если заданная вещь меньше, чем первый элемент, a, списка, затем вернуть {Null, a}. Аналогично, если он больше, чем последний элемент, z, тогда вернуть {z, Null} Кроме того, нам нужно либо предположить, что функция сравнения возвращает true для двух идентичных элементов (т. Е. Она похожа на LessEqual, а не Less), или что список вещей не содержит вихревую вещь. Спасибо High Performance Mark за отлов что!)

Моей первой мыслью было использовать Split, а затем взять Last и First, соответственно, из получающихся двух подсписков. Я опубликую это как ответ (или не стесняйтесь опередить меня), но я думаю, что есть более эффективный или элегантный способ.

Answer 1

Я думаю, что это хорошее решение:

Needs["Combinatorica`"]
pigeon[list_, func_, x_] := 
  Join[{Null}, list, {Null}]
    [[ {# - 1/2, # + 1/2}& @
     BinarySearch[list, 0.5, 
      Piecewise[{{0, func[#, x]}, {1, True}}] &] + 1 ]]

, дающее:

> pigeon[{1, 3, 5, 7}, LessEqual, 0]
{Null, 1}

> pigeon[{1, 3, 5, 7}, LessEqual, 3]
{3, 5}

> pigeon[{1, 3, 5, 7}, LessEqual, 4]
{3, 5}

> pigeon[{1, 3, 5, 7}, LessEqual, 9]
{7, Null}

Объяснение : функция Biecewise применяется внутри BinarySearch к списку{1, 3, 5, 7}, чтобы проверить, какие элементы являются LessEqual, BinarySearch находит позицию конца этой метки, и соответствующие элементы возвращаются.В этой реализации используется только BinarySearch, поэтому предполагается, что он достаточно эффективен.

Эту функцию можно легко изменить, чтобы она возвращалась во втором случае {1, 3} вместо этого.
В качестве альтернативы, если 'x' может бытьэлемент списка, что-то вроде этого:

Needs["Combinatorica`"]
pigeon[list_, func_, 
  x_] := (Join[{Null}, 
    list, {Null}])[[Select[{# - 1/2, #, # + 1/2} &@
      BinarySearch[list, 0, 
       Piecewise[{{0, # == x}, {-1, func[#, x]}, {1, True}}] &], 
     IntegerQ] + 1]]

даст:

> pigeon[{1, 3, 5, 7}, LessEqual, 3]
{3}

Answer 2

Использование BinarySearch

Предположение: в списке нет повторяющихся элементов.

BinarySearch имеет альтернативную форму:

BinarySearch[l,k,f]
gives the position of k in the list obtained from l by applying f to 
each element in l.  

, который можно использовать, если ваш список отсортирован по результатам вышеупомянутого "f"

Clear["Global`*"]; Needs["Combinatorica`"];
ret[list_, f_, elem_] := Module[{pos, last},
  pos[l_, e_, g_] := IntegerPart[BinarySearch[l, g[e], g]];
  {
   list[[pos[list, elem, f]]] /. List -> Null,
   If[(last = pos[list, elem, f] + 1) > Length@list, Null, list[[last]]]
  }
 ]  

a = {1, 2, 3, 4, 5};
b = SelectionSort[a, Cos[#1] < Cos[#2] &]

{3, 4, 2, 5, 1}  

Table[{x, N[Cos[x], 2], ret[b, Cos, x]}, 
     {x, 1, 6}]  

{{1,  0.54, {1, Null}}, 
 {2, -0.42, {2, 5}}, 
 {3, -0.99, {3, 4}}, 
 {4, -0.65, {4, 2}}, 
 {5,  0.28, {5, 1}}, 
 {6,  0.96, {1, Null}}
}  

ret[b, Cos, Pi]  
{Null, 3}

Answer 3

Один из возможных подходов:

lst = {1, 3, 5, 7, 9, 11}

{Last@#1, First@#2} & @@ GatherBy[lst, Less[4, #] &]

Выход = {3, 5}

В качестве альтернативы, SplitBy можно заменить на GatherBy.

Answer 4

Уже поздно, поэтому вот частичное решение частично указанной функции:

f[l_List, compFun_Symbol, el_] := 
 Sort[l, compFun] /. {a___, b_ /; compFun[b, el], 
    c_ /; compFun[el, c], d___} -> {b, c}

Я позволил себе не требовать сортировки списка, переданного в функцию f, посколькувходные аргументы включают функцию сравнения.Эта функция работает хорошо, если (а) элемент el не является членом l и (b) в l есть элементы, отсортированные слева и справа от el.Вероятно, это не работает для LessEqual или GreaterEqual.

Если вы хотите уточнить, что вы хотите, чтобы функция возвращала, когда один или оба (a) и (b) неЯ буду рад еще раз взглянуть на это утром.

РЕДАКТИРОВАТЬ:

Я думаю, что это соответствует пересмотренным требованиям.Как и прежде, он не требует, чтобы список ввода уже был отсортирован.

f2[l_List, compFun_, el_] := Sort[Append[l, el], compFun] /. 
{a___, el, b___} :> {If[{a}==={}, Null, Last@{a}], If[{b}==={}, Null, First@{b}]}

Я оставлю это другим, чтобы судить об элегантности и эффективности этого решения (я вижу некоторые очевидные улучшения впоследнее уважение).Теперь вернемся к работе.

Answer 5

Вот еще один бинарный поисковый ответ:

(* Helper for pigeon. Additional arguments a and b give current bounds on the 
   indices of the pigeonhole. *)
pigeon0[l_, f_, x_, a_, b_] := Which[
  b-a==1,                    {l[[a]], l[[b]]},
  f[x, l[[Floor[(a+b)/2]]]], pigeon0[l, f, x, a, Floor[(a+b)/2]],
  True,                      pigeon0[l, f, x, Floor[(a+b)/2], b]]

pigeon[l_, f_, x_] := Which[
  f[x, First@l],                 {Null, First@l},
  f[Last@l, x] && !f[x, Last@l], {Last@l, Null},
  True,                          pigeon0[l, f, x, 1, Length@l]]

Я попробовал это так:

> l = Sort@RandomReal[{0,1}, {10^6}];
> pigeon[l, LessEqual, .5]
{0.4999991874459364, 0.5000000938493356}

Это соответствует моему другому ответу (тот, что с Select), но намного быстрее.

Другие примеры:

> pigeon[{1,3,5,7}, LessEqual, 4]
{3, 5}

> pigeon[{1,3,5,7}, LessEqual, 0]
{Null, 1}

> pigeon[{1,3,5,7}, LessEqual, 9]
{7, Null}

Answer 6

Вот решение, использующее Select (обратите внимание на третий аргумент), которое занимает не более одного прохода по списку и останавливается, когда находит прямоугольник:

pigeon[l_, f_, x_] := Module[{p, r},
  p = Null;
  r = Select[l, If[f[x,#], True, p = #; False]&, 1];
  If[r==={}, {Last@l, Null}, {p, First@r}]]

Примеры:

> pigeon[{1,3,5,7}, LessEqual, 4]
{3, 5}

> pigeon[{1,3,5,7}, LessEqual, 0]
{Null, 1}

> pigeon[{1,3,5,7}, LessEqual, 9]
{7, Null}