Есть ли способ перебрать n-мерный массив (где n переменная) без использования рекурсии?

Question

Есть ли способ перебора n-мерного массива (где n - переменная) без с использованием рекурсии?В настоящее время я использую C ++, но думаю, что подойдет ответ практически на любом языке.

EDIT : На самом деле мой настоящий вопрос немного другой: я на самом деле хочу перечислить индексы массива.Простой 2D-пример с массивом 2x2: 0,0;0,1;1,0;1,1.

Answer 1

void iterate(const std::vector<int> &dims)
{
    std::vector<int> idxs(dims.size());

    while (1)
    {
        // Print
        for (int i = 0; i < dims.size(); i++)
        {
            std::cout << idxs[i] << " ";
        }
        std::cout << "\n";

        // Update
        int j;
        for (j = 0; j < dims.size(); j++)
        {
            idxs[j]++;
            if (idxs[j] < dims[j]) break;
            idxs[j] = 0;
        }
        if (j == dims.size()) break;
    }
}

Answer 2

Да - просто помните, что любой многомерный массив в C ++ (или в большинстве языков) - это просто линейная область памяти.Язык просто помогает вам, автоматически умножая любые индексы внешнего измерения на размер / смещение этого измерения.

Таким образом, вы можете «вручную» обходить многомерный массив, выполняя ту же арифметику, что и язык при написанииarray[x][y][z] - но, конечно, вы можете сделать это для произвольного числа измерений.

Answer 3

да. если массив «плоский» в памяти, вы можете просто выполнить итерацию от array до array + n^n.
обратите внимание, что то же решение с рекурсией будет работать с циклом + стек. (любая рекурсия может быть переведена как цикл + стек).

РЕДАКТИРОВАТЬ : после того, как вы отредактировали свой вопрос: там ровно m ^ n (при условии, что каждое измерение имеет одинаковое количество элементов m), простое перечисление будет 0,1, ... , (т ^ п) -1. доступ через array + ENUM_NUMBER.

Answer 4

Я недавно написал этого универсального помощника для хэширования массива NxM T.

template <class T, size_t N, size_t M>
    size_t hash(const T (&aa)[N][M])
{
    size_t seed = 0;
    for (size_t i=0; i<N; i++)
        boost::hash_combine(seed, boost::hash_range(aa[i], aa[i]+M));
    return seed;
}

Вы можете использовать тот же самый гист, чтобы перебрать произвольные массивы

template <class T, size_t N, size_t M, class F>
    void for_each(const T (&aa)[N][M], F func)
{
    size_t seed = 0;
    for (size_t i=0; i<N; i++)
    for (size_t j=0; j<M; j++)
        func(aa[i][j]);
}

template <class T, size_t N, size_t M, size_t L, class F>
    void for_each(const T (&aaa)[N][M][L], F func)
{
    size_t seed = 0;
    for (size_t i=0; i<N; i++)
    for (size_t j=0; j<M; j++)
    for (size_t k=0; k<L; k++)
        func(aa[i][j][k]);
}

Используйте его вот так:

void display(float f) {   std::cout << f << std::endl; }
// ...
float fff[1][2][3];
for_each(fff, display);