title: Generating a basic school schedule
body: <p>I am trying to implement a very basic, very simple version of generating a school schedule from a pre-determined list of shifts and a pre-determined list of people.</p>
  
  <p><strong>Constrains and basic setup</strong></p>
  
  <p>For the sake of example, let us assume the following problem data:</p>
  
  <p>5- people, let's call them A,B,C,D,E want their respective schedules to be assigned.</p>
  
  <p>Each person has a list of shifts, previously chosen.</p>
  
  <p>There are 5 days per week, and let us assume that each day has 3 shifts, so, we have a matrix with 3 rows, 5 columns. Cells that represent the shifts are numbered from top to bottom left to right, starting with 1.</p>
  
  <p>For the list:</p>
  
  <p>A = {1,2,3,5,10,11}</p>
  
  <p>B = {6,7,1,3,8,15}</p>
  
  <p>C = {2,6,8,9,12,13}</p>
  
  <p>D = {3,4,5,6,7,8}</p>
  
  <p>E = {6,8,10,11,13,14}</p>
  
  <p>After attributing all the shifts, the schedule would be:</p>
  
  <p>A - 5,10,11</p>
  
  <p>B - 1,7,15</p>
  
  <p>C - 2,6,12</p>
  
  <p>D - 3,4,9</p>
  
  <p>E - 8,13,14</p>
  
  <p>How can I generalize this concept to a real-world case, with let's say 20 people, 40 shifts, each person choosing 2 out of a list of 8 shifts.</p>
  
  <p>My code is below:</p>
  
  <pre><code> #include &lt;iostream&gt;
      #include &lt;algorithm&gt;
      #include &lt;vector&gt;
      #include &lt;set&gt;
      #include &lt;cmath&gt;
      using namespace std;
  
      #define OPT_DEGREE 300
  
      #define DEBUG 0
      #define vpbvi vector&lt;pair&lt;bool,vector&lt;ULL&gt; &gt; &gt;
      #define ULL unsigned long long
  
      static string dict[20];
  
      void showV(vector&lt;ULL&gt; &amp; v)
      {
          for(int i = 0; i &lt; v.size(); i++)
          {
              cout &lt;&lt; v[i] &lt;&lt; " ";
          }
          cout &lt;&lt; endl;
      }
  
      inline bool do_vectors_intersect(vector&lt;ULL&gt; v1, vector&lt;ULL&gt; v2)
      {
          unsigned long long int target_sz = v1.size()+v2.size();
          set&lt;ULL&gt; s;
          for(int i = 0; i &lt; v1.size(); i++)
              s.insert(v1[i]);
          for(int j = 0; j &lt; v2.size(); j++)
              s.insert(v2[j]);
  
          return !(static_cast&lt;ULL&gt;(s.size()) == target_sz); //True se ha intersecçao False c.c.
      }
  
      void generateAllPossibleShifts(vector&lt;vector&lt;ULL&gt; &gt; &amp; auxiliar, vector&lt;ULL&gt; &amp; _shifts, int N, int K)
      {
          string bitmask(K, 1); // K leading 1's
          bitmask.resize(N, 0); // N-K trailing 0's
  
           // print integers and permute bitmask
           do {
                  vector&lt;ULL&gt; aux;
                  for (int i = 0; i &lt; N; ++i) // [0..N-1] integers
                  {
                      if (bitmask[i])
                      {
                          aux.push_back(_shifts[i]);
                          if(DEBUG){
                              cout &lt;&lt; " " &lt;&lt; _shifts[i];}
                      }
                  }
                  if(DEBUG){
                      cout &lt;&lt; endl &lt;&lt; aux.size() &lt;&lt; " Done. Create Pair and add to scheudle." &lt;&lt; endl;}
                      pair&lt;bool,vector&lt;ULL&gt; &gt; pbvi = make_pair(true,aux);
  
                      for(int i = 0; i &lt; aux.size();i++)
                          if(DEBUG){
                          cout &lt;&lt; "aux[" &lt;&lt;i&lt;&lt;"] = " &lt;&lt; pbvi.second[i] &lt;&lt; endl;}
                      auxiliar.push_back(aux);
                     // fullVec.push_back(pbvi);
                      aux.resize(0); //vector is cleared here
                      if(DEBUG){
                      cout &lt;&lt; "Clear vec" &lt;&lt; endl;
                      cout &lt;&lt; pbvi.second.size() &lt;&lt; " Done" &lt;&lt; endl;
                      cout &lt;&lt;  endl;}
              } while ( prev_permutation(bitmask.begin(), bitmask.end()));
      }
  
      vector&lt;ULL&gt; SumVecs(vector&lt;ULL&gt; &amp; a, vector&lt;ULL&gt; &amp; b)
      {
          vector&lt;ULL&gt; newVec;
          for(int i = 0; i &lt; a.size(); i++)
              newVec.push_back(a[i]);
          for(int i = 0; i &lt; b.size(); i++)
              newVec.push_back(b[i]);
          return newVec;
      }
  
      void AppendToFirst(vector&lt;ULL&gt; &amp; fst, vector&lt;ULL&gt; &amp; snd, int ind)
      {
          for(int k = 0; k &lt; snd.size(); k++)
          fst.push_back(snd[k]);
      }
  
      void OptimizeBeforeNextPassLeft(vector&lt;vector&lt;ULL&gt; &gt; &amp; bsc, vector&lt;vector&lt;ULL&gt; &gt; &amp; arg2)
      {
          int opt = 0;
          for(int i = 0; i &lt; bsc.size(); i++)
          {
              for(int j = 0; j &lt; arg2.size(); j++)
              {
                  if(do_vectors_intersect(bsc[i],arg2[j])==true){
                      arg2.erase(remove(arg2.begin(), arg2.end(), arg2[j]), arg2.end());
                      }
              }
          }
      }
  
      void OptimizeBeforeNextPassRight(vector&lt;vector&lt;ULL&gt; &gt; &amp; bsc, vector&lt;vector&lt;ULL&gt; &gt; &amp; arg2)
      {
          int opt = 0;
          for(int i = bsc.size()-1; i &gt;= 0 ; i--)
          {
              for(int j = 0; j &lt; arg2.size(); j++)
              {
                  if(do_vectors_intersect(bsc[i],arg2[j])==true){
                      bsc.erase(bsc.begin()+i);
                      }
              }
          }
      }
  
      void HardOptimize(vector&lt;vector&lt;ULL&gt; &gt; &amp; bsc, vector&lt;vector&lt;ULL&gt; &gt; &amp; arg2)
      {
          int opt = 0;
          for(int i = bsc.size()-1; i &gt;= 0 ; i--)
          {
              for(int j = 1; j &lt; arg2.size(); j+=2)
              {
                  if(do_vectors_intersect(bsc[i],arg2[j])==true){
                      bsc.erase(bsc.begin()+i);
                      }
              }
          }
      }
  
      //Recursive Function that filters bad attempts and uses "basic" look-ahead technique to narrow search space
      //while building an iterative solution. Can still be optimized.
       void ExpandSearchSpace(vector&lt;vector&lt;vector&lt;ULL&gt; &gt; &gt; &amp; v, vector&lt;vector&lt;ULL&gt; &gt; &amp; buildSol, int guesslvl, vector&lt;vector&lt;ULL&gt; &gt; &amp; placeholder)
      {
         if(guesslvl==4) //Num de pessoas-1
         {
             // cout &lt;&lt; "inside ret " &lt;&lt; endl &lt;&lt; buildSol.size();
              placeholder = buildSol;
             return;
         }
         else
         {
              vector&lt;vector&lt;ULL&gt; &gt; BuildSolCp;
              const int ssz = buildSol.size();
              for(int i = 0; i &lt; ssz;i++)
              {
                  vector&lt;ULL&gt; arg1 = buildSol[i];
                  const int ssz2 = v[guesslvl+1].size();
                 //cout &lt;&lt; "arg1.sz() = " &lt;&lt; arg1.size() &lt;&lt; endl;
                  for(int j = 0; j &lt; ssz2;j++)
                  {
                      if(do_vectors_intersect(buildSol[i], v[guesslvl+1][j])==false){
                   //   cout &lt;&lt; "Iter " &lt;&lt; guesslvl &lt;&lt; "   " &lt;&lt; buildSol[i].size() &lt;&lt; " ";
                     vector&lt;ULL&gt; arg2 = v[guesslvl+1][j];
                   // cout &lt;&lt; "arg2 " &lt;&lt; arg1.size() &lt;&lt; " --- ";
                    vector&lt;ULL&gt; auxi = SumVecs(arg1,arg2);
                   // cout &lt;&lt; "OLFOFKODSJFDSIHFDSFDS" &lt;&lt; endl;
                       BuildSolCp.push_back(auxi);
                     //  cout &lt;&lt; "PUSHDED SDUSHFUDSHF"&lt;&lt;endl;
  
                      }
                  }
              }
  
              guesslvl++;
              if(BuildSolCp.size()&gt; 1000){
              cout &lt;&lt; "WE neeed optimize Jon" &lt;&lt; endl;
              for(int i = 0; i &lt; BuildSolCp.size();i++)
              showV(BuildSolCp[i]);
              vector&lt;vector&lt;ULL&gt; &gt; s= v[guesslvl+1];
              //vector&lt;vector&lt;ULL&gt; &gt; s3= v[guesslvl+4];
            //  vector&lt;vector&lt;ULL&gt; &gt; s4= v[guesslvl+5];
           //  OptimizeBeforeNextPassLeft(BuildSolCp, s);
           OptimizeBeforeNextPassLeft(buildSol,v[guesslvl+2]);
  
            //  OptimizeBeforeNextPassRight(BuildSolCp, s);}
             // OptimizeFromBothSidesAtOnce(BuildSolCp, v[guesslvl+1][j]);
             }
  
              cout &lt;&lt; BuildSolCp.size() &lt;&lt; " " &lt;&lt; guesslvl &lt;&lt; endl;
  
             ExpandSearchSpace(v,BuildSolCp, guesslvl, placeholder);
         }
        // cout &lt;&lt; "end" &lt;&lt; endl;
      }
  
      void ShowPrettyScheudle(vector&lt;vector&lt;ULL&gt; &gt; sol)
      {
          vector&lt;int&gt; scheudle(15);
          for(int j = 0; j &lt;= 10; j+=5){
              for(int i = j; i &lt; j+5; i++)
              {
                  cout &lt;&lt; sol[0][i] &lt;&lt; "\t | ";
              }
              cout &lt;&lt; endl;}
  
      }
  
      int main()
      {
          static vector&lt;vector&lt;ULL&gt; &gt; WorkerVec1,WorkerVec2,WorkerVec3,WorkerVec4, WorkerVec5;
          static vector&lt;vector&lt;ULL&gt; &gt; WorkerVec6,WorkerVec7,WorkerVec8,WorkerVec9, WorkerVec10;
          static vector&lt;vector&lt;ULL&gt; &gt; WorkerVec11,WorkerVec12,WorkerVec13,WorkerVec14, WorkerVec15;
          static vector&lt;vector&lt;ULL&gt; &gt; WorkerVec16,WorkerVec17,WorkerVec18,WorkerVec19, WorkerVec20;
          vector&lt;vector&lt;ULL&gt; &gt; sol;
          static vector&lt;vector&lt;vector&lt;ULL&gt;&gt;&gt; v;
  
          vector&lt;ULL&gt; v1{5,10,11,3,1,2}, v2{1,7,3,15,6,8} ,v3{2,6,12,8,13,9}, v4{3,4,5,6,7,8},v5{6,8,10,11,13,14};
          generateAllPossibleShifts(WorkerVec1, v1,6,3);
          generateAllPossibleShifts(WorkerVec2, v2,6,3);
          generateAllPossibleShifts(WorkerVec3, v3,6,3);
          generateAllPossibleShifts(WorkerVec4, v4,6,3);
          generateAllPossibleShifts(WorkerVec5, v5,6,3);
          v.insert(v.end(), {WorkerVec1,WorkerVec2, WorkerVec3,WorkerVec4, WorkerVec5} );
          cout &lt;&lt; "SIZE OF v[0] in main is " &lt;&lt; v[0].size() &lt;&lt; endl; //20
          for(int i = 0; i &lt; v[0].size(); i++)
          {
              sol.push_back(v[0][i]);
          }
          cout &lt;&lt; sol.size() &lt;&lt; endl; //20
          vector&lt;vector&lt;ULL&gt; &gt; plcholder;
          cout &lt;&lt; "OMG " &lt;&lt; plcholder.size()&lt;&lt;endl;
          ExpandSearchSpace(v,sol,0,plcholder);
  
          cout &lt;&lt; sol.size() &lt;&lt; endl;
          for(int i = plcholder.size()-1; i &gt;= 0; i--){
              cout &lt;&lt; plcholder[i].size() &lt;&lt; endl;
              if(plcholder[i].size()==15){
                   cout &lt;&lt; "FUCK YEA ";showV(plcholder[i]);
                   cout &lt;&lt; endl &lt;&lt; endl;
                  vector&lt;vector&lt;ULL&gt; &gt; vect{plcholder[i]};
                  ShowPrettyScheudle(vect);
                  break;}
                  }
          cout &lt;&lt; endl;
         // cout &lt;&lt; endl &lt;&lt; Ans[0].size() &lt;&lt; " " &lt;&lt; Ans[1].size() &lt;&lt; " " &lt;&lt; Ans[2].size() &lt;&lt; " " &lt;&lt; Ans[3].size();
          return 0;
      }
  </code></pre>
  
  <p>I know the code is messy, but, its essence is simple:</p>
  
  <p>I basically do a brute force where on each pass I "accumulate" blocks of 3 possible shifts and compare them with the next set of possible shifts until I reach the end with only possible shifts selected.</p>
  
  <p>I tried to think in terms of a simple DP formulation, even graphs, but, I'm totally stuck... Maybe thinking in terms of the individual shifts instead of "blocks of shifts" is better, but, right now, I'm at a loss. 
  I've been over this thing for 2 days now and it's sincerely getting on my nerves </p>