生成一個有序的選擇重複的指定長度的條目

Question

我正在寫一個函數種類模仿unordered_tuple從sage combinatorial functions python中可用。

不同之處在於，我使用的輸入集總是[10,9,8,7,6]，並且只有輸入項數量變化（不大於10）。

所以，期望的輸出爲輸入= 3和用於輸入= 4，

unordered_tuples([10,9,8,7,6], 3) 
[[6, 6, 6], 
[6, 6, 7], 
[6, 6, 8], 
[6, 6, 9], 
[6, 6, 10], 
[6, 7, 7], 
[6, 7, 8], 
[6, 7, 9], 
[6, 7, 10], 
[6, 8, 8], 
[6, 8, 9], 
[6, 8, 10], 
[6, 9, 9], 
[6, 9, 10], 
[6, 10, 10], 
[7, 7, 7], 
[7, 7, 8], 
[7, 7, 9], 
[7, 7, 10], 
[7, 8, 8], 
[7, 8, 9], 
[7, 8, 10], 
[7, 9, 9], 
[7, 9, 10], 
[7, 10, 10], 
[8, 8, 8], 
[8, 8, 9], 
[8, 8, 10], 
[8, 9, 9], 
[8, 9, 10], 
[8, 10, 10], 
[9, 9, 9], 
[9, 9, 10], 
[9, 10, 10], 
[10, 10, 10]] 

unordered_tuples([10,9,8,7,6], 4) 
[[6, 6, 6, 6], 
[6, 6, 6, 7], 
[6, 6, 6, 8], 
[6, 6, 6, 9], 
[6, 6, 6, 10], 
[6, 6, 7, 7], 
[6, 6, 7, 8], 
[6, 6, 7, 9], 
[6, 6, 7, 10], 
[6, 6, 8, 8], 
[6, 6, 8, 9], 
[6, 6, 8, 10], 
[6, 6, 9, 9], 
[6, 6, 9, 10], 
[6, 6, 10, 10], 
[6, 7, 7, 7], 
[6, 7, 7, 8], 
[6, 7, 7, 9], 
[6, 7, 7, 10], 
[6, 7, 8, 8], 
[6, 7, 8, 9], 
[6, 7, 8, 10], 
[6, 7, 9, 9], 
[6, 7, 9, 10], 
[6, 7, 10, 10], 
[6, 8, 8, 8], 
[6, 8, 8, 9], 
[6, 8, 8, 10], 
[6, 8, 9, 9], 
[6, 8, 9, 10], 
[6, 8, 10, 10], 
[6, 9, 9, 9], 
[6, 9, 9, 10], 
[6, 9, 10, 10], 
[6, 10, 10, 10], 
[7, 7, 7, 7], 
[7, 7, 7, 8], 
[7, 7, 7, 9], 
[7, 7, 7, 10], 
[7, 7, 8, 8], 
[7, 7, 8, 9], 
[7, 7, 8, 10], 
[7, 7, 9, 9], 
[7, 7, 9, 10], 
[7, 7, 10, 10], 
[7, 8, 8, 8], 
[7, 8, 8, 9], 
[7, 8, 8, 10], 
[7, 8, 9, 9], 
[7, 8, 9, 10], 
[7, 8, 10, 10], 
[7, 9, 9, 9], 
[7, 9, 9, 10], 
[7, 9, 10, 10], 
[7, 10, 10, 10], 
[8, 8, 8, 8], 
[8, 8, 8, 9], 
[8, 8, 8, 10], 
[8, 8, 9, 9], 
[8, 8, 9, 10], 
[8, 8, 10, 10], 
[8, 9, 9, 9], 
[8, 9, 9, 10], 
[8, 9, 10, 10], 
[8, 10, 10, 10], 
[9, 9, 9, 9], 
[9, 9, 9, 10], 
[9, 9, 10, 10], 
[9, 10, 10, 10], 
[10, 10, 10, 10]] 

和C++函數我寫如下。

我其實不是一個有經驗的程序員，我只是試圖想出正確的解決方案，但它工作正常，但它提供了許多重複的解決方案。

老實說，我寫了這個函數，但我甚至不知道自己寫了什麼。

我可以使用set，但它會是非常低效的，我想知道這個問題的正確解決方案。

任何人都可以修復它，以便它提供上面的輸出？

#include<iostream> 
    #include<string> 
    #include<cstdlib> 
    #include<vector> 

    using namespace std; 

    vector<vector<int> > ut(int); 

    int main(int argc, char** argv) { 
     int entry = atoi(argv[1]); 
     ut(entry); 
     return 1; 
    } 

    vector<vector<int> > ut(int entry) { 
     vector<vector<int> > ret; 

     int upper = 10; 
     vector<int> v(entry, upper); 
     ret.push_back(v); 

     typedef vector<int>::iterator iter_t; 

     iter_t it = v.begin(); 
     int count=0; 
     int c = 0; 
     while(v.back() != 6) { 
      v = ret[count+c]; 
      while(it != v.end()) { 
       --(*it); 
       ++it; 
       ret.push_back(v); 
       ++c; 
      } 
      it = v.begin(); 
      c=0; 
      ++count; 
     } 


     for(int i=0; i<ret.size(); ++i) { 
      vector<int> tuple = ret[i]; 
      for(int j=0; j<tuple.size(); ++j) { 
       cout << tuple[j] << ' '; 
      } 
      cout<<endl; 
     } 
     cout << endl; 
     return ret; 
    } 

