编写一个函数,通过添加/删除元素循环遍历子集

Question

问题:开始一组S大小的2n + 1和一个子集A的S大小为n的.你具备的功能addElement(A,x),并removeElement(A,x)可以添加或删除的元素A.编写一个函数,S仅使用这两个操作循环遍历大小为n或n + 1的所有子集A.

我发现有(2n + 1选择n)+(2n + 1选择n + 1)= 2*(2n + 1选择n)子集我需要找到.所以这是我的功能结构:

for (int k=0; k<2*binomial(2n+1,n); ++k) {
    if (k mod 2) {
        // somehow choose x from S-A
        A = addElement(A,x);
        printSet(A,n+1);
    } else
        // somehow choose x from A
        A = removeElement(A,x);
        printSet(A,n);
    }
}

该函数binomial(2n+1,n)只给出二项式系数,函数printSet打印元素,A以便我可以看到我是否击中了所有集合.

不过,我不知道如何选择要添加或删除的元素.我尝试了很多不同的东西,但是我没有得到任何有效的东西.

对于n = 1,这是我找到的解决方案:

for (int k=0; k<6; ++k) {
    if (k mod 2) {
        x = S[A[0] mod 3];
        A = addElement(A,x);
        printSet(A,2);
    } else
        x = A[0];
        A = removeElement(A,x);
        printSet(A,1);
    }
}

且输出为S = [1,2,3]和A=[1]是:

[1,2]
[2]
[2,3]
[3]
[3,1]
[1]

但即使让这个工作n = 2我也做不到.有人能给我一些帮助吗？

Answer 1

这不是一个解决方案,而是另一种思考问题的方法.

制作以下图表:

• 顶点是S大小n或的所有子集n+1.
• 如果两个集合相差一个元素v,w则之间存在边缘.

例如,对于n = 1,您将获得以下循环:

 {1} --- {1,3} --- {3}
  |                 |
  |                 |
{1,2} --- {2} --- {2,3}

你的问题是找到汉密尔顿循环:

哈密​​顿循环(或哈密顿循环)是无向图中的一个循环,它只访问每个顶点一次并返回到起始顶点.确定图中是否存在这样的路径和周期是哈密顿路径问题,它是NP完全的.

换句话说,这个问题很难.

有一些定理给出了在图中存在哈密顿循环的充分条件(例如,如果所有顶点的度数至少N/2在哪里N是顶点的数量),但我所知道的没有立即暗示该图具有哈密顿循环.

您可以尝试其中一种无数算法来确定是否存在哈密顿循环.例如,从关于汉密尔顿路径问题的维基百科文章中:

用于定位哈密顿路径的简单启发式算法是构造路径abc ...并将其扩展直到不再可能; 当路径abc ... xyz不能再延长因为z的所有邻居已经位于路径中时,一个人返回一步,移除边缘yz并用y的不同邻居扩展路径; 如果没有选择产生哈密尔顿路径,则进一步退回,移除边缘xy并使用x的不同邻居扩展路径,依此类推.该算法肯定会找到一个哈密尔顿路径(如果有的话),但它会以指数时间运行.

希望这可以帮助.

好消息:虽然汉密尔顿循环问题一般很难,但这个图非常好:它是二分和(n+1)常规的.这意味着这个特定图表可能有一个很好的解决方案.

坏消息:经过一些搜索后,事实证明这个问题被称为中级猜想,它似乎起源于1980年左右.我可以说,最好的问题仍然是开放的,但它有经过计算机验证n <= 17(我从2009年12月发现了一份声称要验证的预印本n=18).这两页有关于问题和参考的其他信息:

• http://www.math.uiuc.edu/~west/openp/revolving.html
• http://garden.irmacs.sfu.ca/?q=op/middle_levels_problem