Коллеги!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

Сложность N!

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

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

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

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

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

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

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

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


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

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

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

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

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




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

По сравнению с массивом, объем данных увеличивается не сильно:

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


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

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

> Тимохов Дима ©   (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. Хорошая теория очень практична.

> Sha ©   (14.10.16 07:30) [20]

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