【胡扯向】数据生成器

Posted on | In |
Words count in article: 579 | Reading time ≈ 2

作为一名OIER，我们会时不时的需要生成几组比较大的数据来进行测试，但是这种东西手玩肯定是不可能实现的，所以就需要用到数据生成器了。

这种东西呢，大家都知道是基于rand函数随机生成的数据，由于笔者极其的蒟蒻，所以决定先从比较基础的数据结构讲起。

全排列

首先因为基础的大家都会，这里就不讲了，从全排列开始吧。

当然比较暴力的做法是多次rand，对每个数打标，如果rand到打了标的数就重做，直到生成全排列为止，但面对$10^6$甚至更大的数据的时候这样就基本不可能输出了。

所以我们根据抽牌的原理写出了以下这段程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define N 1000000+110
using namespace std;
int n,a[N];
int main()
{
    freopen("data.out","w",stdout);
    srand((unsigned)time(NULL));
    n=1+rand()%1000000;
    printf("%d\n",n);
    for(register int i=1;i<=n;i++)
        a[i]=i;
    for(register int i=1;i<=n;i++)
    {
        int x=1+rand()%(n-i+1);
        printf("%d ",a[x]);
        swap(a[x],a[n-i+1]);
    }
    return 0;
}

在上面这个程序中，我们每次在前(n-i+1)个数中抽一个出来，然后把它换到第(n-i+1)个位置上，这样就可以保证相对快速而且不重复。

树

对于树，而且是比较规矩的，画出来真正有树的形状的树，我们也可以用类似的思想生成。

在这里，我们把所有用过的点放在后i个位置，每次从未用过的点中随机取出一个点v，从用过的点中随机取出一个点u，就相当于生成了一条由u到v的边，然后将v点放入已使用点集。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define N 1000000+110
using namespace std;
int n,a[N];
int main()
{
    freopen("data.out","w",stdout);
    srand((unsigned)time(NULL));
    n=1+rand()%1000000;
    printf("%d\n",n);
    for(register int i=1;i<=n;i++)
        a[i]=i;
    swap(a[1],a[n]);
    for(register int i=1;i<n;i++)
    {
        int v=1+rand()%(n-i),u=n-i+1+rand()%i;
        printf("%d %d\n",a[u],a[v]);
        swap(a[v],a[n-i]);
    }
    return 0;
}

这样就可以得到一棵树了。

0%