/*  AlternateValue.cc - A program that computes the results of the 
 *  sequential entry algorithm.
 *  Copyright (C) 2006 Elette Boyle
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2
 *  of the License, or (at your option) any later version.
 */

/*  Date: August 23, 2006 
 *  Author: Elette Boyle
 *  Email: eboyle@caltech.edu
 */

/*  This program is an implementation of the 1-1 algorithm in the paper 
 *  "Sequential Entry in Many-to-Many Matching Markets"
 */


#include <stdio.h>

#define ACCEPT 1
#define REJECT 0
#define MEN 0
#define WOMEN 1

#define NUM_PLAYERS 8
#define NUM_MEN 4
#define NUM_WOMEN 4
#define NUM_MATCHINGS_STORED 15
#define NUM_POSSIBLE_MATCHINGS 24

//Proposal class is used in preProposalProcess when ordering 
// possible proposals in order of utility 
class Proposal {
public:
  int player;
  int util;
  int index;
  Proposal* next;
  Proposal(int player, int utility, int playerIndex, Proposal* nextProp);
};

Proposal::Proposal(int player, int utility, int playerIndex, Proposal* nextProp) {
  this->player = player;
  util = utility;
  index = playerIndex;
  next = nextProp;
}


// recursively go through all possible permutations of joining order
void recursePermutations(int currentSpot);

// for a given ordering of the players, compute the resulting matching
// also prints out optimal matching for men and for women
void calculateUtilities();

// determine to whom the player will propose
void preProposalProcess(int currentNumPlayers, int player, int noPropPlayer);

// in the propose function, player 1 proposes to player 2, leading to a 
// possible repairing of player 2's current spouse 
int propose(int player1, Proposal* proposal, int currentNumPlayers);

// recursively find all permutations of the party with greater number of players
void findAllMatchings (int currentSpot, int stopSpot, int men_or_women);

void determineFeasibility();

//given the utility vector of a particular matching, detemrmine if the matching is stable
int determineStability(int currentUtilityVector[]);


//U is the array of player utilities: 
// U[x][y] is utility of player x to be matched with player y

/*int U[5][5] = {{-1,-1,-1,-1,-1},
               { 0,-1,-1, 1, 2},
               { 0,-1,-1, 1, 2},
               { 0, 1, 2,-1,-1},
               { 0, 2, 1,-1,-1}};
*/

/*int U[6][6] = {{-1,-1,-1,-1,-1,-1},		//5 players: 2 men, 3 women
               { 0,-1,-1, 3, 1, 2},
               { 0,-1,-1, 2, 3, 1},
               { 0, 1, 2,-1,-1,-1},
               { 0, 2, 1,-1,-1,-1},
               { 0, 2, 1,-1,-1,-1}};
*/

/*int U[6][6] = {{-1,-1,-1,-1,-1,-1},		//5 players: 2 women, 3 men
               { 0,-1,-1,-1, 2, 1},
               { 0,-1,-1,-1, 1, 2},
               { 0,-1,-1,-1, 2, 1},
               { 0, 1, 3, 2,-1,-1},
               { 0, 2, 1, 3,-1,-1}};
*/
/*int U[7][7] = {{-1,-1,-1,-1,-1,-1,-1},
               { 0,-1,-1,-1, 3, 1, 2},
               { 0,-1,-1,-1, 1, 2, 3},
               { 0,-1,-1,-1, 3, 2, 1},
               { 0, 1, 3, 2,-1,-1,-1},
               { 0, 2, 1, 3,-1,-1,-1},
               { 0, 1, 2, 3,-1,-1,-1}};
*/
int U[9][9] = {{-1,-1,-1,-1,-1,-1,-1,-1,-1},
               { 0,-1,-1,-1,-1, 3, 1, 2, 4},
               { 0,-1,-1,-1,-1, 2, 3, 4, 1},
               { 0,-1,-1,-1,-1, 4, 3, 1, 2},
               { 0,-1,-1,-1,-1, 1, 3, 4, 2},
               { 0, 1, 4, 3, 2,-1,-1,-1,-1},
               { 0, 2, 1, 4, 3,-1,-1,-1,-1},
               { 0, 2, 3, 4, 1,-1,-1,-1,-1},
               { 0, 1, 2, 3, 4,-1,-1,-1,-1}};


