Поиск алгоритма

← →
Тимохов Дима © (2016-10-13 12:29) [0]

Коллеги!

1. Знаю, что тут бывает много людей, знающих алгоритмы. Буду рад, если поможете.

2. К моему стыду я не смог сам придумать алгоритм. А найти в интернете не вышло, ибо не знаю по каким ключевым словам искать.

3. Итак суть задачи.

Есть массив A:
а. Занимает много памяти.
б. Элемент массива большой (т.е. не ссылка на что-то).
в. Есть операция перестановки Swap(I, J).

Есть массив Б:
а. Содержит Integer.
б. Кол-во элементов равно кол-ву элементов А.
в. Каждый элемент массива содержит индекс из А.

Задача:
С помощью операции Swap переставить в А элементы так, чтобы порядок следования элементов был равен тому, который указан в массиве Б.

Ограничения:
а. Массив А - большой. Поэтому нельзя создавать копию А и перетаскивать в нее соотв. значения из А.
б. Время N.

Пример:
Исходно: А = [a, b, c], Б = [1, 2, 0]
После применения алгоритма: A = [b, c, a] - на первом месте становится элемент А с индексом Б[0], на втором Б[1], на третьем Б[2].

У меня есть ощущение, что это какой-то стандартный алгоритм. Просто я его не знаю.

Благодарю, если подскажите.

← →
iop © (2016-10-13 12:56) [1]

исходный управляющий механизм неверен.

ибо после очередного свапа как ты отличишь b стоящее в нулевой позиции массива а.

это оно там вначале так стояло, или его уже задвинули свапом?

← →
iop © (2016-10-13 13:00) [2]

к тому же управляющая инфа в Б актуальна только на начало сортировки.
и ее актуальность протухнет после первых же свапов.

← →
iop © (2016-10-13 13:08) [3]

хотя если скользить слева направо по длине Б и делать свап если справа меньше чем слева.
если больше то свап не делать

← →
Тимохов Дима © (2016-10-13 13:11) [4]

> iop © (13.10.16 12:56) [1]
> исходный управляющий механизм неверен.

Никто не мешает сделать еще один массив индексов и помнить, кто куда был переставлен. Но я пока в этих индексах запутался.

Повторюсь. У меня есть ощущение, что задача решаема и не нова. Должен быть алгоритм известный.

← →
iop © (2016-10-13 13:27) [5]

и помнить, кто куда был переставлен.

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

есть два подхода.

академический.
это произвольная взятая наугад структура языка и долгий поиск "научного" алгоритма перестановок

разумный.
структура выбирается так, чтобы перестановки выполнялись за один проход и без головной боли.

в твоем случае взятая наугад структура - это массив.
элементы которого ничего не помнят про то где они были секунду назад

← →
Rouse_ © (2016-10-13 13:59) [6]

Двунаправленный список вместо первого элемента. Незачто Дим

← →
Sha © (2016-10-13 14:07) [7]

> Тимохов Дима © (13.10.16 12:29)

Массив Б задает перестановку элементов массива А,
поэтому удобнее всего использовать то,
что любая перестановка есть совокупность независимых циклов.

Т.е. переставлять удобнее операцией Swap(), у которой произвольное число аргументов.

Ранее использованные при этой позиции можно помечать -1 или собственным номером.

Вот и весь алгоритм.

Если N-местный Swap() не разрешается использовать,
то его можно эмулировать N-1 двуместными.

← →
Sha © (2016-10-13 15:19) [8]

type TElem= int64; TElems= array of TElem; TPlaces= array of integer; procedure Swap(var e1, e2: TElem); begin; e1:=e1 xor e2; e2:=e1 xor e2; e1:=e1 xor e2; end; procedure Place(a: TElems; b: TPlaces); var i, j, k: integer; begin; for i:=0 to Length(b)-1 do begin; j:=i; while true do begin; k:=b[j]; b[j]:=j; if k=i then break; Swap(a[j],a[k]); j:=k; end; end; end; procedure TMainForm.Button1Click(Sender: TObject); var a: TElems; b: TPlaces; i: integer; begin; SetLength(a,6); a[0]:=0; a[1]:=1; a[2]:=2; a[3]:=3; a[4]:=4; a[5]:=5; SetLength(b,6); b[0]:=1; b[1]:=2; b[2]:=0; b[3]:=5; b[4]:=4; b[5]:=3; Place(a, b); for i:=0 to Length(a)-1 do Memo1.Lines.Add(IntToStr(a[i])); end;

← →
Тимохов Дима © (2016-10-13 17:47) [9]

> Sha © (13.10.16 15:19) [8]

Честно скажу, очень детально не вникал, но сложность все же не N.
Ибо Swap идет в цикле в цикле. Т.е. N в какой-то степени. Думаю, что N^2 в общем случае. Виноват, если не точно написал в исходной постановке, что сложность (кол-во вызовов) именно Swap д.б. N.

