У меня проблема, когда мне нужно l oop над мультииндексом типа (a[1],a[2],a[3],...,a[n]), где a[i] находится в диапазоне от 0 до некоторого целого числа m[i]. В принципе, я мог бы, конечно, «просто» использовать n вложенные циклы for, однако я не могу знать n заранее, поэтому о вложенных циклах не может быть и речи.
Учитывая входы: n, m[1], m[2], ..., m[n].
То, что у меня уже есть: Простая «функция-преемник», которая позволяет мне перемещаться по индексу, как если бы я выполнял несколько вложенных циклов; т.е. сначала (0,0,0,...), (1,0,0,...), ..., (m[1],0,0,...), (0,1,0,...), (1,1,0,...), et c ...
Реализация MATLAB здесь:
function ii = incr(ii, M)
% multiindex incrementer; ii is a multi-index, M is the upper limits
for i = 1:numel(M)
ii(i) = ii(i) + 1;
if i > 1, ii(i-1) = 1; end
if ii(i) <= M(i), return, end
end
end
То, что я хотел бы иметь: Однако было бы наиболее выгодно, если бы я мог l oop по индексам в порядке увеличения «величины», т.е. (0,0,0,...), (1,0,0,...) , (0,1,0,...), ..., (2,0,0,...), (1,1,0,...), ...
Порядок между индексами одной и той же «величины» не имеет особого значения, более важно, что когда
Альтернатива: Альтернативным и также приемлемым решением может быть что-то, что вычисляет перестановку, принимающую первый порядок к любому порядку второй тип.
Изменить: мой плохой, учитывая, что это MATLAB, он, конечно, считает от 1, а не от 0, так что это то, что делает код. Но проблема остается той же самой по своему характеру.
Обновление (29/05): Итак, я разработал метод сейчас, но он, вероятно, не так эффективен, как мог бы (на все). Но вот оно. Приветствуются любые улучшения и упрощения.
function a = succ(a,m)
if all(a==m), return; end
n = numel(a);
i = find(a,1);
if i < n
j = i;
while a(i+1) +1 > m(i+1)
i = i+1;
if i >= n
i = n;
break;
end
end
if i == j && a(i) == 1
a(i) = a(i) -1;
a(i+1) = a(i+1) +1;
else
a(i) = sum(a(j:i));
a(j:i-1) = 0;
if i == n
a = succ_ext(a,m,i,1);
else
a = succ_ext(a,m,i,-1);
a(i+1) = a(i+1) +1;
end
end
else
a = succ_ext(a,m,n,1);
end
end
function a = succ_ext(a,m,i,c)
j = 1;
v = a(i) + c;
a(i) = 0;
while a(j) + v > m(j)
v = v + a(j)-m(j);
a(j) = m(j);
j = j+1;
end
a(j) = a(j) + v;
end
Обновление (02/06) [A]: Альтернативный грубый метод включает использование incr, как определено выше, для создания последовательности "вложенных стиль петель ". Затем суммируем компоненты каждого вычисленного мультииндекса, чтобы сформировать последовательность целых чисел. Затем отсортируйте этот список и используйте полученную перестановку индексов для перестановки исходной последовательности мультииндекса.
Обновление (02/06) [B]: Я понял, что по вычислительным причинам это Мне тоже потребовался порядок oop в incr во время вычислений, но более поздние представления все же выигрывают от переупорядочения. При любом желаемом обходе мультииндекса, скажем, характеризующемся функцией преемника succ, принимающей индекс и производящей следующий в последовательности обхода, как в моих реализациях выше, мы можем вычислить карту индекса перестановки следующим образом:
Идея состоит в том, чтобы учесть, что мы представляем целые числа в базе с разным основанием для каждого di git, в частности m[i]+1 будет основанием для i 'th di git.
Таким образом мы можем легко вычислить соответствующее целочисленное представление каждого мультииндекса в последовательности обхода. Целые числа будут упорядочены по вложенному обходу стиля l oop, поэтому сортировка последовательности по индексу перестановки (назовем его A) дает отображение от порядка обхода к вложенному l oop порядку. Если мы затем отсортируем индекс перестановки A для нового индекса перестановки B, то B обеспечит обратный порядок, переводящий нас от вложенного l oop порядка к порядку обхода.