/*int U[10][10] = {{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},		//9 players: 5 men, 4 women
                 { 0,-1,-1,-1,-1,-1, 3, 1, 2, 4},
                 { 0,-1,-1,-1,-1,-1, 4, 3, 1, 2},
                 { 0,-1,-1,-1,-1,-1, 3, 4, 2, 1},
                 { 0,-1,-1,-1,-1,-1, 1, 3, 4, 2},
                 { 0,-1,-1,-1,-1,-1, 1, 2, 3, 4},
                 { 0, 3, 1, 2, 4, 5,-1,-1,-1,-1},
                 { 0, 5, 3, 1, 2, 4,-1,-1,-1,-1},
                 { 0, 4, 5, 3, 1, 2,-1,-1,-1,-1},
                 { 0, 2, 4, 5, 3, 1,-1,-1,-1,-1}};
*/
/*int U[11][11] = {{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
                 { 0,-1,-1,-1,-1,-1, 3, 1, 2, 4, 5},
                 { 0,-1,-1,-1,-1,-1, 5, 3, 1, 2, 4},
                 { 0,-1,-1,-1,-1,-1, 4, 5, 3, 1, 2},
                 { 0,-1,-1,-1,-1,-1, 2, 4, 5, 3, 1},
                 { 0,-1,-1,-1,-1,-1, 1, 2, 4, 5, 3},
                 { 0, 3, 1, 2, 4, 5,-1,-1,-1,-1,-1},
                 { 0, 5, 3, 1, 2, 4,-1,-1,-1,-1,-1},
                 { 0, 4, 5, 3, 1, 2,-1,-1,-1,-1,-1},
                 { 0, 2, 4, 5, 3, 1,-1,-1,-1,-1,-1},
                 { 0, 1, 2, 4, 5, 3,-1,-1,-1,-1,-1}};
*/
/*int U[8][8] = {{ 0, 0, 0, 0, 0, 0, 0, 0},		//7 players: 3 men, 4 women
               { 0,-1,-1,-1, 1, 2, 3, 4},
               { 0,-1,-1,-1, 2, 3, 4, 1},
               { 0,-1,-1,-1, 3, 4, 1, 2},
               { 0, 3, 2, 1,-1,-1,-1,-1},
               { 0, 1, 3, 2,-1,-1,-1,-1},
               { 0, 2, 1, 3,-1,-1,-1,-1},
               { 0, 3, 2, 1,-1,-1,-1,-1}};
*/
/*int U[8][8] = {{ 0, 0, 0, 0, 0, 0, 0, 0},		//7 players: 4 men, 3 women
               { 0,-1,-1,-1,-1, 3, 1, 2},
               { 0,-1,-1,-1,-1, 1, 2, 3},
               { 0,-1,-1,-1,-1, 3, 2, 1},
               { 0,-1,-1,-1,-1, 1, 2, 3},
               { 0, 1, 4, 3, 2,-1,-1,-1},
               { 0, 2, 1, 4, 3,-1,-1,-1},
               { 0, 2, 3, 4, 1,-1,-1,-1}};
*/
// stores the current ordering of players to go through the proposing process
int currentOrder[2][NUM_PLAYERS+1];
//int currentOrder[2][NUM_PLAYERS+1] = {{0,4,2,6,1,3,5},{0,0,0,0,0,0,0}};		//numplayerscheck

// stores each distinct matching and its frequency
// element [i][0] = number of occurrences of matching i
// element [i][x] = partner of player x in matching i (0 if single)
int totalDifferentPairs[NUM_MATCHINGS_STORED][NUM_PLAYERS+1];

FILE* outFile;

///////////////////////////////////////////

