如何加快将 n 元素集的所有分区打印成 k 无序集的速度

Question

如何加速我的程序？

我的任务：1<=k<=n<=10，时间 1 秒将 n 元素集的所有分区打印成 k 个无序集。分区可以任意顺序输出。在分区内，集可以按任何顺序显示。在集合中，数字必须按升序显示。遵循示例中的格式。

示例： example

我的解决方案：

#include <iostream>
#include <vector>
//#pragma GCC optimize ("O3")

using namespace std;
int n;

int num(vector<vector<int>> sets) {
  int res = 0;
  for (int i = 0; i < sets.size(); i++)
    for (int j = 0; j < sets[i].size(); j++)
      if (sets[i][j] != 0)
        res++;
  return res;
}

bool testSets(vector<vector<int>> sets) {
  for (int i = 0; i < sets.size(); i++) {
    if (sets[i].size() == 0) {
      return false;
    } else {
      for (int j = 0; j < sets[i].size() - 1; j++)
        if (sets[i][j] >= sets[i][j + 1])
          return false;
    }
  }
  if (num(sets) == n)
    return true;
  else
    return false;
}

void out(vector<vector<int>> a) {
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < a[i].size(); j++)
      cout << a[i][j] << " ";
    cout << endl;
  }
}

void func(vector<vector<int>> sets, vector<int> a, vector<bool> used) {
  if (num(sets) == n) {
    if (testSets(sets)) {
      out(sets);
      cout << endl;
    } else {
      return;
    }
  } else {
    int i, x;
    for (i = 0; i < used.size(); i++) {
      if (used[i] == false)
        break;
    }
    if (i == used.size())
      i--;

    for (x = 0; x < sets.size(); x++) {
      if (sets[x].size() == 0)
        break;
    }
    if (x == sets.size())
      x--;

    used[i] = true;
    for (int j = 0; j <= x; j++) {
      sets[j].push_back(a[i]);
      //out(sets);
      func(sets, a, used);
      sets[j].pop_back();
    }
    used[i] = false;
  }
}

int main() {
  int k;
  cin >> n >> k;
  vector<int> a(n);
  vector<vector<int>> sets;
  vector<bool> used(n, false);

  for (int i = 0; i < a.size(); i++)
    a[i] = i + 1;
  sets.resize(k);

  func(sets, a, used);

  return 0;
}```

Answer 1

谢谢大家

去掉了num函数，给func增加了sum变量，push时加1，pop时减1

如何加快将 n 元素集的所有分区打印成 k 无序集的速度

How to speed up my Print all partitions of an n-element set into k unordered sets

c++

performance

optimization

micro-optimization