title: Most efficient algorithm to generate a random seating chart for benches?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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".</p>
  
  <p>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.</p>
  
  <p><strong>Edit:</strong> 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:</p>
  
  <p><a href="http://kcraigie.com/sittychart" rel="nofollow">http://kcraigie.com/sittychart</a></p>
  
  <p>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. </p>
  
  <pre><code>private static class Person {
      private String m_name = null;
      private Handedness m_handedness = null;
      private Set&lt;Person&gt; m_nonadjacents = null;
  }
  
  private static class Node {
      private Person m_person = null;
      private List&lt;Node&gt; m_possibleRightNodes = null;
      private boolean m_isInPath = false;
  }
  
  private Stack&lt;Node&gt; 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&lt;Node&gt; possibleRightNodes = new LinkedList&lt;&gt;();
          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 &amp;&amp;
                 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&lt;Node&gt; nodes2 = new LinkedList&lt;&gt;(nodes.values());
      Collections.shuffle(nodes2);
  
      // Perform recursive graph traversal
      Stack&lt;Node&gt; pathStack = new Stack&lt;&gt;();
      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&lt;Node&gt; allNodes,
                                        Stack&lt;Node&gt; pathStack,
                                        Node node,
                                        TraversalStatistics stats) {
      stats.numNodesTouched++;
      if(node.isInPath()) {
          stats.numLeavesReached++;
          return false;
      }
      pathStack.push(node);
      node.setIsInPath(true);
      if(pathStack.size() &gt;= 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;
  }
  </code></pre>