//information printout
void printCurrentOrder() {  

/*
  if(currentOrder[0][NUM_PLAYERS]<=NUM_MEN) {
    printf("  ");
    for(int i=1; i<=NUM_PLAYERS; i++)
      printf("%d", currentOrder[0][i]);
    printf("\t");
    int printStars=0;
    for(int i=1; i<=NUM_PLAYERS; i++) {
      //printf("%d+%d ", currentOrder[0][i], currentOrder[1][i]);
      if(currentOrder[0][i]==1 && currentOrder[1][i]==4)  printStars = 1;
    }
    if(printStars) printf("***");
  }
*/


      //print out all orderings with one of some set proposing last but not yielding a certain soln
//if(currentOrder[0][NUM_PLAYERS]<=NUM_MEN && currentOrder[0][NUM_PLAYERS-1]>NUM_MEN) {
//  if(currentOrder[0][1]>NUM_MEN && currentOrder[0][2]<=NUM_MEN && currentOrder[0][3]>=NUM_MEN && currentOrder[0][4]<=NUM_MEN && currentOrder[0][5]>=NUM_MEN && currentOrder[0][6]<=NUM_MEN && currentOrder[0][7]>NUM_MEN && currentOrder[0][8]<=NUM_MEN) {
  if( 0) {  // currentOrder[0][NUM_PLAYERS]==1 || currentOrder[0][NUM_PLAYERS]==4) {
    int womenOptimal = 1;
    int menOptimal = 1;
    for(int i=1; i<=NUM_PLAYERS; i++) {
      if(currentOrder[0][i]==1 && currentOrder[1][i]!=6)   womenOptimal = 0;
//    if(currentOrder[0][i]==3 && currentOrder[1][i]!=8)   womenOptimal = 0;
      if(currentOrder[0][i]==5 && currentOrder[1][i]!=2)   menOptimal = 0;
//    if(currentOrder[0][i]==3 && currentOrder[1][i]!=7)   menOptimal = 0;
    }
//  if(!womenOptimal) {     
      fprintf(outFile, "\n");
      for(int i=1; i<=NUM_PLAYERS; i++)    //for(int i=1; i<=NUM_PLAYERS; i++)
        fprintf(outFile, "%d", currentOrder[0][i]);
      if(menOptimal)   fprintf(outFile, "  M");
      if(womenOptimal) fprintf(outFile, "    W");
      fprintf(outFile,"\t");
      for(int j=1; j<= NUM_PLAYERS; j++) {
        //if(currentOrder[0][j]==1 && currentOrder[1][j]!=4) printf("***");
        fprintf(outFile, "%d+%d ", currentOrder[0][j], currentOrder[1][j]);
      }
    }
//}

/*
  if(currentOrder[0][1]<=NUM_MEN && currentOrder[0][4]<=NUM_MEN && currentOrder[0][6]<=NUM_MEN) {
    printf("\n");
    for(int i=1; i<=NUM_PLAYERS; i++)
      printf("%d", currentOrder[0][i]);
    printf("\t");
    for(int j=1; j<= NUM_PLAYERS; j++) {
      if(currentOrder[0][j]==1 && currentOrder[1][j]!=4) printf("***");
      printf("%d+%d ", currentOrder[0][j], currentOrder[1][j]);
    }
  }
*/
/*
  if(currentOrder[0][NUM_PLAYERS]<=NUM_MEN) {  // && currentOrder[1][NUM_PLAYERS]!=2) {
    printf("\t\t\t");
    for(int i=1; i<=NUM_PLAYERS; i++)
      printf(" %d+%d", currentOrder[0][i], currentOrder[1][i]);       
  }

  if(currentOrder[0][NUM_PLAYERS]==6 && currentOrder[0][NUM_PLAYERS-2]>NUM_MEN && currentOrder[0][NUM_PLAYERS-1]==1  ) {

//    printf("\t");
//    for(int j=1; j<=NUM_PLAYERS; j++)
//      printf("%d", currentOrder[0][j]);
//    printf(":   ");


    for(int i=1; i<=NUM_PLAYERS; i++) {
//      printf(" %d+%d", currentOrder[0][i], currentOrder[1][i]);
      if(currentOrder[0][i]==2 && currentOrder[1][i]== 4) {
        printf("\t\t");
        for(int i=1; i<=NUM_PLAYERS; i++)
          printf(" %d+%d", currentOrder[0][i], currentOrder[1][i]);
      }

/*      if(currentOrder[0][i]==1 && currentOrder[1][i]==4 &&
  	currentOrder[0][NUM_PLAYERS-2]<=NUM_MEN && currentOrder[0][NUM_PLAYERS-1]==6 && currentOrder[0][NUM_PLAYERS]==3)
          printf("***");
 
    }
  }
*/
}


