c++ - 嵌套循环 : permuting an n-dimensional array represented by a vector

Question

我有一个 n 维数组 T，其中每个维度的长度都相同 L。该数组由一维 vector v 表示(可以看作是 T 的“ reshape ”版本，因此 v 的长度为L^n).

以下示例显示了如何根据 T 的索引(其中 n = 3 和 L = 4)对 v 进行索引):

(例如 T(0,3,2) = v[14])

我想做的是创建一个 vector u 表示 n 维数组 S 其中 S 是通过将 T 置换/旋转 1 获得的，即

T(i1,i2,...,in) = S(i2,i3,...,in,i1) 对于任何 (i1,i2,... ,在)。

(当T为矩阵时，S对应T的转置)。

更新:

下面的代码或许能更好地解释我的问题:

void permute(vector<double> &output, const vector<double> &v, int L)
{
    int n = log(v.size())/log(L);

    // Suppose that we have a function doing this
    narray T = get_narray_from_vector(v, L);

    // Get the permutation of T
    narray S(T.size());
    for(int i1 = 0; i1 < L; i1++){
        for(int i2 = 0; i2 < L; i2++){
            ...
            for(int in = 0; in < L; in++){
                S(i2,i3,...,in,i1) = T(i1,i2,...,in);
            }
        }
    }

    // get vector from narray
    output.resize(v.size());
    int idx = 0;   
    for(int i1 = 0; i1 < L; i1++){
        for(int i2 = 0; i2 < L; i2++){
            ...
            for(int in = 0; in < L; in++){
                output[idx] = S(i1,i2,...,in);
                idx++;
            }
        }
    }   
}

然而，在实践中，我认为直接使用 vector 要好得多。因此，我会做这样的事情:

void permute(vector<double> &output, const vector<double> &v, int L)
{
    int n = log(v.size())/log(L);
    output.resize(v.size());

    // Get the permutation
    for(int i1 = 0; i1 < L; i1++){
        for(int i2 = 0; i2 < L; i2++){
            ...
            for(int in = 0; in < L; in++){
                output[i2*pow(L, n-1) + i3*pow(L, n-2) + ... + in*L + i1] = v[i1*pow(L, n-1) + i2*pow(L, n-2) + ... + i_{n-1}*L + in];
            }
        }
    } 
}

这里的难点在于嵌套循环，因为n是一个参数。

任何想法如何做到这一点？ 预先感谢您的帮助!!

Answer 1

这是一个不需要 n 的解决方案嵌套 for 循环。

首先，我有一些将数字分解为 L 的旧代码基于数字系统。

std::vector<int>
num2base(const int value,
         const unsigned int base){

  // Represents an input int VALUE in a new BASE-based number system                                                                                                    
  // n = a0*b^0 + a1*b^1 + ...                                                                                                                                          

  std::vector<int> base_representation;
  unsigned int num_digs = (unsigned int) (floor(log(value)/log(base))+1);
  base_representation.resize(num_digs);

  for (unsigned int i_dig = 0; i_dig < num_digs; i_dig++){
    base_representation[i_dig] =
      ((value % (int) pow(base,i_dig+1)) - (value % (int) pow(base, i_dig))) /
      (int) pow(base, i_dig);
  }

  return base_representation;
}

换句话说，这是一种转换单值索引idx的方法给你的i1至 in n -元组索引。

idx = i1*L^0 + i2*L^1 + ... in*L^(n-1)

这是反方向的代码

int
base2num(const std::vector<int> base_representation,
         const unsigned int base){

  unsigned int digit_val = 1;

  int value = 0;

  for (unsigned int digit = 0; digit < base_representation.size(); digit++){
    value += base_representation[digit]*digit_val;
    digit_val *= base;
  }

  return value;
}

一旦你有了 std::vector<int>代表你的n - 元组索引，很容易置换它。

void
permute_once(std::vector<int> &base_representation){

  std::vector<int>::iterator pbr = base_representation.begin();
  int tmp = *pbr;
  base_representation.erase(pbr);
  base_representation.push_back(tmp);

  return;
}

因此，要生成新的 n维数组 S

1. 遍历每个索引 idxS的 S .

2. 转换 idxS到 n -元组 ( iS1 , iS2 , ..., iSn )

3. 在 T 中找到相关条目及其 n -元组 ( iT1 , iT2 , ..., iTn )

4. 将其转换为单个索引 idxT .

5. u[idxS] = v[idxT];