algorithm - Skolem 序列生成器算法

Question

我的老师要我写一个函数，它获取一个整数值 N 并返回长度为 2n 的数组，并包含该值的一个 skolem 序列。

例如:function(4) 将返回 {4,2,3,2,4,3,1,1}

我不知道该怎么做。

Answer 1

数 n 的 Skolem 序列是一个大小为 2×n 的整数序列，它满足两个条件:

1. 对于每个非负数k <n，恰好存在两个元素s_i 和 s_j 在序列中使得 s _em>i = s_j = k

   <

2. 如果 s_i = s_j = k 和 i <j 然后 j−i = k

参见 http://mathworld.wolfram.com/SkolemSequence.html

基本上，这意味着您需要创建一个包含从 1 到 n 的数字的序列，其中每个数字出现两次。要将该序列转换为 skolem 序列，两个 1 必须彼此相邻，两个 2 之间必须有一个数字，3 之间必须有 2 个数字，依此类推。

这个算法比人们想象的要难得多。最简单的方法是检查序列的每个排列，并返回第一个有效的排列。这是 (2n)!复杂性，这是非常缓慢的。这是一个没有 n! 的算法的引用。复杂: http://www.cs.mun.ca/~dchurchill/pdf/honours.pdf

我用 C++ 编写了朴素算法。这将为任何给定的输入生成 Skolem 序列。这个算法非常慢，但我希望你能明白这一点:

#include<iostream>
#include<vector>
#include<algorithm>
void start(int num, std::vector<int>& v) { //creates the |2n| sequence
        for(int i = 1; i<=num; i++) {
                v.push_back(i);
                v.push_back(i);
        }
}
bool check(std::vector<int>& v) { //checks to see if sequence is a skolem sequence
        for(int i = 1; i<=v.size()/2; i++) {
                auto j = std::find(v.begin(), v.end(), i);
                auto k = std::find(j+1, v.end(), i);
                if(k-j != i) {
                        return false;
                }
        }
        return true;
}
void skolem(int num, std::vector<int>& v) { //permutes the vector to find skolem sequences
        start(num, v);
        while(std::next_permutation(v.begin(), v.end())){
                if(check(v))
                        break;
        }
}
int main()
{
        int num;
        std::cin>>num;
        std::vector<int> v;
        skolem(num, v);
        std::cout<<"found it"<<std::endl;
        print(v);
}

此算法仅适用于小数字(小于 10)。如果您需要处理更大的序列，我建议您查看上面的链接。