// set all pairs in currentOrder to 0 (single) before each proposing process
void resetCurrentOrderPairs() {
  for(int i=0; i<=NUM_PLAYERS; i++)
    currentOrder[1][i] = 0;
}

// print the different matchings and their frequencies
void printTotalDifferentPairs() {
  int counter = 0;
  printf("\n\nDifferent pairs: ");
  while(totalDifferentPairs[counter][0]!=0 && counter<NUM_MATCHINGS_STORED) {
    printf("\n  %d: ", totalDifferentPairs[counter][0]);
    for(int j=1; j<=NUM_PLAYERS; j++)  printf(" %d+%d", j, totalDifferentPairs[counter][j]);
    counter++;
  }
}

void printAllMatchingsAndUtils(int men_or_women, int numPairs);

int globalCounter = 0;
double totalUtilities[NUM_PLAYERS+1];

//used in determining feasibility
int allMatchingsAndUtils[NUM_POSSIBLE_MATCHINGS][NUM_PLAYERS+1][3];
int numMatchings = 0;
int permArray[NUM_PLAYERS+1];


//////////////////////////////////////////////////////////////////////////////////////////

int main() {
  // initialize arrays to all zeros
  for(int i=0; i<NUM_MATCHINGS_STORED; i++)
    for(int k=0; k<NUM_PLAYERS; k++)
      totalDifferentPairs[i][k] = 0;
  for(int j=0; j<=NUM_PLAYERS; j++) {
    currentOrder[0][j]=0;
    currentOrder[1][j]=0;
  }
  for(int i=0; i<NUM_POSSIBLE_MATCHINGS; i++)
    for(int j=0; j<=NUM_PLAYERS; j++)
      for(int k=0; k<3; k++)
        allMatchingsAndUtils[i][j][k] = 0;
  for(int i=0; i<=NUM_PLAYERS; i++)
    permArray[i]=0;
  for(int k=0; k<=NUM_PLAYERS; k++)
    totalUtilities[k]=0;   

  outFile = fopen("OutputFile", "w+");

  // begin going through all the permutations
  recursePermutations(1);			//currentSpot=1 (ie, permute all players)
//  calculateUtilities(); 
  printf("\nTotal permutations: %d", globalCounter);
  printTotalDifferentPairs();
  printf("\nAverage utilities: ");
  for(int i=1; i<=NUM_PLAYERS; i++)  printf("%.2f ", totalUtilities[i]/globalCounter);
  printf("\n\n");

  determineFeasibility();
  return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////

/* void recursePermutations(int currentSpot)
 * int currentSpot - designates which location from 1 to NUM_PLAYERS to fill
 * 
 * Go through all permutations of the players by using recursion.  For each 
 * permutation, call calculateUtilities to determine the resulting matching
 * and the corresponding utility vector
 */
void recursePermutations(int currentSpot) {
  int nonused = 1;

  for(int i=1; i<= NUM_PLAYERS; i++) {		//steps through all the different nonused values
    nonused = 1;
    for(int j=1; j < currentSpot; j++) {
      if(currentOrder[0][j] == i)
        nonused = 0;
    }
    if(nonused) {				//don't repeat a value already listed
      currentOrder[0][currentSpot] = i;	
      if(currentSpot < NUM_PLAYERS)
        recursePermutations(currentSpot+1);
      else {					//if we have a complete legal ordering
        globalCounter++;
        calculateUtilities();			//calculate the matching and utilities of the ordering
        printCurrentOrder();
        resetCurrentOrderPairs();		//initialize partners back to zeros (single)
      }
    }
  }
}


/* void CalculateUtilities
 * Given an ordering of the players, determine the resultant matching and the 
 * corresponding utility vector.  If the ordering is 1,2,3,... or ...3,2,1
 * then print matching out as optimal strategy for women or men (respectively).
 * Adjust totalDifferentPairs to include the matching.
 */

void calculateUtilities() {
  int matchingUtilities[NUM_PLAYERS+1];
  for(int j=0; j<=NUM_PLAYERS; j++) matchingUtilities[j]=0;

  for(int i=1; i<=NUM_PLAYERS; i++) {			//go down the line and commence proposals in order
    preProposalProcess(i, currentOrder[0][i], 0);
  }
  int currentPlayer = 0;
  int orderedPairs[NUM_PLAYERS+1];
  for(int i=1; i<= NUM_PLAYERS; i++) {
    currentPlayer = currentOrder[0][i];
    matchingUtilities[currentPlayer] = U[currentPlayer][currentOrder[1][i]];
    totalUtilities[currentPlayer] += matchingUtilities[currentPlayer];
    //printf("matchingUtil: %d", matchingUtilities[currentPlayer]);
    orderedPairs[currentPlayer] = currentOrder[1][i];			//store the pairs
    //printf("\t %d %d ", currentPlayer, currentOrder[1][i]);
    //printf("    %d", orderedPairs[currentPlayer]);
  }

  int bestForMen = 1;		//flag stays 1 if players are in order of number
  int bestForWomen = 1;		//flag stays 1 if players are in reverse order of number
  for(int j=1; j<=NUM_PLAYERS; j++) {
    if(j != currentOrder[0][j])  bestForWomen = 0;
    if(currentOrder[0][j] != (NUM_PLAYERS - j + 1))   bestForMen = 0;
  }
  if(bestForMen) {		//print out the optimal matching for the men and women
    printf("\nM: ");
    for(int j=1; j<=NUM_PLAYERS; j++)  printf(" %d+%d", j, orderedPairs[j]);
    printf("\n");
  } else if(bestForWomen) {
    printf("\nW: ");
    for(int j=1; j<=NUM_PLAYERS; j++)  printf(" %d+%d", j, orderedPairs[j]);
    printf("\n");
  }

  int finished = 0;
  int counter = 0;
  while( !finished && counter<NUM_MATCHINGS_STORED ) {		//Adjust totalDifferentPairs to include current matching
    if(totalDifferentPairs[counter][0] == 0) {
      totalDifferentPairs[counter][0] = 1;
      for(int i=1; i<=NUM_PLAYERS; i++) {
        totalDifferentPairs[counter][i] = orderedPairs[i];
      }
      finished = 1;
    }
    else {
      int equal = 1;
      for(int i=1; i<=NUM_PLAYERS; i++) {
        if(totalDifferentPairs[counter][i] != orderedPairs[i])
          equal = 0;
      }
      if(equal) {
        (totalDifferentPairs[counter][0])++;
        finished = 1;
      }
    }
    counter++;
  }

//  printTotalDifferentPairs();


/*  if(matchingUtilities[1]!=3 || matchingUtilities[2]!=3 || matchingUtilities[3]!=1 || 
	matchingUtilities[4]!=3 || matchingUtilities[5]!=3 || matchingUtilities[6]!=3) {
    printCurrentOrder();
    printf("%d%d%d%d%d%d:\t",currentOrder[0][1],currentOrder[0][2],currentOrder[0][3],
	currentOrder[0][4],currentOrder[0][5],currentOrder[0][6]);
  }
*/
/*  if(globalCounter % 10 == 0) {	//debug print: output every 10 matchings
    printf("\t");
    for(int k=1; k<=NUM_PLAYERS; k++) printf(" %d", matchingUtilities[k]);
    //printf("\t");    
    //for(int k=1; k<=NUM_PLAYERS; k++) printf(" %.3f", totalUtilities[k]);
  }
*/

}


void preProposalProcess(int currentNumPlayers, int player, int noPropPlayer) {
//  globalCounter++;
//  if(globalCounter >= 20) return;

  int tempPlayer = 0;
  int numOptions = 0;

  Proposal* firstProposal = 0;
  Proposal* currentProposal = 0;

  for(int i=1; i<=currentNumPlayers; i++) {
    tempPlayer = currentOrder[0][i];
    if(((tempPlayer <= NUM_MEN && player > NUM_MEN)||(tempPlayer > NUM_MEN 
         && player <= NUM_MEN)) && tempPlayer != noPropPlayer) {
      if(numOptions == 0){
        numOptions++;
        firstProposal = new Proposal(tempPlayer, U[player][tempPlayer], i, NULL);
      }
      else {
        numOptions++;
        currentProposal = firstProposal;
        if(U[player][tempPlayer] > firstProposal->util) 
          firstProposal = new Proposal(tempPlayer, U[player][tempPlayer], 
				i, currentProposal);
        else {
          while(currentProposal->next != 0 && U[player][tempPlayer] < (currentProposal->next)->util)
            currentProposal = currentProposal->next; 
          Proposal* temp = currentProposal->next;
          currentProposal->next = new Proposal(tempPlayer, U[player][tempPlayer], i, temp);
        }
      }
    }
  } 
  if(numOptions > 0) {
    int numProposalsMade = 0;
    int proposalAccepted = 0;
    currentProposal = firstProposal;
    proposalAccepted = propose(player, currentProposal, currentNumPlayers);
    numProposalsMade++;

    while(currentProposal != 0 && currentProposal->next!=0 && 
	numProposalsMade < numOptions && proposalAccepted==0) {
      currentProposal = currentProposal->next;
      proposalAccepted = propose(player, currentProposal, currentNumPlayers);
      numProposalsMade++;
    }
  
    //free memory when done
    Proposal* temp;
    currentProposal = firstProposal;
    while(currentProposal !=0 && currentProposal->next != 0) {
      temp = currentProposal;
      currentProposal = currentProposal->next;
      delete temp;
    }
    delete currentProposal;
  }
}


int propose(int player1, Proposal* proposal, int currentNumPlayers) {
  int player2 = proposal->player;
  int index2 = proposal->index;
//  printf("\n\n\nEntered propose: %d proposing to %d", player1, player2);
//  printf("\n player %d's utilities: ", player2);
//  for(int k=1; k<=NUM_PLAYERS; k++) printf(" %d", U[player2][k]);

  int answer = REJECT;
  int currentSpouse = currentOrder[1][index2];
  //printf("\ncurrentSpouse = %d\t\t", currentSpouse);

  int counter = 0;
  while(currentOrder[0][counter] != player1) { counter++; }
  int index1 = counter;

  if(U[player2][player1] > U[player2][currentSpouse]) {
    answer = ACCEPT;
    //printf("\taccept");
    currentOrder[1][index2] = player1;
    currentOrder[1][index1] = player2;
    //printCurrentOrder();
    if(currentSpouse != 0) {
      int i = 0;
      while(currentOrder[0][i]!=currentSpouse) { i++; }
      int currentSpouseIndex = i;
      currentOrder[1][currentSpouseIndex] = 0;    //set current spouse to single
      preProposalProcess(currentNumPlayers, currentSpouse, player2);
    }
  }
  //else printf("\treject");
  return answer;
}

////////////////////////////////////////////////////////////////////////////////

void determineFeasibility() {
  int bigPartySize = 0;
  int smallPartySize = 0;
  int men_or_women = 0;

  if(NUM_WOMEN > NUM_MEN) {				//must permute the party with more players to avoid 0 issue
    men_or_women = WOMEN;
    bigPartySize = NUM_WOMEN;
    smallPartySize = NUM_MEN;
  }
  else {
    men_or_women = MEN;
    bigPartySize = NUM_MEN;
    smallPartySize = NUM_WOMEN;
  }

  findAllMatchings(1, bigPartySize, men_or_women);
//  printAllMatchingsAndUtils(men_or_women, bigPartySize);

  int feasible = 0;
  int currentUtilityVector[NUM_PLAYERS+1];
  double avgStableUtil[NUM_PLAYERS+1];
  int numStableMatchings = 0;
  for(int k=0; k<=NUM_PLAYERS; k++) avgStableUtil[k] = 0;

  for(int currentMatching=0; currentMatching<numMatchings; currentMatching++) {
    if(men_or_women == WOMEN) {				//Indices correspond to men
      for(int r=1; r<=NUM_WOMEN; r++) {
        if(r<=NUM_MEN)
          currentUtilityVector[r] = allMatchingsAndUtils[currentMatching][r][1];
        int partner = allMatchingsAndUtils[currentMatching][r][0];
        currentUtilityVector[partner+NUM_MEN] = allMatchingsAndUtils[currentMatching][r][2];
      }
    }else {						//Indices correspond to women
      for(int r=1; r<=NUM_MEN; r++) {
        if(r<=NUM_WOMEN)
          currentUtilityVector[r+NUM_MEN] = allMatchingsAndUtils[currentMatching][r][1];  
        int partner = allMatchingsAndUtils[currentMatching][r][0];
        currentUtilityVector[partner] = allMatchingsAndUtils[currentMatching][r][2];
      }
    }
    int currentVectorFeasible = 1;
    printf("\n");
    for(int i=1; i<=NUM_PLAYERS; i++) {
      printf(" %d", currentUtilityVector[i]);
      if(totalUtilities[i]/globalCounter > currentUtilityVector[i])
        currentVectorFeasible = 0;
    }
    if(currentVectorFeasible)  feasible = 1;
    if(determineStability(currentUtilityVector)) {
      numStableMatchings ++;
      printf("\tStable");
      for(int k=1; k<=NUM_PLAYERS; k++) {
        avgStableUtil[k] += currentUtilityVector[k];
      }
    }
  } 

  if(feasible)  printf("\nFeasible");
  else          printf("\nNot Feasible");

  printf("\nStable Average: ");
  for(int k=1; k<=NUM_PLAYERS; k++) {
    avgStableUtil[k] /= numStableMatchings;
    printf(" %.2f", avgStableUtil[k]);
  }
}


void findAllMatchings (int currentSpot, int stopSpot, int men_or_women) {
  int nonused = 1;
  int adjustment1 = 0;
  int adjustment2 = 0;
  if(men_or_women == MEN)			// more men means indices correspond to women #'s
    adjustment1 = NUM_MEN;
  else						// more women means indices correspond to men #'s
    adjustment2 = NUM_MEN;

  for(int i=1; i<= stopSpot; i++) {
    nonused = 1;
    for(int j=1; j < currentSpot; j++) {
      if(permArray[j] == i)			//      if(currentOrder[0][j] == i)
        nonused = 0;
    }
    if(nonused) {
      permArray[currentSpot] = i;
      if(currentSpot < stopSpot)
        findAllMatchings(currentSpot+1, stopSpot, men_or_women);
      else {
        for(int k=0; k<=stopSpot; k++){
          allMatchingsAndUtils[numMatchings][k][0] = permArray[k];
          if(k > NUM_MEN || k > NUM_WOMEN) {
            allMatchingsAndUtils[numMatchings][k][1] = 0;
            allMatchingsAndUtils[numMatchings][k][2] = 0;
          }else { 
            allMatchingsAndUtils[numMatchings][k][1] = U[k+adjustment1][permArray[k]+adjustment2];
            allMatchingsAndUtils[numMatchings][k][2] = U[permArray[k]+adjustment2][k+adjustment1];
          }
        }
        numMatchings++;
      }
    }
  }
}


   //int allMatchingsAndUtils[NUM_POSSIBLE_MATCHINGS][NUM_PLAYERS+1][3];
   // "[i][j][0] is partner of man/woman j in matching i
   // "[i][j][1] is utility of man/woman j in matching i
   // "[i][j][2] is utility of man/woman j's partner in matching i

void printAllMatchingsAndUtils(int men_or_women, int numPairs) {
  int adjustment1 = 0;
  int adjustment2 = 0;

  printf("\n\n\n\n");

  if(men_or_women == MEN)
    adjustment1 = NUM_MEN;
  else
    adjustment2 = NUM_MEN;

  for(int i=0; i<numMatchings; i++) {
    printf("\n  %d: ", i+1);
    for(int j=1; j<=numPairs; j++) {
      printf("\t%d+%d", j+adjustment1, allMatchingsAndUtils[i][j][0]+adjustment2);
//      printf(" u %d %d", allMatchingsAndUtils[i][j][1], allMatchingsAndUtils[i][j][2]);
    }
  }
}


int determineStability(int currentUtilityVector[]) {
  int stable = 1;

  for(int m=1; m<=NUM_MEN; m++) {
    for(int w=1+NUM_MEN; w<=NUM_WOMEN+NUM_MEN; w++) {
      if(U[m][w] > currentUtilityVector[m] && U[w][m] > currentUtilityVector[w])
        stable = 0;
    }
  }
  return stable;
}