Number of ways to seat people given certain constraints

See also questions close to this topic

• Are there any efficient ways to populate a balanced tree structure

  I have a balanced binary tree structure:

  Node 0 at depth 0 is the root. The root's left child is 1 and right child is 2, and so on.

  Please see image:

  The total depth of the tree is given as N. This N is the only parameter of the problem. Nodes at level N are designated as leaf nodes.

  I am storing this tree using the following node structure.

  struct node_s{
      int n, depth, parent;//n is node number
      int nodescendents;//number of descendents of the current node
      std::vector<int> descendents;//Descendents in ascending order
      int lchild, rchild;//Immediate left child and right child
      std::vector<int> lchildleaves;//leaf nodes that descend from the immediate 
                                                        //left child
      std::vector<int> rchildleaves;//leaf nodes that descend from the immediate 
                                                        //right child
  };
  

  I intend to store the tree itself as:

  std::vector<node_s> tree;
  

  Is there a way to numerically efficiently populate the tree vector using simple algebra roughly as:

  //Creating the nth node, beginning from 0th node, then 1st node and so on
  nodes_s node;
  //populate all data structures of the nth node
  //precisely, here, there are loops, algebraic calculations, etc., that can help 
  //populate all of the node_s data members.
  tree.push_back(node);
  

  The only way I can think of as of now is to construct a graph explicitly and run some sort of Dijkstra algorithm to figure out these data structure values for each node.
• Multidimensional array sorting by cluster type (similar to Sudoku)

  Let's say we have an examination hall, the capacity is between 40 to 160 seats

  Inputs: number of seats and number of clusters.

  Let's say the user entered 16 seats and 4 clusters.

  The cluster4 has members or fields (computing, pharmacy, accounting, psychology)

  Array 1st has 4 members (1a,2a,3a,4a)
  Array 2nd has 4 members (1b,2b,3b,4b)
  Array 3rd has 4 members (1c,2c,3c,4c)
  Array 4th has 4 members (1d,2d,3d,4d)
  

  so the distribution can be as follows:

  1a-Accounting, 1c-Pharmacy  ---   2a-Accounting, 2c-Pharmacy
  1b-Psychology, 1d-Computing  ---   2b-Psychology, 2d-Computing
  
  3a-Accounting, 3c-Pharmacy  ---   4a-Accounting, 4c-Pharmacy
  3b-Psychology, 3d-Computing  ---   4b-Psychology, 4d-Computing
  

  ---

  If the user enters 16 seats and 3 clusters, the distribution can be as follows:

  1a-Accounting, 1c-Pharmacy
  

  2a-Accounting, 2c-Pharmacy 1b-Psychology 2d-Computing

  3a-Accounting,                 4c-Pharmacy
  3b-Psychology, 3d-Computing    4b-Psychology, 4d-Computing
  
  3a-Accounting,                 4c-Pharmacy
  3b-Psychology, 3d-Computing    4b-Psychology, 4d-Computing
  
  3a-Accounting,                 4c-Pharmacy
  

  ---

  Let's say the user enters 8 seats and 4 clusters

  1a-Accounting, 1c-Pharmacy     2a-Accounting, 2c-Pharmacy
  1b-Psychology, 1d-Computing    2b-Psychology, 2d-Computing
  
  3a-Accounting, 3c-Pharmacy     4a-Accounting, 4c-Pharmacy
  3b-Psychology, 3d-Computing    4b-Psychology, 4d-Computing
  

  where every student type is different than the one next to him.

  ---

  It seems like 4 switch statements with 5 for loops and nested if statements to compare values, using math.random to randomise cluster values where every cluster is given a weight to compared with the next cluster so they can be arranged in a sequence, and also to insure no collusion is occurring when arranging two groups next to each other.

  I find it pretty challenging but I wish to request your assistance because I have so much work to do and less time to try coding.
• QuickSort - Median Three

  I am working on the QuickSort - Median Three Algorithm. I have no problem with the first and last element sorting. But, when comes to the Median-three, I am slightly confused. I hope someone could help me on this.

  Would be appreciate if someone could provide me some pseudocode?

  My understanding is to get the middle index by doing this. (start + end) / 2 , then swap the middle pivot value to the first value, after all these done it should goes well with the normal quick sort ( partitioning and sorting).

  Somehow, I couldn't get it works. Please help!
• Initialize two 2D arrays and fill the first column and first row of one of the arrays with 0

  This function should initialize arrays C[m+1][n+1] and B[m][n] and fill the first row and first column of C with zeros. Note: int*** C refers to a pointer points to the 2D integer array. Please correct the error.

  void initLCSTable(int*** C, char*** B, int m, int n)
  {
  C[m + 1][n + 1] = {{0}};
  B[m][n];
  }
  void printLengthTable(int** C, int m, int n);
  void printArrowTable(char** B, int m, int n);
  
  main {
  int** C;
  char** B;
  initLCSTable(&C, &B, m, n);
  
  cout << "\nTable C" << endl;
  printLengthTable(C, m, n);
  
  cout << "\nTable B" << endl;
  printArrowTable(B, m, n);
  return 0;
  }
  

  Output should look like this (ignore the non-zeros since that is a different Longest Subsequence question all together): https://i.stack.imgur.com/ElWMY.png
• Dynamic programming: Counting super numbers in between

  Given two numbers, let's call them X and Y how to find all "super" numbers between them.

  A super number is a number whose neighbouring digits have an absolute difference more than 1. So, for example, number 132 is not a super number because 3 and 2 have a difference equal to 1. Number 62 is a super number because diffrence between 6 and 2 is greather than 1.

  How to find all super numbers between X and Y (included) using Dynamic programming?

  1 < X,Y < 10^5000 
  
• Value iteration to determine probability of winning the dice game "Pig"

  I have recently been researching into the optimisation of the dice game "Pig" and have come across the paper "Optimal Play of the Dice Game Pig" by Todd Neller. In this paper he uses value iteration to determine the probability of winning the game from each possible state of the game using the optimal strategy.

  In a later paper, he then talks about comparing policies, one of which being the "Hold at 20" strategy. He includes the probabilities that the optimal player will beat the "Hold at 20" player, however never makes it clear how he came about these results. Is there a way to calculate the probability of winning the game from each state when using "Hold at 20" as with the optimal play, using value iteration or some other technique? If so, it then seems possible to compare the strategies using the algorithm stated.