> Rouse_ © (13.10.16 13:59) [6]
> Двунаправленный список вместо первого элемента. Незачто Дим

Долго думал. Не сообразил, что ты имеешь в виду.

-----
НО! Вдохновленный тем, что задача скорее решаема, чем нет, написал свой вариант! И не спрашивайте, как он работает!))

Делал методом индукции: от частного к общему. Нашел закономерности, запрограммировал, и проверил статистически.

Самое главное тут массив P. Он содержит позиции элементов, которые в ходе перестановок тоже меняются.

Сложность N!

procedure SwapInt64(var E1, E2: Int64); var Temp: Int64; begin Temp := E1; E1 := E2; E2 := Temp; end; procedure SwapInteger(var E1, E2: Integer); var Temp: Integer; begin Temp := E1; E1 := E2; E2 := Temp; end; procedure TForm1.Button1Click(Sender: TObject); var A: array of Int64; B, P: array of Integer; I, J, K: Integer; begin SetLength(A, 8); A[0]:=5; A[1]:=2; A[2]:=3; A[3]:=7; A[4]:=1; A[5]:=6; A[6]:=4; A[7]:=0; SetLength(B, 8); B[0]:=7; B[1]:=4; B[2]:=1; B[3]:=2; B[4]:=6; B[5]:=0; B[6]:=5; B[7]:=3; SetLength(P, Length(B)); for I := 0 to Length(B)-1 do P[B[I]] := I; for I := 0 to Length(B)-1-1{no last element} do begin J := B[I]; K := P[I]; if I <> J then begin SwapInt64(A[I], A[J]); SwapInteger(B[I], B[K]); SwapInteger(P[I], P[J]); end; end; for I := 0 to Length(A)-1 do Memo1.Lines.Add(IntToStr(A[I])); end;

← →
Sha © (2016-10-13 17:53) [10]

> Тимохов Дима © (13.10.16 17:47) [9]
> Честно скажу, очень детально не вникал, но сложность все же не N.
> Ибо Swap идет в цикле в цикле. Т.е. N в какой-то степени.
> Думаю, что N^2 в общем случае.
> Виноват, если не точно написал в исходной постановке,
> что сложность (кол-во вызовов) именно Swap д.б. N.

а ты попробуй вникнуть

← →
iop © (2016-10-13 17:57) [11]

все верно.
если задумал круглое носить, то надо носить. а квадратное катать.

похожий пример из античности:
грид с порядком колонок установленным в дизайне и пользовательская настройка очередности колонок.

сортируем пользовательский список колонок по индексам и слева направо присваиваем индексы живым колонкам грида.

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

вывод:
если есть несколько однотипных элементов и рука уже потянулась объявить массив - останови ее и подумай.
массив ли здесь удобен.

← →
Тимохов Дима © (2016-10-13 18:29) [12]

> Sha © (13.10.16 17:53) [10]
> > Тимохов Дима © (13.10.16 17:47) [9]
> > Честно скажу, очень детально не вникал, wap д.б. N.
> а ты попробуй вникнуть

Александр, виноват - был не прав. Сложность тоже N.

Скажи, пожалуйста, это твой алгоритм или из литературы? Кнута, например.
Я почему спрашиваю - ощущение, что эти алгоритмы уже все разработаны в рамках теории. Не хочу в следующий раз сам придумывать, что к чему. Поучиться хочу. Тема то хоть какая, где эти алгоритмы изучают?

← →
Юрий Зотов © (2016-10-13 18:41) [13]

> Тимохов Дима © (13.10.16 17:47) [9]

>> Rouse_ © (13.10.16 13:59) [6]
>> Двунаправленный список вместо первого элемента.

> Долго думал. Не сообразил, что ты имеешь в виду.

type PDataRecord = ^TDataRecord; TDataRecord = packed record Data: тип_данных (тот же, что у элементов массива A); Prev: PDataRecord; // Адрес предыдущей записи, у первой - nil Next: PDataRecord; // Адрес следующей записи, у последней - nil FirstDataRecord: PDataRecord; // Адрес первой записи в списке

И вместо массива A строим список записей TDataRecord. После чего можем перемещать элементы этого списка как угодно, просто меняя значения полей Prev и Next в элементах. Причем скорость такой сортировки будет очень высокой, так как сами элементы никуда не перемещаются.

По сравнению с массивом, объем данных увеличивается не сильно:
количество_элементов * 2 * SizeOf(Pointer)

← →
Игорь Шевченко © (2016-10-13 18:59) [14]

> Тема то хоть какая, где эти алгоритмы изучают?

Крайне рекомендую почитать
https://www.ozon.ru/context/detail/id/20883551/

В то время процент правильных книжек был больше, хотя книжек меньше :)

