c++ - 尝试开发一种排列算法

Question

我想开发下面的put搞不定。 我有一个长度为 N 的 vector 。每个元素可以变成0到K。这里的N和K由用户给定。现在我正在尝试创建一个函数，我可以在其中遍历所有可能的解决方案。

假设 N 为 4 且 K = 2，那么我想遍历所有可能的排列(？)。

我想用 0000 填充一个 vector ，测试它然后用 1000 填充 vector ，测试它然后 0100 等等。

重要的是要知道 0100 和 0010 是不同的。与 1100 和 0011 等一样。

需要特别注意的是，这是循环应该打印的内容(只要出现所有不同的可能序列，0001 或 1000 在 0000 等之后真的无关紧要)。

0000、1000、0100、0010、0001、1100、1010、1001、1110、1101、0111、0101、......、2012、2211 等。

我尝试了 for 循环的组合，但无法真正理解。 该应用程序是在 C++ 中

请帮忙，谢谢

Answer 1

我不认为排列是您要找的词。你说的是计数，所以你想做的基本上是增加 vector ，就像你在一年级做加法一样

First value   0 0 0 0
Add 1               1
              =======
Second Value  0 0 0 1
Add 1               1
              =======
Third Value   0 0 1 0

所以你会做这样的事情:

// returns false when you've seen all of the possible values for this vector
bool increment(std::vector<int> & vector, int k) {
  for (int i = 0; i < vector.size(); ++i) {
    int j = vector[i] + 1;
    if (j <= k) {
      vector[i] = j;
      return true; 
    }
    else vector[i] = 0;
    // and carry a 1 by looping back again
  }
  return false;
}

这将按以下顺序返回值，对于 k=1，假设您从 vector 0000 开始:1000、0100、1100、0010、1010、0110、1110、0001、1001， 0101、1101、0011、1011、0111、1111。 (图片以二进制计数——我只是将每个数字颠倒过来以符合我们通常认为的从左到右的 vector View 。)