Блог

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

 s(i) = (i / w)   (i % w) * h;
 

где h и w -номера строк и столбцов матрицы (я хочу использовать ее для транспонирования матрицы на месте). Однако единственный известный мне алгоритм декомпозиции использует дополнительную память O(h * w), как это:

 std::vector<size_t> cycles;
std::vector<bool> visited(h * w, false);
for (size_t i = 0; i < h * w;   i) {
  if (!visited[i]) {
    visited[i] = true;
    cycles.push_back(i);
    // I don't need complete cycles, one member from each cycle is enough.
    for (size_t j = (i / w)   (i % w) * h; j != i;
         j = (j / w)   (j % w) * h) {
      visited[j] = true;
    }
  }
}
 

Поэтому мой вопрос в том, существует ли алгоритм, который может привести к одному и тому же cycles вектору, но для этого не потребуется такой вектор, как visited ?