Переменная в рекурсивной функции сохраняет ее значение

Question

Переменная в рекурсивной функции сохраняет ее значение

Я пытаюсь преобразовать этот код php в код C #.

Допустим, у нас есть некоторая матрица чисел

1 2 3
4 5 6
7 8 9

Этот php-код определяет, сколько комбинаций может быть, если мы можем только за один шаг в любых направлениях, не повторяя себя.
Из числа 1 это может быть например:

1,2
1,2,3
1,2,3,5
1,2,3,6
1,2,3,5,9

… и так далее.

Этот php-код работает нормально, но когда я делаю то же самое в C #, результат получается другим, и в конце я получаю сообщение об ошибке.

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

Как я могу решить эту проблему? Я знаю, что есть что-то с проблемой статических переменных, но не могу узнать.

<?php
$paths = array();

function find_path($graph, $start, $end, $path = array())
{
global $paths;
$path[] = $start;

if ($start == $end)
return $path;

if (!isset($graph[$start]))
return false;

foreach($graph[$start] as $node) {
if (!in_array($node, $path)) {
$newpath = find_path($graph, $node, $end, $path);
if ($newpath)
$paths[] = implode(',', $newpath);
}
}
return array();
}
$graph = array(
'1' => array('2', '4', '5'),
'2' => array('1', '3', '5', '4', '6'),
'3' => array('2', '5', '6'),
'4' => array('1', '2', '7', '8', '5'),
'5' => array('1', '2', '3', '4', '6', '7', '8'),
'6' => array('3', '2', '5', '9', '8'),
'7' => array('4', '5', '8'),
'8' => array('4', '6', '6', '7', '9'),
'9' => array('5', '6', '8')
);
for($i = 1; $i <= 9; $i++)
for($j = 1; $j <= 9; $j++)
find_path($graph, (string) $i, (string) $j);

using System;
using System.Collections.Generic;namespace ConsoleSlovoMania
{
class Program
{
public static List<string> newpath = new List<string>();

static void Main()
{
int[][] graph = new int[10][];

graph[1] = new int[] { 2, 4, 5 };
graph[2] = new int[] { 1, 3, 5, 4, 6 };
graph[3] = new int[] { 2, 5, 6 };
graph[4] = new int[] { 1, 2, 7, 8, 5 };
graph[5] = new int[] { 1, 2, 3, 4, 6, 7, 8 };
graph[6] = new int[] { 3, 2, 5, 9, 8 };
graph[7] = new int[] { 4, 5, 8};
graph[8] = new int[] { 4, 6, 6, 7, 9};
graph[9] = new int[] { 5, 6, 8 };

for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
find_path(graph, i, j);
}
}

Console.ReadKey();
}

private static List<string> find_path(int[][] graph, int start, int end, List<string> path = null)
{

Console.Write("start = " + start + " | end = " + end);
Console.WriteLine();
if (path == null)
{
path = new List<string>();
}
path.Add(start.ToString());
path.ForEach(Console.Write);
Console.WriteLine();

if (start == end)
{
return path;
}

foreach (int node in graph[start])
{
if (path.Exists(element => element == node.ToString()) == false)
{
newpath.AddRange(find_path(graph, node, end, path));
if (newpath.Count > 0)
{
//newpath.ForEach(Console.WriteLine);
newpath.Clear();
}
}
}
return path = null;
}
}
}

0

c#php recursion static static-variables

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это должно исправить исключение:

newpath.AddRange() выдает исключение, когда find_path() возвращает ноль.

Назначить результат find_path() в переменную и проверьте на нулевое значение перед добавлением в newpath

Чтобы исправить логическую ошибку, помните, что в .NET List<String> это объект, и когда вы передаете path на рекурсивном шаге вы передаете значение ссылки на этот объект, а не копию объекта. Простое исправление: просто скопируйте список (легко с LINQ), вот так:

path.ToList()

Вот полный исправленный код C #. Я переставил его и переименовал пару переменных, чтобы сделать транслитерацию PHP более 1: 1; это облегчило поиск и исправление List<String> path проблема мутации.

namespace ConsoleSlovoMania
{
class Program
{
public static List<string> paths = new List<string>();
private static List<string> find_path(int[][] graph, int start, int end, List<string> path = null)
{
if (path == null)
{
path = new List<string>();
}
path.Add(start.ToString());
if (start == end)
{
return path;
}
foreach (int node in graph[start])
{
if (!path.Contains(node.ToString()))
{
// before calling recursive step, copy path instead of passing around object reference value
List<String> newPath = find_path(graph, node, end, path.ToList());
if (newPath != null)
{
paths.Add(String.Join(",", newPath.ToArray()));
}
}
}
return path = null;
}
static void Main()
{
int[][] graph = new int[10][];
graph[1] = new int[] { 2, 4, 5 };
graph[2] = new int[] { 1, 3, 5, 4, 6 };
graph[3] = new int[] { 2, 5, 6 };
graph[4] = new int[] { 1, 2, 7, 8, 5 };
graph[5] = new int[] { 1, 2, 3, 4, 6, 7, 8 };
graph[6] = new int[] { 3, 2, 5, 9, 8 };
graph[7] = new int[] { 4, 5, 8};
graph[8] = new int[] { 4, 6, 6, 7, 9};
graph[9] = new int[] { 5, 6, 8 };

for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
find_path(graph, i, j);
}
}
Console.ReadKey();
}
}
}

Чтобы проверить результаты, вы можете поставить точку останова на строку с Console.ReadyKey() и убедитесь, что содержимое paths эквивалентно результату, возвращаемому кодом PHP. Для PHP вы можете использовать отладчик, или print_r($paths) выплюнуть массив. Я автоматизировал эту проверку путем сериализации paths а также $paths в JSON, который было очень легко проверить в jsFiddle, смотрите здесь: http://jsfiddle.net/ea89L8x8/

1