在圆上没有相交弦

Question

在圆上没有相交弦

algorithmmathgeometrychord-diagram

3

我正在尝试实现这个任务。我们在圆上有2n个点。因此，我们可以在它们之间创建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函数。

有人有任何想法吗？

更新：我确实缓存中间结果，但我真正想要找到GenerateNextSeq()函数，它可以通过前一个序列生成下一个序列，从而生成所有这样的组合。

顺便说一下，这是我的代码。

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;
}

- Nikita

你的例子中是不是应该是 n=3？ - Sneftel

你说的更有效率是什么意思？像这样递归的方式确实很高效，因为它只在有可能的情况下才会打印和进入。 - vish4071

我的意思是，我们需要合并通过创建第一个和弦所产生的所有3个结果的区间。这就是为什么我们需要多次乘以它们的原因。在从先前的序列生成新序列时，请避免这种情况。 - Nikita

递归算法将会是这样，你从点(1)开始（指区间中的第一个点），只在结果区间中有偶数个点时才将它连接到任何一个点。然后继续执行直到达到可能的集合，并打印出来，然后继续执行。 - vish4071

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bezmax · Answer 1

使用动态规划。也就是说，缓存部分结果。

基本上，从1个弦开始，计算所有答案并将它们添加到缓存中。然后取2个弦，每当可以使用缓存时计算所有答案。以此类推。

递归方式的时间复杂度为O(n!)（至少是n!，我不擅长复杂度计算）。

这种方法对于每一步来说是n/2-1次操作，总共有n步，因此时间复杂度为O(n^2)，比递归方式好得多。但是，这种解决方案依赖于内存，因为它必须在缓存中保存所有组合。15个弦很容易使用1GB的内存（Java解决方案）。

示例解决方案： https://ideone.com/g81zP9

约在306毫秒内完成12个和弦的计算。给定1GB的RAM，约在8秒内计算15个和弦。

缓存以特定格式保存以优化性能：数组中保存的数字表示链接还要再往前走多少步。例如[1,0,3,1,0,0]表示：

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

你可以将它转换为任何你想要的格式，这是一个单独的步骤。