【状态压缩搜索】函数依赖

【问题描述】
设 R(U)是一个属性集U 上的关系模式，X 和Y 是U 的子集。若对于R(U)的任意一个可能的关系r，r 中不可能存在两个元组在X 上的属性值相等，而在Y 上的属性值不等， 则称 “X 函数确定Y” 或 “Y 函数依赖于X”，记作X
→Y。其中X 称为这个函数依赖的决定属性集(Determinant)。
解释：如果有函数依赖XY，当我们知道X 的时候，也就知道了Y，也就是X 能推出Y。另外，可以简单的证明，如果XY，YZ，那么可以得到XZ。
若关系中的某一属性组的值能唯一的表示一个元组，则称该属性组为超码。
若关系中的某一属性组的值能唯一地表示一个元组，而其真子集不行，则称该属性组为候选码。
解释：设有属性集合(A,B,C)和函数依赖AB 和BC，显然，在已知A 的情况下，我们能够通过函数依赖得到整个集合的所有属性ABC，那么我们称A为超码。当超码的任何一个子集都不是超码的时候，我们称之为候选码。例如
AB 是一个超码，但是不是一个候选码，因为A 是AB 的子集，它也是超码。
现在给出属性集合和函数依赖集合R(U,F)，请找出该R 的候选码。
【输入文件】
输入文件的第一行为一个整数 N(N ≤ 10)和M(1 ≤ M ≤ 1000)，表示属性集中的属性个数和函数依赖集中的依赖个数。这里我们默认大写字母中的前N 个字母为我们所考虑的属性。接下来的M 行每行一个字符串表示一个函数依赖，如
ABDE。(中间的蕴含符号是由减号和大于号组成。另外需要说明的是，只有当我们同时得到A 和B 的时候，才能推出D 和E）。
【输出文件】
输出文件的第一行希望你输出你找到的候选码的个数 K。接下来的K 行每行输出一个候选码。候选码本身按字母顺序排列，所有候选码按照字典顺序排列输出。如果没有找到候选码，输出“No candidate key”(不含引号)。
【样例输入】
5 5
AB->C
AC->B
AD->E
BC->D
E->A
【样例输入】
4
AB
AC
BE
CE
【数据规模】
对于30%的测试数据，满足只有二元联系(即不存在函数依赖左边或右边的
属性个数超过1 个)。
对于 40%的测试数据，满足N ≤ 5。
对于70%的测试数据，满足M ≤ 100。
对于100% 的测试数据，满足1 ≤ N ≤ 10,1 ≤ M ≤ 1000。

#include <cstdio>
#include <algorithm>

char str[40],s[1 << 10][20];
bool tag[1 << 10];
int a[1 << 10],b[1 << 10],n,m;

inline bool check(int x)
{
    int tmp = x;
    while (tmp < (1 << n) - 1)
    {
        bool flag = 0;
        for (int i = 0; i < m; ++i)
        if (((a[i] | tmp) == tmp)
            && ((b[i] | tmp) > tmp))
        {tmp |= b[i]; flag = 1;}
        if (!flag) break;
    }
    if (tmp == (1 << n) - 1)
    for (int i = 1; i < 1 << n; ++i)
        tag[x | i] = 0;
	//若可行则将包含它的所有集合的标记记为false。
    return tmp == (1 << n) - 1;
}

int cmp(const void *a,const void *b)
{return strcmp((char *)a,(char *)b);}

int main()
{
    freopen("dependence.in","r",stdin);
    freopen("dependence.out","w",stdout);
    scanf("%d%dn",&n,&m);
    for (int i = 0; i < m; ++i)
    {
        gets(str); int j;
        for (j = 0; str[j] != '-'; ++j)
            b[i] = a[i] |= 1 << (str[j] - 'A');
        for (++++j; str[j]; ++j)
            b[i] |= 1 << (str[j] - 'A');
    }
    for (int i = 1; i < 1 << n; ++i) tag[i] = 1;
    for (int i = 1; i < 1 << n; ++i)
        if (tag[i]) tag[i] &= check(i);
    int cnt = 0;
    for (int i = 1; i < 1 << n; ++i) cnt += tag[i];
    if (!cnt)
    {printf("No candidate keyn"); return 0;}
    printf("%dn",cnt); cnt = 0;
    for (int i = 1; i < 1 << n; ++i) if (tag[i])
    {
        int x = 0;
        for (int tmp = i,j = 0; tmp; tmp >>= 1,++j)
        if (tmp & 1)
            sprintf(s[cnt] + (x++),"%c",j + 'A');
        ++cnt;
    } //把结果找到并输出到字符串中，以便按字典序排序。
    qsort(s,cnt,sizeof(char) * 20,cmp);
    for (int i = 0; i < cnt; ++i)
        printf("%sn",s[i]);
    return 0;
}

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!