C++中的组合

Question

比方说，您有一个字符串向量，用于在用户指定的位置存储X.例如，用户可以键入“X 3”，并且必须告诉他们是否可以在矢量的第3个位置插入X.这是问题出现的地方......告诉用户插入是否有效。

所以，基本上，向量有2个数字分配给它，每次用户运行程序时都会改变。所以，假设矢量大小为10，分配给它的数字是3,2。这意味着必须有3个X的运行，至少一个空间和一个2X的运行。因此，它可能是这个样子：

XXX _ _ _ _ XX _

在这种情况下，如果用户在上述任何位置，其中的X是进入了一个X，它将是一个有效的举措。但是，用户可能也做了这样的事情：

_ _ _ _ X X X _ X X

而这也将是有效的。

我的问题是：我该如何设置一个处理用户输入有效的所有可能组合的系统？

请记住，矢量大小可以是任意大小。这个问题实际上是皮克斯拼图的一部分，万一有帮助！

Answer 1

下面的函数生成段之间的空间排列，返回false时，它不能产生任何更多：

template <typename SpaceIter> 
bool next(SpaceIter start, SpaceIter finish) 
{ 
    for (SpaceIter i = start; i != finish; ++i) 
    { 
     // Find the first non-minimised space. 
     if (*i) 
     { 
      SpaceIter j = i; ++j; 
      if (j == finish) 
      return false; 

      int s = *i; // Remember *i, in case i == start. 

           // Preserve the invariant: Σ(space[i]) 
           //  i != start i == start 
           //  ---------- ----------- 
      // Minimise current. 
      *i = 0;    // Gain = -s  overwritten 
      // Increment the next. 
      ++*j;     // Gain =  1   1 
      // Adjust the first. 
      *start = s - 1;  // Gain = s - 1  -1 
           //  ----------------------- 
           // Nett =  0   0 
      return true; 
     } 
    } 
    return false; 
} 

注意，这个算法需要在包括两端的空间和工作在过剩空间 - 也就是说，如果长度为S的空间在任一端，则S表示为S，但如果S - 1在中间的某处，则空间S表示为S，因为内部空间必须长度为1或更大。清楚的是，在这种表示中，所有空格的最小值为零。您通过将第一个空格设置为N + 1来初始化spaces - Σ _{i = 0..N}（长度 _i + 1）并且其余N + 1个空格为0，其中N是序列的数量。

要完成故事，您需要测试给定的输入是否与给定的输入兼容，是否有给定的空格排列组合长度数组。

一个简单的方法是在开始时将输入转换为位集。然后将每个空间排列与长度数组一起转换为一个bitset并从输入bitset中减去。如果结果为空，则输入有效。

警告：我对上述算法进行了相当仔细的分析，但是我对代码做了很少的测试。下面是我写的一个相当难看的试车手，在情况下，它可以帮助你自己的测试：

template <typename T, int N> 
bool next(T (&spaces)[N]) 
{ 
    return next(spaces, spaces + N); 
} 

const char* x(int n) { return "XXXXXXXXXX" + 10 - n; } 
const char* s(int n) { return "----------" + 10 - n; } 

int main(int argc, const char* argv[]) 
{ 
    int spaces[] = { 4, 0, 0, 0 }; 
    do 
    { 
     // I reverse the spaces to make segments shuffle left-to-right. 
     // This is a purely aesthetic thing. The order of permutations 
     // doesn't matter. 
     std::cout << s(spaces[3]) << x(2) 
       << s(spaces[2] + 1) << x(1) 
       << s(spaces[1] + 1) << x(1) 
       << s(spaces[0]) 
       << "\n"; 
    } 
    while (next(spaces)); 
}