如何生成大小为n的所有矢量，其中每个元素可能包含m个不同值中的1个？

Question

对不起，如果这是重复的，但我没有找到任何符合我的答案。

请考虑我有一个包含3个值的向量。我想从这个向量构造另一个指定长度的向量。例如，假设长度为n=3，矢量包含以下值0 1 2。我期待的输出如下：

0 0 0 
0 0 1 
0 0 2 
0 1 0 
0 1 1 
0 1 2 
0 2 0 
0 2 1 
0 2 2 
1 0 0 
1 0 1 
1 0 2 
1 1 0 
1 1 1 
1 1 2 
1 2 0 
1 2 1 
1 2 2 
2 0 0 
2 0 1 
2 0 2 
2 1 0 
2 1 1 
2 1 2 
2 2 0 
2 2 1 
2 2 2 

我目前的实现只是构建了基于n环路，并产生预期的输出。我希望能够在输入向量中构造不同长度和不同值的输出向量。

我已经看过可能的实现使用next_permutation，但不幸的是传递一个长度值似乎并不奏效。

有没有时间和复杂性算法，可以用于这种情况？再次，我可能已经计算出了n=17以及6附近的矢量大小。

以下是我对n=3的实施。这里，enc是包含输入的向量。

vector<vector<int> > combo_3(vector<double>enc,int bw){ 
    vector<vector<int> > possibles; 
    for (unsigned int inner=0;inner<enc.size();inner++){ 
     for (unsigned int inner1=0;inner1<enc.size();inner1++){ 
      for (unsigned int inner2=0;inner2<enc.size();inner2++){ 
       cout<<inner<<" "<<inner1<<" "<<inner2<<endl; 
       unsigned int arr[]={inner,inner1,inner2}; 
       vector<int>current(arr,arr+sizeof(arr)/sizeof(arr[0])); 
       possibles.push_back(current); 
       current.clear(); 
    } 
    } 
} 
    return possibles; 
} 

Answer 1

你在做什么是简单的计数。把你的输出矢量看作一列数字（一个矢量的矢量）列表。每个数字可能有一个m不同的值，其中m是您输入矢量的大小。

这不是排列生成。生成每个置换意味着生成一个输入向量的每个可能的排序，这不是你想要的。

如果你认为这是一个计数问题，答案可能会变得更清晰。例如，你将如何生成5位数的所有基数为10的数字？在这种情况下，输入矢量的大小为10，并且输出列表中的每个矢量的长度为5.