algorithm - 每对相邻数字之间的差值大于 1 的序列有多少个

Question

我刚发现这样一个问题

“给你N个不同的整数，你知道每对相邻数的差大于1的有多少个不同的数列吗？”

当整数为“1 2 3”时，答案为零，当整数为“5 3 1”时，答案为6，对于“1 3 5”“1 5 3”“3 1” 5""3 5 1""5 1 3""5 3 1"满足问题，我只是尝试了所有我能做的但我无法解决它，所以我的问题是，如何编写算法来解决它。

谢谢。

这是我的程序

int n;bool vi[30];int a[30];int b[30];int counter = 0;
void dfs(int k)
{
    if ( k == n)
    {
        for (int i = 2; i <= n; i ++)
            if (fabs(b[i] - b[i - 1]) <= 1) return ;
        counter ++;
        return ;
    }
    for (int i = 0; i < n; i ++)
    {
    if (!vi[i])
    {
        b[k + 1] = a[i];
        vi[i] = true;
        dfs(k + 1);
        vi[i] = false;
        }
    }
}
int main (void)
{
        cin >> n;
        for (int i = 0; i < n; i ++)
            cin >> a[i];
        memset(vi, 0, sizeof(vi));
        for (int i = 0; i < n; i ++)
        {
            vi[i] = true;b[1] = a[i];dfs(1);vi[i] = false;
        }
        cout << counter << endl;
    return 0;
}

Answer 1

“有多少种不同的序列……”这个问题的答案无需枚举每个组合即可解决。这是一件好事，因为 25! 大约是 1.55 x 10^24，或者比 任何 现有计算机在一秒钟内枚举的要多得多。或者在一年内。

这是一道数学题，尤其是组合数学。参见 http://en.wikipedia.org/wiki/Combinatorics可能还有 http://en.wikipedia.org/wiki/Combinations获取有关如何解决问题的信息。