Answer 1

看吧！

vector<vector<int> > ret; 

int upper = 10; 
vector<int> v(entry, upper); 
ret.push_back(v); 

typedef vector<int>::iterator iter_t; 

iter_t it = v.begin(); 
int count=0; 
int c = 0; 
while(v.back() != 6) { 
    v = ret[count+c]; 
    while(it != v.end()) { 
    --(*it); 
    ++it; 
    ret.push_back(v); 
    ++c; 
    } 
    it = v.begin(); 
    c=0; 
    ++count; 
} 

這只是可怕。 （我明白你是初學者，請理解我的批評意圖是爲了幫助。）通常這種類型如果密集的複雜性是不必要的，並且可以作爲bug的隱藏地。請注意，c和it設置爲之前的循環和在循環的末尾，並且從未再次使用;我們可以在循環的開始設置它們，代碼會更短，更清晰：

int count=0; 
while(v.back() != 6) { 
    iter_t it = v.begin(); 
    int c = 0; 
    v = ret[count+c]; 
    while(it != v.end()) { 
    --(*it); 
    ++it; 
    ret.push_back(v); 
    ++c; 
    } 
    ++count; 
} 

現在我們可以看到，c是從來沒有使用過，除了當它是零。 （如果你不相信我，請看原始代碼。）但更糟糕的是it指向v，然後v被分配一個新的值。因此it可能指向死鎖內存，並且解除引用會導致未定義的行爲。目前還不清楚這個代碼是如何工作的。

試試這個：

vector<int> v(n,6); 

vector<int>::iterator itr1; 
do{ 
    ret.push_back(v); 

    itr1 = v.begin(); 

    while(++(*itr1)>10){ 
     if(++itr1==v.end()) 
     break; 
    } 
    for(vector<int>::iterator itr2 = v.begin(); itr2!=itr1; ++itr2) 
    *itr2 = *itr1; 
} 
while(itr1!=v.end()); 

Answer 2

一個很好的地方開始置換問題是遞歸。採用這種方法，要構建長度爲3的所有輸出，您需要從集合[6, 7, 8, 9, 10]中選擇一個數字，然後將長度爲2的所有輸出附加到該數字，並將輸入集限制爲從所選數字開始。所以，如果，例如你選擇了7，你爲第一次遞歸調用設置的輸入將是[ 7, 8, 9, 10]。即，在此情況下，遞歸調用將來自輸入[ 7, 8, 9, 10]

實現這種想法是下面的程序來附加到[ 7 ]長度2的所有輸出。我有興趣看看是否有人可以想出一個非遞歸解決方案。

#include "stdafx.h" 
#include <iostream> 
#include <vector> 

typedef std::vector<int> intvec; 
typedef std::vector<intvec> intvecs; 

void GenerateUnOrderedIntVecs(
    const int* remainingInput, int remainingInputLen, 
    const intvec& outputSoFar, int remainingOutputLen, 
    intvecs& output) 
{ 
    if (remainingOutputLen == 0) { // base case of recursion 
     output.push_back(outputSoFar); 
     return; 
    } 

    // For all digits in our input 
    for(int i=0; i<remainingInputLen; ++i) { 
     // Add the ith digit to our output so far 
     intvec outputSoFar2(outputSoFar); 
     outputSoFar2.push_back(remainingInput[i]); 
     // The recursion 
     GenerateUnOrderedIntVecs(
      remainingInput + i, // input set constrained to start from chosen digit 
      remainingInputLen - i, // input set is shorter 
      outputSoFar2,   // one digit longer than the parameter outputSoFar 
      remainingOutputLen -1, // so we need one digit less as we recurse 
      output); 
    } 
} 

int main(int argc, _TCHAR* argv[]) 
{ 
    const int nToChooseFrom = 5; 
    const int nToChooose = 3; 
    const int input[nToChooseFrom] = { 6, 7, 8, 9, 10 }; // provide input in sorted order (or sort it!) 

    intvecs output; 
    GenerateUnOrderedIntVecs(
     input, nToChooseFrom, 
     intvec(), nToChooose, 
     output); 

    for(intvecs::const_iterator i=output.begin(); i!=output.end(); ++i) { 
     std::cout << "[ "; 
     const intvec& unordered_tuple = *i; 
     for(intvec::const_iterator j = unordered_tuple.begin(); j!=unordered_tuple.end(); ++j) { 
      std::cout << *j << " "; 
     } 
     std::cout << "]\n"; 
    } 

    return 0; 
} 

它似乎適用於你的兩個例子（但我只是徹底檢查了第一個）。如果你不能看到它是如何工作通過閱讀代碼，一個好的辦法是在調試器中運行（這是我必須做的就是它的工作:)