-1、+1 的所有组合的向量的向量

Question

对于任何给定的 n，我需要创建一个长度为 n std::vector<std::vector<int>> 的向量向量，其中包含所有可能的组合-1 和 +1。例如，对于 n=3 我需要

std::vector<std::vector<int>> v = {
  { 1,  1,  1},
  { 1,  1, -1},
  { 1, -1,  1},
  { 1, -1, -1},
  {-1,  1,  1},
  {-1,  1, -1},
  {-1, -1,  1},
  {-1, -1, -1}
};

有什么提示吗？

Answer 1

使用二进制表示并测试位值的简单解决方案。我使用了 std::bitset，尽管您也可以使用简单的 C 风格位操作。

#include <bitset>

int main(){
    int n=3;
    int to = pow(2,n);
    std::vector<std::vector<int>> result;
    for (int i=0; i < to; i++){
        std::bitset<32> b(i);
        std::vector<int> vec1;
        for (int j=0; j < n; j++){
            int value = b.test(j) ? 1 : -1;
            vec1.push_back(value);
        }
        result.push_back(vec1);
    }

    // Printing out result
    for (auto& vec : result){
        for (auto val : vec){
            cout << val;
        }
        cout << endl;
    }
}

Test Example

Answer 2

根据@sascha 的建议，这里有一个将 +-1 附加到给定列表集的方法。

#include <vector>
#include <iostream>

std::vector<std::vector<int>>
append_plus_minus(const std::vector<std::vector<int>> & in)
{
  auto out = in;
  out.insert(out.end(), in.begin(), in.end());
  for (std::size_t i=0; i < in.size(); i++) {
    out[i].push_back(+1);
    out[i+in.size()].push_back(-1);
  }
  return out;
}

int main() {
  const int n = 5;

  std::vector<std::vector<int>> b_combinations = {{}};
  for (std::size_t i=0; i < n; i++) {
    b_combinations = append_plus_minus(b_combinations);
  }

  for (std::size_t i=0; i < b_combinations.size(); i++) {
     for (std::size_t j=0; j < b_combinations[i].size(); j++) {
       std::cout << b_combinations[i][j] << " ";
     }
     std::cout << std::endl;
  }
  return 0;
}

Answer 3

对于较大的 (n) 值，您可能希望提高效率：

std::vector<std::vector<int>> v;
v.reserve(1 << n);

for (unsigned int i = 0; i < (1 << n); i++)
{
    std::vector<int> vi (n, 0);
    for (unsigned int j = 0; j < n; j++)
        vi[n - 1 - j] = (i & (1 << j)) ? (-1) : (+1);
    v.push_back(vi);
}

我相信有人可以想出一个模板元程序，可以在编译时为常量 (n).

构造 (v)

-1、+1 的所有组合的向量的向量

vector of vectors of all combinations of -1, +1

c++

vector

combinatorics