用c ++生成组合

Question

我一直在搜索使用c ++生成组合的源代码.我找到了一些高级代码,但这仅适用于特定数量的预定义数据.任何人都可以给我一些提示,或者也许是一些想法来产生组合.例如,假设集合S = {1,2,3,....,n},我们选择r = 2.输入将是n和r.在这种情况下,程序将生成长度为2的数组,如5 2输出1 2,1 3等.我很难构建算法.我花了一个月的时间思考这个问题.

Answer 1

一种简单的方法std::next_permutation:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

或稍微变化,以更容易遵循的顺序输出结果:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

一点解释:

它的工作原理是创建一个"选择数组"(v),我们放置r选择器,然后我们创建这些选择器的所有排列,如果在当前排列中选择了它,则打印相应的集成员v.希望这可以帮助.

Answer 2

我基于Nathan Wodarz 教授算法的简单有效的解决方案：

// n choose r combination
#include <vector>
#include <iostream>
#include <algorithm>

struct c_unique {
  int current;
  c_unique() {current=0;}
  int operator()() {return ++current;}
} UniqueNumber;

void myfunction (int i) {
  std::cout << i << ' ';
}

int main()
{
    int n=5;
    int r=3;

    std::vector<int> myints(r);
    std::vector<int>::iterator first = myints.begin(), last = myints.end();

    std::generate(first, last, UniqueNumber);

    std::for_each(first, last, myfunction);
    std::cout << std::endl;

    while((*first) != n-r+1){
        std::vector<int>::iterator mt = last;

        while (*(--mt) == n-(last-mt)+1);
        (*mt)++;
        while (++mt != last) *mt = *(mt-1)+1;

        std::for_each(first, last, myfunction);
        std::cout << std::endl;
    }
}

然后输出是：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Answer 3

如果您注意到每个级别r选择1到n之间的数字,则可以实现它.

在C++中,我们需要"手动"保持产生结果(组合)之间的通话状态:所以,我们建立了一个类,建筑初始化状态,并具有在每次调用,同时也有解决方案返回组合成员: 例如

#include <iostream>
#include <iterator>
#include <vector>
#include <cstdlib>

using namespace std;

struct combinations
{
    typedef vector<int> combination_t;

    // initialize status
   combinations(int N, int R) :
       completed(N < 1 || R > N),
       generated(0),
       N(N), R(R)
   {
       for (int c = 1; c <= R; ++c)
           curr.push_back(c);
   }

   // true while there are more solutions
   bool completed;

   // count how many generated
   int generated;

   // get current and compute next combination
   combination_t next()
   {
       combination_t ret = curr;

       // find what to increment
       completed = true;
       for (int i = R - 1; i >= 0; --i)
           if (curr[i] < N - R + i + 1)
           {
               int j = curr[i] + 1;
               while (i <= R-1)
                   curr[i++] = j++;
               completed = false;
               ++generated;
               break;
           }

       return ret;
   }

private:

   int N, R;
   combination_t curr;
};

int main(int argc, char **argv)
{
    int N = argc >= 2 ? atoi(argv[1]) : 5;
    int R = argc >= 3 ? atoi(argv[2]) : 2;
    combinations cs(N, R);
    while (!cs.completed)
    {
        combinations::combination_t c = cs.next();
        copy(c.begin(), c.end(), ostream_iterator<int>(cout, ","));
        cout << endl;
    }
    return cs.generated;
}

测试输出:

1,2,
1,3,
1,4,
1,5,
2,3,
2,4,
2,5,
3,4,
3,5,
4,5,

Answer 4

          #include<iostream>
          using namespace std;

          for(int i=1;i<=5;i++)
             for (int j=2;j<=5;j++) 
                if (i!=j)
                  cout<<i<<","<<j<<","<<endl;

           //or instead of cout... you can put them in a matrix n x 2 and use the solution