Есть файл вида (id1, id2). Айдишники - вершины графов. В строках - связи между вершинами.
1 2
1 3
1 4
2 5
7 5
3 4
8 6
9 22
....
Одна и та же вершина может находиться как в id1 так и в id2. На выходе надо получить такой массив:
0 => '1,2,3,4,5,6,7',
1 => '8,6',
2 => '9,22',
...
Иными словами, получить все графы из возможных комбинаций. Совсем не понимаю рекурсию =(
Помогите пожалуйста написать функцию. Заранее спс!
Спустя 18 минут, 54 секунды (10.07.2010 - 23:12) qpayct написал(а):
ничего не понимаю. может я просто не силён в математике.....
опиши подробно логический ход своей мысли, в каком виде именно ты из первого хочешь получать второе?
твоя рекурсия должна посылать в саму себя что? построчно id1 и id2 или как?
и что с ними тебе надо делать? в каком порядке встраивать в массив? а то задача вроде интересная, а с какого боку подходить пока не ясно....
опиши подробно логический ход своей мысли, в каком виде именно ты из первого хочешь получать второе?
твоя рекурсия должна посылать в саму себя что? построчно id1 и id2 или как?
и что с ними тебе надо делать? в каком порядке встраивать в массив? а то задача вроде интересная, а с какого боку подходить пока не ясно....
Спустя 16 минут, 19 секунд (10.07.2010 - 23:28) drone076 написал(а):
| Цитата (qpayct @ 10.07.2010 - 20:12) |
| ничего не понимаю. может я просто не силён в математике..... опиши подробно логический ход своей мысли, в каком виде именно ты из первого хочешь получать второе? |
Может не очень понятно написал, сорри. Суть такая, в файле в строках описаны графы. В каждой строке указаны связи вершин. Например, из файла выше: Вершина номер 1 связана с вершинами 2, 3 и 4. В свою очередь, вершина номер 2 связана с вершиной номер 5. А вершина 5 с 7. В итоге получается описание всех вершин одного графа: 1,2,3,4,5,7. Другой граф состоит всего из двух точек с номерами 9 и 22.
Надо получить массив, в котором будут описаны все графы, полученные из файла.
В первом посте опечатка у меня в результате, вершина номер 6 лишняя в первой строке. Надеюсь более понятно расписал.
Спустя 16 минут, 8 секунд (10.07.2010 - 23:44) qpayct написал(а):
| Цитата (drone076 @ 10.07.2010 - 22:28) |
| В первом посте опечатка у меня в результате, вершина номер 6 лишняя в первой строке. |
вот именно это и запутало.... в пхп это делается элементарно, Ватсон
и никакая рекурсия не нужна// открываешь построчно файл
while($string = // тут пишешь условие выдавать построчно пока не EOF)
{// каждой строке делаешь вот это
$id = explode(" ",$string);
$array[$id[0]] = $id[1];
}
print_r($array);
Спустя 8 часов, 23 минуты, 36 секунд (11.07.2010 - 08:08) Nord написал(а):
Тогда уж скорее:
Должно вывести:
$graphs = array();
$gcount = 0;
// открываешь построчно файл
while($string = // тут пишешь условие выдавать построчно пока не EOF)
{// каждой строке делаешь вот это
$id = explode(" ",$string);
$i = 0;
while ($i < $gcount){
// Проверяем, принадлежат ли вершины графу
$in0 = in_array($id[0], $graphs[$i]));
$in1 = in_array($id[1], $graphs[$i]));
if ($in0) {
if (!$in1) $graphs[$i][] = $id[1]; // В графе есть веришина $id[0], но нет веришины $id[1] => добавляем
break; // граф найден
} else {
if ($in1) {
$graphs[$i][] = $id[0]; // В графе есть веришина $id[1], но нет веришины $id[0] => добавляем
break; // граф найден
}
}
$i++;
}
if ($i == $gcount){
// графа с такими вершинами еще нет => создадим такой
$graphs[] = array($id[0], $id[1]);
$gcount++;
}
}
print_r($graphs);
Должно вывести:
Array
(
[0] => Array('1' , '2' , '3', '4', '5', '7'),
[1] => Array('8', '6'),
[2] => Array('9', '22')
)
Спустя 27 минут, 57 секунд (11.07.2010 - 08:36) linker написал(а):
Это банальное дерево, в связи с этим не понятен результирующий массив, да и требования ТС получить такой массив.
Спустя 9 минут, 47 секунд (11.07.2010 - 08:45) Ineed$ написал(а):
Можно конечно, только толку от этого? Сам себе усложняешь жизнь.. А так всё чётко поделено в ключах одно в значениях другое и кода в разы меньше
и зачем счетчик ставить? Ставишь пустую ячейку [] и всё.
и зачем счетчик ставить? Ставишь пустую ячейку [] и всё.
Спустя 31 минута, 55 секунд (11.07.2010 - 09:17) Nord написал(а):
Ineed$ это вы кому?
Спустя 36 минут, 23 секунды (11.07.2010 - 09:54) drone076 написал(а):
Nord спасибо огромное!!!! То что надо. Про рекурсию думалось, ибо казалось, что задача похожа на Поиск компонент сильной связности.