algorithm - 圆上不相交

我正在努力执行这项任务。圆上有2*n个点。所以我们可以在它们之间创建n个和弦。打印所有方法以绘制N个不相交的和弦。
例如：如果n=6我们可以画（1->2 3->4 5->6），（1->4，2->3，5->6），（1->6，2->3，4->5），（1->6，2->5，3->4）
我开发了一个递归算法，从1->2，4，6创建一个和弦，并为剩余的2个间隔生成答案但我知道有更有效的非递归方法可能是通过实现nextseq函数。
有人有什么想法吗？
upd：我确实缓存了中间结果，但我真正想要的是找到generatenextseq（）函数，它可以通过previous生成下一个序列，从而生成所有这样的组合
顺便说一下，这是我的代码

struct SimpleHash {
    size_t operator()(const std::pair<int, int>& p) const {
        return p.first ^ p.second;
    }
};

struct Chord {
    int p1, p2;
    Chord(int x, int y) : p1(x), p2(y) {};
};

void MergeResults(const vector<vector<Chord>>& res1, const vector<vector<Chord>>& res2, vector<vector<Chord>>& res) {
    res.clear();
    if (res2.empty()) {
        res = res1;
        return;
    }


    for (int i = 0; i < res1.size(); i++) {
        for (int k = 0; k < res2.size(); k++) {
            vector<Chord> cur;

            for (int j = 0; j < res1[i].size(); j++) {
                cur.push_back(res1[i][j]);
            }

            for (int j = 0; j < res2[k].size(); j++) {
                cur.push_back(res2[k][j]);
            }
            res.emplace_back(cur);

        }

    }
}

int rec = 0;
int cached = 0;

void allChordsH(vector<vector<Chord>>& res, int st, int end, unordered_map<pair<int, int>, vector<vector<Chord>>, SimpleHash>& cach) {
    if (st >= end)
        return;

    rec++;

    if (cach.count( {st, end} )) {
        cached++;
        res = cach[{st, end}];
        return;
    }

    vector<vector<Chord>> res1, res2, res3, curRes;
    for (int i = st+1; i <=end; i += 2) {
        res1 = {{Chord(st, i)}};
        allChordsH(res2, st+1, i-1, cach);
        allChordsH(res3, i+1, end, cach);


        MergeResults(res1, res2, curRes);
        MergeResults(curRes, res3, res1);

        for (auto i = 0; i < res1.size(); i++) {
            res.push_back(res1[i]);
        }

        cach[{st, end}] = res1;

        res1.clear(); res2.clear(); res3.clear(); curRes.clear();
    }
}

void allChords(vector<vector<Chord>>& res, int n) {
    res.clear();

    unordered_map<pair<int, int>, vector<vector<Chord>>, SimpleHash> cach; // intrval => result

    allChordsH(res, 1, n, cach);
    return;
}

最佳答案

使用动态编程。也就是说，缓存部分结果。
基本上，从1和弦开始，计算所有答案并将它们添加到缓存中。
然后取两个和弦，尽可能使用缓存计算所有答案。
等。
递归方式是o（n！）（至少N！我对复杂度计算不好。
这种方法是对每个步骤和n个步骤执行n/2-1操作，因此o（n^2）更好。然而，这个解决方案依赖于内存，因为它必须在缓存中保存所有的组合。15和弦轻松使用1GB内存（Java解决方案）。
示例解决方案：
https://ideone.com/g81zP9
在~306ms内完成12和弦计算。
给定1GB内存，它在大约8秒内计算出15个和弦。
缓存以特定格式保存以优化性能：数组中保存的数字表示链接的距离。例如[1,0,3,1,0,0]表示：

1  0  3  1  0  0
|--|  |  |--|  |
      |--------|

您可以在单独的步骤中将其转换为所需的任何格式。