← →
Sha © (2016-10-13 20:10) [15]

> Тимохов Дима © (13.10.16 18:29) [12]

Не помню, где бы встречался конкретно этот алгоритм.
Но в теории групп есть много всего про перестановки,
и много похожего обычно всплывает на практических занятиях)

Опять же есть Липский и http://guildalfa.ru/alsha/node/26

Коллеги, всем спасибо!

Есть, что поизучать.
Да и задачу решил.

> Sha © (13.10.16 20:10) [15]

Спасибо!
Вот же у программистов мука...
Сижу и думаю, какой алгоритм брать - свой или твой.
Свой - он свой. Твой - проще.
Вот вопрос))

> Тимохов Дима © (13.10.16 22:31) [16]
> Сижу и думаю, какой алгоритм брать - свой или твой.
> Свой - он свой. Твой - проще.

Вот тут похожий случай:
http://www.sql.ru/forum/1234205/kto-smozhet-zastavit-3-potoka-rabotat-so-skorostu-odnogo
свой алгоритм генерации сочетаний оказался примерно в 10 раз менее стандартного)

Чтоб совсем помочь тебе определиться - вот пара быстрых реализаций,
с двуместным и многоместным свопами:

type TElem= integer; PElems= PIntegerArray; PPlaces= PIntegerArray; procedure Place1(a: PElems; b: PPlaces; count: integer); var temp: TElem; i, j, k: integer; begin; for i:=count-1 downto 1 do begin; j:=i; while true do begin; k:=b[j]; b[j]:=j; if k=i then break; temp:=a[j]; a[j]:=a[k]; a[k]:=temp; //Swap(a[j],a[k]); j:=k; end; end; end; procedure Place2(a: PElems; b: PPlaces; count: integer); var temp: TElem; i, j, k: integer; begin; for i:=count-1 downto 1 do begin; k:=b[i]; if k<>i then begin; j:=i; b[j]:=j; temp:=a[j]; repeat; a[j]:=a[k]; j:=k; k:=b[j]; b[j]:=j; until k=i; a[j]:=temp; end; end; end; function FormatArray(a: PElems; count: integer): string; var i: integer; begin; Result:=""; for i:=0 to count-1 do Result:=Result+" "+IntToStr(a[i]); end; procedure TMainForm.Button1Click(Sender: TObject); var a, b: array of integer; i, j, k, count: integer; t: array[0..2] of cardinal; begin; // SetLength(a,6); a[0]:=0; a[1]:=1; a[2]:=2; a[3]:=3; a[4]:=4; a[5]:=5; // SetLength(b,6); b[0]:=1; b[1]:=2; b[2]:=0; b[3]:=5; b[4]:=4; b[5]:=3; count:=10; SetLength(a,count); SetLength(b,count); for i:=0 to count-1 do a[i]:=i; for i:=0 to count-1 do b[i]:=i; for i:=count-1 downto 1 do begin; j:=Random(i+1); k:=a[j]; a[j]:=a[i]; a[i]:=k; end; t[0]:=GetTickCount; for i:=1 to 1000000 do begin; Place1(@a[0], @b[0], count); Place1(@b[0], @a[0], count); end; t[1]:=GetTickCount; for i:=1 to 1000000 do begin; Place2(@a[0], @b[0], count); Place2(@b[0], @a[0], count); end; t[2]:=GetTickCount; Memo1.Lines.Add(FormatArray(@a[0], count)); Memo1.Lines.Add(FormatArray(@b[0], count)); Memo1.Lines.Add(IntToStr(t[1]-t[0])); Memo1.Lines.Add(IntToStr(t[2]-t[1])); end;

В предыдущем посте опечатка: в 10 раз медленнее стандартного

> Sha © (13.10.16 23:37) [17]

> Чтоб совсем помочь тебе определиться

Спасибо. Буду изучать!

ЗЫ Просмотрел твой алгоритм. Кажется (помню, что креститься надо когда кажется:) ), что понимаю, как он работает. А, может, и не понимаю. Но, чьерт попьери, вот как ты его придумал?! Вот свой я придумал, как говорил, индукцией - написал на бумажке, заметил закономерности, запрограммировал - экспериментально (миллионы случайных перестановок случайных данных с верификацией) доказал правильность. А вот в твоем случае - как проходило построение алгоритма? Понимаю, что вопрос, скорее, философский. Но все же, поделись, пожалуйста))

> Тимохов Дима © (14.10.16 00:35) [19]

Есть теория, первые изучаемые там теоремы о том,
что любая перестановка разложима на независимые циклы,
т.е. представима в виде суперпозиции независимых циклических перестановок,
а любой цикл длины N разложим на N-1 транспозицию.
И то, и другое легко программируется.

P.S. Хорошая теория очень практична.

Поиск алгоритма Найти похожие ветки