Как найти циклы в массиве?

Question

[nickolay0704]

Имеется массив такого вида:

Array
(
    [385] => 392
    [386] => 392
    [387] => 392
    [390] => 402
    [402] => 421
    [405] => 401
    [409] => 416
    [410] => 401
    [414] => 402
    [416] => 389
    [420] => 421
    [421] => 422
    [422] => 420
)

У каждого элемента должно быть своё конечное значение. Но есть в этом массиве проблемное место:

[420] => 421
[421] => 422
[422] => 420

420 переходит в 421, 421 в 422, 422 снова в 420 - тут идёт зацикливание цепочки.

Если есть зацикливание, то как получить эти три значения: 420, 421 и 422?

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

Как получить эти зацикленные цепочки?

Comments

[Виктор Кожухарь]

Я не совсем понимаю, что вам нужно. Нужно просто понять, есть ли где-то в цепочке зацикленность?

[nickolay0704]

Виктор Кожухарь, если есть зацикленность, то вывести элементы, которые создают эту зацикленность

[Антон Шаманов]

очень мутно описаны условия - почему [385] => 392 [386] => 392 это не зацикливание?

[nickolay0704]

Антон Шаманов, потому что нет ключа в массиве со значением 392

[ksnk]

Антон Шаманов, Наверное потому, что 392 нету. Ну, или там не цикл, а тупиковая ветка.
Описано действительно мутно.

Answer 1

[0xD34F]

Вот говнокод:

$result = [];

foreach ($arr as $n) {
  for ($visited = []; array_key_exists($n, $arr); $visited[] = $n, $n = $arr[$n]) {
    if (($i = array_search($n, $visited)) !== false) {
      $loop = array_slice($visited, $i);
      if (empty(array_intersect(array_column($result, 0), $loop))) {
        $result[] = $loop;
      }
      break;
    }
  }
}

или

$result = [];
$visited = [];
$iLoop = -1;

foreach ($arr as $n) {
  for ($iLoop++; isset($arr[$n]); $visited[$n] = $iLoop, $n = $arr[$n]) {
    if (isset($visited[$n])) {
      if ($visited[$n] === $iLoop) {
        for ($loop = [ $m = $n ]; ($m = $arr[$m]) !== $n; $loop[] = $m) ;
        $result[] = $loop;
      }
      break;
    }
  }
}

Answer 2

[ksnk]

Вот более оптимизированный говнокод ;)

$array = [
    385 => 392,
    386 => 392,
    387 => 392,
    390 => 402,
    402 => 421,
    405 => 401,
    409 => 416,
    410 => 401,
    414 => 402,
    416 => 389,
    420 => 421,
    421 => 422,
    422 => 420,
];

foreach ($array as $key => $value) {
    $level=0;
    $leaf=[$key=>$level]; $v=$value;
    while(true){
        if(!isset($array[$v])) break;
        $v=$array[$v];
        if(isset($leaf[$v])) {
            // loop found
            // is it real loop ?
            if($key==$v) {
                printf("\n %s => %s", $key, $value);
            }
            break;
        }
        $leaf[$v]=++$level;
    }
}

Comments

[ksnk]

Если все еще интересует - вот почти не говнокод. По крайней мере - o(n), во всяком случае - каждая вершинка обходится 1 раз.

$array = [
    385 => 386,
    386 => 385, // миницикл на 2
    387 => 385,
    390 => 402,
    402 => 421,
    405 => 401,
    409 => 409, // микроцикл
    410 => 401,
    414 => 402,
    416 => 389,
    420 => 421,
    421 => 422,
    422 => 420,
    423 => 424,
    424 => 425,
    425 => 426,
    426 => 427,
    427 => 420,
];
//*/

/**
 * Расставляет ветки по уровням
 */
$leaf = []; // уровни веток в нашем "дереве";
$loop = []; // циклы в дереве

$minlev = 1; // минимальный и максимальный уровень
$maxlev = 0;

foreach ($array as $key => $value) {
    $v = $value;
    if (!isset($leaf[$key])) {// совсем нехоженая ветка?
        $minlev -= count($array); // чтобы гарантированно не пересекаться уровнями
        $leaf[$key] = $minlev;
    }
    $level = $minlev;
    while (true) {
        if (!isset($array[$v])) // ссылка вовне дерева, дальше не идем
            break;
        if (!isset($leaf[$v])) { // первый раз?
            $leaf[$v] = ++$maxlev;
            $level = $maxlev;
        } else if ($leaf[$v] > $level) {
            $level = $leaf[$v]; ; // продолжаем? А зачем ?
            break;
        } else { // loop found
            // уже включен этот цикл ?
            $t = $v;
            do {
                if (isset($loop[$t])) break 2;
                if (!isset($array[$t])) break 2; // это не цикл
                $t = $array[$t];
            } while ($t != $v);
            $loop[$v] = 0;// пометили
            break;
        }
        $v = $array[$v];
    }
}
if (!empty($loop)) {
    printf("loops found:");
    foreach ($loop as $k => $v) {
        echo "\n:";
        $t = $k;
        do {
            printf("%s=>%s,", $t, $array[$t]);
            $t = $array[$t];
        } while (isset($array[$t]) && $t != $k);
    }
} else {
    printf("no loops found\n");
}

Могу пояснить, если все еще интересно...

[nickolay0704]

ksnk, предыдущий вариант тоже выполняет то, что нужно, пока что его оставили, благодарю за помощь в решении проблемы

Answer 3

[Антон Шаманов]

не совсем понятно зачем там рекурсия

$i = 1;
foreach ($array as $key => $value) {
    $arrayTail = array_slice($array, $i);
    if (in_array($key, $arrayTail)) {
         // зацикливание
    }
    $i++;
}

Comments

[nickolay0704]

вывел ключи массива

// зацикливание
$arKeys[] = $key;

получился такой массив

Array
(
    [0] => 402
    [1] => 420
)

[Антон Шаманов]

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

if (array_intersect(array_keys($array), $array)) {
   есть зацикливания
}

[nickolay0704]

Антон Шаманов, да, искал уже таким образом

Array
(
    [390] => 402
    [402] => 421
    [414] => 402
    [420] => 421
    [421] => 422
    [422] => 420
)

ближе к желаемому результату, но не то

[Антон Шаманов]

nickolay0704, ну и?

[Антон Шаманов]

nickolay0704, я вообще системы в твои ответах не вижу, исходя из условий, мы получаем

[402] => 421
    [405] => 401
    [409] => 416
    [410] => 401
    [414] => 402

    [420] => 421
    [421] => 422
    [422] => 420

Answer 4

[Vitsliputsli]

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

do {
    $path = [key($array), $link = current($array)];
    while (isset($array[$link2 = $link])) {
        $link = $array[$link2];
        unset($array[$link2]);
        $pathPos = array_search($link,$path); // более для понятности, для длинных колец эффективнее хранить только ключи и искать по ним
        if (false !== $pathPos) {
            var_export(array_slice($path,$pathPos));
            break;
        }
        $path[] = $link;
    }
} while (false!==next($array));