Most efficient algorithm to generate a random seating chart for benches?

Question

I'm writing an app for a family member who is a teacher. She asked for an app to allow her to enter a bunch of kids, set their handedness, set who they can't sit next to, specify how many seats per bench, and then generate a random layout for the kids such that no left-handers sit to the right of a right-hander, and the kids that shouldn't sit next to each other are not adjacent on a bench.

This isn't quite the same problem as a generic table seating algorithm because there are 2 ends to a bench, and because there is no "value" to the nodes to create any preferential groupings.

I decided to create a directed graph where the edges represent who can sit to the right of a given kid. Then I do a recursive DFS from every node without touching a node twice until I get a path where every node has been touched. One catch is that at the "end" of every bench, anyone can sit to their "right".

This algorithm seems to always work, which is nice. But the runtime seems to grow awfully once I get beyond say 10 kids on a single bench assuming the benches can seat say 20 kids. Am I doing something wrong, or is there some much better way to solve this? Java code follows.

Edit: Sorry I didn't make this clear, but I want to achieve a RANDOM seating arrangement each time, such that the kids don't get stuck in the same place or on the same bench or next to the same kids. Also I've got my app running against this algorithm here:

http://kcraigie.com/sittychart

Currently I'm enforcing an upper limit of 1,000,000 node touches so that my server doesn't get hosed. You can see that the algorithm seems to scale properly until you set the seats per bench to 9 or so at which point it immediately becomes unwieldy.

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);
    }
    // Create all edges based on constraints
    for(Node leftNode: nodes.values()) {
        List<Node> possibleRightNodes = new LinkedList<>();
        for(Node rightNode: nodes.values()) {
            Person leftPerson = leftNode.getPerson();
            Person rightPerson = rightNode.getPerson();
            if(leftNode==rightNode) {
                log.fine("Can't seat '" + leftPerson.getName() + "' next to himself");
                continue;
            }
            if(leftPerson.getHandedness()==Person.Handedness.RIGHT_HANDED &&
               rightPerson.getHandedness()==Person.Handedness.LEFT_HANDED) {
                log.fine("Can't seat right-handed '" + leftPerson.getName()
                         + "' to the left of left-handed '" + rightPerson.getName() + "'");
                continue;
            }
            if(leftPerson.getNonadjacents().contains(rightPerson)) {
                log.fine("Can't seat '" + leftPerson.getName() + "' next to '" + rightPerson.getName() + "'");
                continue;
            }
            if(rightPerson.getNonadjacents().contains(leftPerson)) {
                // TODO: This should be redundant but not enforcing right now...
                log.fine("Can't seat '" + rightPerson.getName() + "' next to '" + leftPerson.getName() + "'");
                continue;
            }
            log.fine("Can seat '" + leftPerson.getName() + "' to the left of '" + rightPerson.getName() + "'");
            possibleRightNodes.add(rightNode);
        }
        Collections.shuffle(possibleRightNodes);
        leftNode.setPossibleRightNodes(possibleRightNodes);
    }
    List<Node> nodes2 = new LinkedList<>(nodes.values());
    Collections.shuffle(nodes2);

    // Perform recursive graph traversal
    Stack<Node> pathStack = new Stack<>();
    for(Node node: nodes2) {
        TraversalStatistics stats = new TraversalStatistics();
        boolean isPathFound = depthFirstSearchRecur(numSeatsPerBench, nodes2, pathStack, node, stats);
        if(isPathFound) {
            break;
        }
        pathStack.clear();
    }
}

// The resursive DFS method
private boolean depthFirstSearchRecur(int numSeatsPerBench,
                                      List<Node> allNodes,
                                      Stack<Node> pathStack,
                                      Node node,
                                      TraversalStatistics stats) {
    stats.numNodesTouched++;
    if(node.isInPath()) {
        stats.numLeavesReached++;
        return false;
    }
    pathStack.push(node);
    node.setIsInPath(true);
    if(pathStack.size() >= allNodes.size()) {
        return true; // We win!
    }
    if(pathStack.size() % numSeatsPerBench == 0) {
        // "End" of a bench, anyone can "sit to the right of" me
        for(Node node2: allNodes) {
            if(node == node2) {
                // Can't sit next to myself
                continue;
            }
            if(depthFirstSearchRecur(numSeatsPerBench, allNodes, pathStack, node2, stats)) {
                return true;
            }
        }
    } else {
        for(Node node2: node.getPossibleRightNodes()) {
            if(depthFirstSearchRecur(numSeatsPerBench, allNodes, pathStack, node2, stats)) {
                return true;
            }
        }
    }
    pathStack.pop();
    node.setIsInPath(false);
    return false;
}

Answer 1

I think you don't need to generate a list of possible left Nodes for each node. Instead, do it on the fly in an recursive algorithm with trackback.

On the first seat you seat the first node. Search through the list of nodes for the first possible neighbour and seat him there. Repeat until the plan is complete or you reach a dead end. In that case, go back one seat and seat the next possible person there (eg. if it was Node 4 change it to Node 5). Either try the next seat from there or, if not possible to find a next Node (e.g. the node there was already the last on the list) go back one step until there is a next node.

With this method, you should statistically have to compute n!/2 possibilities for a number of students n to find an answer.

PS: I hope you understand my descrition of the algorithm. If i had more time i would have made a diagram.

Answer 2

I wouldn't automatically think graphs for this sort of problem. Building the graph gives a complexity of O(n^2), and a DFS is O(V+E) (with V being verticies, E being edges, which will be less than O(n^2), so you're still looking at O(n^2)).

If no left hander can be directly to the right of a right hander, then for a single bench, there's no way to order the kids so that any right hander is to the right at all of any left hander. So your result is always going to look something like:

l l l l l r r r r r

You can prove this by induction. If the correct solution has a right hander anywhere to the left of a left hander, i.e :

r ? l

Then there must be a kid '?' who is either left or right handed that doesn't break the rule. If the kid is right handed, it breaks it for the first left handed kid. If the kid is left handed, it breaks the rule for that kid.

So, what you need to do is sort your left and right handed kids, and look at who can and can't sit next to each other. In reality, if the kids relationships aren't like an episode of the bold and the beautiful, and you don't have a crazy graph of who can and can't sit next to each other, you could probably use a greedy algorithm. You would just start from the list of left handers, pulling out one kid at a time. If they won't sit next to the last one, then pull out the next, and try again. This would give you a complexity of O(n), but you might not get a solution everytime.

Alternatively, you could use a recursive algorithm to put together compatible groups of kids one pair at a time, and build up a solution that way. This would obviously be a more complex algorithm, but you'd always get an answer.

If you've got more than one bench though, then this won't work at all.