Алгоритм посещения всех точек в матрице из N (неизвестных) измерений - PullRequest
Новая
       34

Алгоритм посещения всех точек в матрице из N (неизвестных) измерений

1 голос
/ 24 августа 2010

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

Некоторая информация о коде: Матрица имеет такие методы доступа, как значения (хотя они не очень актуальны). 

object value = matrixInstance.GetValue(int[] point);   
matrixInstance.SetValue(object value, int[] point);

Примечание: Аргумент точка является массивом индексов и должен соответствовать # измерениям, иначе генерируется исключение.

Информация о структуре матрицы может быть получена: 

int numDims = matrixInstance.Rank; //# dimensions
int sizeDim = matrix.getRankSize(int index); // length of specified dimension

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

Например, в 2D матрице 2x3 будут посещены следующие шесть точек:
[0,0] [0,1] [0,2] [1,0] [1,1][1,2]

Алгоритм должен работать до N измерений: 2,3,4 и т. Д.Для эффективности я буду использовать C # итератор для возврата очков.

Ответы [ 4 ]

4 голосов
/ 24 августа 2010

Вы можете просмотреть свою матрицу в виде дерева, у которого все листья имеют значения:

Illustration

- это матрица 

[0,0] = 'A'
[0,1] = 'B'
[1,0] = 'C'
[1,1] = 'D'

Просто применитеЛюбое известное решение для обхода дерева.

Вот рекурсивное решение (не проверено): 

IEnumerable<Point> GetPoints(Matrix matrix, int[] indexes)
{
    if (indexes.Length == matrix.Rank)
    {
        yield return matrix.GetValue(indexes);
    }
    else
    {
        for (int i = 0; i < matrix.GetRankSize(indexes.Length); i++)
        {
            foreach (var point in
                GetPoints(matrix, indexes.Concat(new int[] { i }).ToArray())
            {
                yield return point;
            }
        }
    }
}

Преобразовать это в итерационную версию, использующуюявный стек.

1 голос
/ 25 августа 2010

Просто рекурсивно итерируйте по каждому измерению. Например, первый вызов выполняет итерацию по каждому значению для первого измерения, вызывая себя для итерации по каждому значению для второго измерения и т. Д. Для любого количества измерений. Затем базовый случай (когда больше нет измерений) должен возвращать значение в соответствующей ячейке, а не повторять снова.

1 голос
/ 25 августа 2010

Если вы можете сгенерировать коллекцию значений индекса для каждого измерения во время выполнения, тогда вы можете использовать Фрагмент LINQ Эрика Липперта для генерации всех комбинаций значений индекса.

Метод Эрикасоздать коллекцию всех комбинаций: 

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
  return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) =>  
      from accseq in accumulator  
      from item in sequence  
      select accseq.Concat(new[] {item}));                
}

Итак, для вашего примера 2x3, 

int [ , ] dimensions= { { 0, 1}, { 0, 1, 2 } } ;
var allMatrixCells = CartesianProduct<int>(dimensions);

foreach(var cellLocation in allMatrixCells )
{
 ...
}
0 голосов
/ 25 августа 2010

Вы можете использовать смешанное радикальное представление, см., Например, http://en.wikipedia.org/wiki/Mixed_radix

Например, если у вас было 4 измерения с длинами 4,3,2,7, скажем, в соответствии с индексами a, b, c, d у нас есть число a + 4 * (b + 3 * (c + 2 *) г)). Чтобы восстановить индексы из число n аналогично получению десятичных цифр, за исключением того, что база меняется, т.е. а = п% 4; п / = 4; b = n% 3; п / = 3; с = n% 2; п / = 2; d = n.

Таким образом, у вас будет один цикл for (в данном случае для n = 0..4 * 3 * 2 * 7-1), в котором индексы могут восстановитесь как описано выше.

Однако, возможно, все эти подразделения и модули означают, что это не так эффективно.

...