'vectorize' 这个重复的 C++ 代码的方法？

Question

我看到了 this code in a HackerRank 挑战解决方案，我想知道是否有办法让它更高效 and/or 更美观。它正在计算一堆数字的所有排列，其中有 x 4's、y 5's 和 z 6's。因此，代码变得非常重复：

int cnt[101][101][101];

int solve1(int x,int y,int z){
    if(x <= 0 && y <= 0 && z <= 0)
        return 1 ;
    int &ret = cnt[x][y][z] ;
    if(ret != -1) return ret ;
    ret = 0 ;
    if(x)
        ret += solve1(x-1,y,z) ;
    if(ret >= mod) ret -= mod ; 
    if(y)
        ret += solve1(x,y-1,z) ;
    if(ret >= mod) ret -= mod ; 
    if(z)
        ret += solve1(x,y,z-1) ;
    if(ret >= mod) ret -= mod ; 
    return ret ;
}

STL 容器或算法是否提供了一种方法来降低这种重复性 and/or 的效率？

考虑并拒绝：将 vector 传递给 solve() 而不是许多整数，然后使用 accumulate 收集 ret 同时修改每个向量元素（x、y、z 作为向量元素）并在原始向量输入的修改副本上调用 solve。但这只是创建了一大堆 vectors 没有任何明确的平衡改进。另外，我还没有想出 accumulate 应用程序，所以大概那部分是 off/not 可能的方式。

感谢您的任何建议。

Answer 1

使用 c++11，您可以替换：

if(x)
    ret += solve1(x-1,y,z) ;
if(ret >= mod) ret -= mod ; 
if(y)
    ret += solve1(x,y-1,z) ;
if(ret >= mod) ret -= mod ; 
if(z)
    ret += solve1(x,y,z-1) ;
if(ret >= mod) ret -= mod ;

与：

auto func = [](int&ret, int x, int y, int z)
{
    ret += solve1(x, y, z);
    if (ret >= mod) ret -= mod;
    return ret;
};
if (x) func (ret, x-1, y, z);
if (y) func (ret, x, y-1, z);
if (z) func (ret, x, y, z-1);

你也可以只使用一个函数。

Answer 2

对x y z进行排序，记忆更有效：

int cnt[101][101][101]={0};
int solve1(std::array<int,3> idx){
  std::sort(idx.begin(),idx.end());
  int x=idx[0],y=idx[1],z=idx[2];

  if(x <= 0 && y <= 0 && z <= 0) return 1;
  int &ret = cnt[x][y][z];
  if(ret != -1) return ret;
  ret = 0;
  auto f=[&](int x,int y,int z){
    ret += solve1({{x-1,y,z}});
    if(ret >= mod) ret -= mod;
  };
  if(x)f(x-1,y,z);
  if(y)f(x,y-1,z);
  if(z)f(x,y,z-1);
  return ret;
}
int solve1(int x,int y,int z){
  return solve1({{x,y,z}});
}

'vectorize' 这个重复的 C++ 代码的方法？

Ways to 'vectorize' this repetitive C++ code?

c++

algorithm

stl

vector