小编kcr*_*gie的帖子

我正在为一位教师的家庭成员编写应用程序.她要求一个应用程序,允许她进入一群孩子,设定他们的惯用手,设置他们不能坐在旁边的人,指定每个工作台有多少个座位,然后为孩子们生成一个随机的布局,这样就没有了 - 汉德斯坐在右手边的右边,不应该坐在一起的孩子们不会坐在长凳上.

这与通用表座位算法的问题并不完全相同,因为一个工作台有2个端点,并且因为节点没有"值"来创建任何优先分组.

我决定创建一个有向图,其中边表示谁可以坐在给定孩子的右边.然后我从每个节点做一个递归DFS而不触摸节点两次,直到我得到一个触摸每个节点的路径.一个问题是,在每个工作台的"尽头",任何人都可以坐到他们的"右边".

这个算法似乎总是有效,这很好.但是,一旦我超过10个孩子在一个长凳上,假设长椅可以说20个孩子,那么运行时似乎会变得非常糟糕.我做错了什么,还是有更好的方法来解决这个问题？Java代码如下.

编辑:对不起,我没有说清楚,但我希望每次都能实现RANDOM座位安排,这样孩子们就不会被困在同一个地方或同一个长凳上或者在同一个孩子旁边.此外,我的应用程序运行此算法:

http://kcraigie.com/sittychart

目前我正在强制执行1,000,000个节点触摸的上限,这样我的服务器就不会受到冲击.您可以看到算法似乎正确缩放,直到您将每个工作台的座位设置为9左右,此时它立即变得难以处理.

private static class Person {
    private String m_name = null;
    private Handedness m_handedness = null;
    private Set<Person> m_nonadjacents = null;
}

private static class Node {
    private Person m_person = null;
    private List<Node> m_possibleRightNodes = null;
    private boolean m_isInPath = false;
}

private Stack<Node> generateSeatingArrangement() {
    // Generate randomized directed graph, start with all nodes as root nodes
    for(Person leftPerson: people.values()) {
        Node node = new Node(leftPerson);
        nodes.put(leftPerson, node);
    } …

有人请告诉我这有什么意义,以及如何让它停止？说真的,我疯了还是64位Windows长型只有4个字节？这有什么用呢？我认为本机长原始大小应该与本机寄存器大小相同.

[32-bit Linux]

me@u32:~$ ./sizes32
sizeof(char):      1
sizeof(short):     2
sizeof(int):       4
sizeof(long):      4
sizeof(long long): 8

[64-bit Linux]

me@u64:~$ ./sizes64
sizeof(char):      1
sizeof(short):     2
sizeof(int):       4
sizeof(long):      8
sizeof(long long): 8

[32-bit Windows]

C:\Users\me\Downloads>sizes32.exe
sizeof(char):      1
sizeof(short):     2
sizeof(int):       4
sizeof(long):      4
sizeof(long long): 8

[64-bit Windows]

C:\Users\me\Downloads>sizes64.exe
sizeof(char):      1
sizeof(short):     2
sizeof(int):       4
sizeof(long):      4
sizeof(long long): 8