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)); 
}