Форум PHP программистов > Алгоритм сортировки

[ Поиск ] - [ Пользователи ] - [ Календарь ]

dr_manson

15.12.2011 - 12:17

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


$elems = array(
	'Elem2' => array('Elem1'),
	'Elem1' => array(),
	'Elem4' => array('Elem3'),
	'Elem5' => array('Elem1','Elem2','Elem4'),
	'Elem3' => array('Elem2')
);

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


$elems = array(
	'Elem1' => array(), // идет первым, т.к. нужен для Elem2, Elem5
	'Elem2' => array('Elem1'), // второй, т.к. нужен для Elem3, Elem5
	'Elem3' => array('Elem2'), // третий, т.к. нужен для Elem4
	'Elem4' => array('Elem3'),  // четвертый, т.к. нужен для Elem5
	'Elem5' => array('Elem1','Elem2','Elem4'), // последний
);

При этом необходимо предусмотреть обработку коллизий вида:


$elems = array(
	'Elem1' => array('Elem4'),
	'Elem4' => array('Elem1')
);

Внимание, вопрос: как это реализовать? :)

Спустя 14 минут, 2 секунды (15.12.2011 - 11:31) kovaldm написал(а):

А где у тебя во вложенных массивах указан порядок сортировки?

Спустя 4 минуты, 39 секунд (15.12.2011 - 11:36) dr_manson написал(а):

Отредактировал пример, надеюсь стало понятней))

Спустя 1 минута, 32 секунды (15.12.2011 - 11:38) RCuPeR написал(а):

$first = array(
	'Elem2' => array('Elem1'),
	'Elem1' => array(),
	'Elem4' => array('Elem3'),
	'Elem5' => array('Elem1','Elem2','Elem4'),
	'Elem3' => array('Elem2')
);

sort($first);

echo '<pre>' . print_r($first, 1) . '</pre>';

Не ?

Спустя 5 минут, 18 секунд (15.12.2011 - 11:43) dr_manson написал(а):

Цитата (RCuPeR @ 15.12.2011 - 08:38)

$first = array(
	'Elem2' => array('Elem1'),
	'Elem1' => array(),
	'Elem4' => array('Elem3'),
	'Elem5' => array('Elem1','Elem2','Elem4'),
	'Elem3' => array('Elem2')
);

sort($first);

echo '<pre>' . print_r($first, 1) . '</pre>';

Не ?

В алгоритме сортировки должны учитываться зависимости, указанные во вложенных массивах. Т.е, если


   $elems = array(
       'Elem2' => array('Elem3'),
       'Elem3' => array('Elem1'),
       'Elem1' => array()
   );

то


   $elems = array(
       'Elem1' => array(),
       'Elem3' => array('Elem1'),
       'Elem2' => array('Elem3')
   );

При этом должна обрабатываться ситуация, когда встречается массив вида:


   $elems = array(
       'Elem1' => array('Elem2'),
       'Elem2' => array('Elem1')
   );

Спустя 7 минут, 6 секунд (15.12.2011 - 11:50) Michael написал(а):

Цитата

При этом необходимо предусмотреть обработку коллизий вида:

какое правило для обработки этой ситуации?

Цитата

как это реализовать?

свои попытки реализовать имеются? Это тест какой то тебе задали?

Спустя 8 минут, 14 секунд (15.12.2011 - 11:58) dr_manson написал(а):

Цитата (Michael @ 15.12.2011 - 08:50)

какое правило для обработки этой ситуации?

Правило простое: Выводить сообщение об ошибке.

Цитата (Michael @ 15.12.2011 - 08:50)

свои попытки реализовать имеются? Это тест какой то тебе задали?

Пытался реализовать но, к сожалению, туплю. Никак не найду правильное решение. Это - часть моей будущей CMSки

Если не можете подсказать решение - подскажите хотя бы алгоритм))

Спустя 24 минуты, 10 секунд (15.12.2011 - 12:22) Michael написал(а):

Алгоритм такой.
Заводишь массив

$res = array(
	'Elem2' ,
	'Elem1' ,
	'Elem4' ,
	'Elem5' ,
	'Elem3' ,
);

сортировка произвольная, первоначальная как у

$elems = array(
	'Elem2' => array('Elem1'),
	'Elem1' => array(),
	'Elem4' => array('Elem3'),
	'Elem5' => array('Elem1','Elem2','Elem4'),
	'Elem3' => array('Elem2')
);

пробегая по массиву $elems, первым циклом перебираем все эл-ты, текущий тут $el, а вторым - зависимости по каждому элементу $el. И во втором цикле перебирая "предыдущие" эл-ты $pri, в массиве $res двигаем $el за каждый $pri

Спустя 16 минут, 36 секунд (15.12.2011 - 12:39) dr_manson написал(а):

Спасибо за алгоритм))

Спустя 1 час, 7 минут, 26 секунд (15.12.2011 - 13:46) sergeiss написал(а):

Есть такая функция с названием usort(). Она делает сортировку согласно правилу, определяемому программистом, посредством отдельной call-back функции.

Я бы usort() применил.

Спустя 1 минута, 18 секунд (15.12.2011 - 13:48) dr_manson написал(а):

Ок, попробую usort(). Спасибо!))

Быстрый ответ:

Здесь расположена полная версия этой страницы.