fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <time.h>
  5. #include <string.h>
  6.  
  7. /* ==================== Input Data ==================== */
  8.  
  9. #define TOTAL_ITEMS 20
  10. #define TOTAL_MODULES 5
  11. #define MH_ITER 1000
  12. #define MH_ALPHA 1.0
  13.  
  14. // Table 1: Mean Information for Items Across Modules (H22)
  15. double mean_info[TOTAL_ITEMS][TOTAL_MODULES] = {
  16.     {0.0551342205, 1.1229549861, 1.0746550402, 0.273644702,  0.3789612651}, // Item_1
  17.     {1.5159051325, 0.9547912017, 0.6838172809, 0.729615083,  1.3183586369}, // Item_2
  18.     {0.4263425097, 0.4009858961, 0.1942834514, 1.9686943023,  1.9678124012}, // Item_3
  19.     {1.3914179336, 1.9653292177, 1.6987745520, 1.276778025,   0.0037878142}, // Item_4
  20.     {0.3729225141, 1.4446974322, 1.1962628849, 0.2984828125,  0.8939753608}, // Item_5
  21.     {0.0912230066, 1.3080023215, 1.4472607197, 0.0348708527,  0.6183642983}, // Item_6
  22.     {0.7302597184, 1.1067225309, 1.7269795015, 1.3609462492,  0.8742362978}, // Item_7
  23.     {0.7628315771, 0.90299008,   0.5567556787, 0.0081749232,  0.6736855884}, // Item_8
  24.     {0.5476417858, 0.7755998513, 1.3814817402, 1.5209261049,  1.1303703147}, // Item_9
  25.     {0.9169885837, 1.430428321,  0.8864384596, 0.9514936865,  1.6372995656}, // Item_10
  26.     {0.7191456454, 1.2072812952, 0.4427503883, 0.2653594026,  0.7121747779}, // Item_11
  27.     {1.8255623579, 1.5235340218, 0.2311946922, 1.7890632707,  1.3132771454}, // Item_12
  28.     {0.0592750302, 0.4910661918, 1.5775046116, 1.8711764617,  0.5687820357}, // Item_13
  29.     {1.7727101115, 1.9907456539, 0.5861100047, 0.75383928,    0.597872715},  // Item_14
  30.     {1.5786721054, 0.7445353908, 1.2787411003, 0.8351749131,  1.8470229823}, // Item_15
  31.     {1.0837545246, 0.6862612348, 1.2791052731, 0.8805288146,  0.3869853732}, // Item_16
  32.     {1.565522531,  0.2279829192, 0.5790772517, 1.1613239124,  1.9721290898}, // Item_17
  33.     {1.4484547731, 1.7876939061, 1.5256539653, 0.7668565032,  0.2002832731}, // Item_18
  34.     {0.4790251292, 1.33859911,   1.5265114061, 1.3049658258,  1.4785322957}, // Item_19
  35.     {0.8885746957, 1.21464705,   0.9087569579, 1.9485661844,  0.267142314}   // Item_20
  36. };
  37.  
  38. // Table 2: Item Attributes (F23)
  39. int item_attr[TOTAL_ITEMS] = {
  40.     2, 2, 2, 1, 1, 4, 3, 3, 1, 5,
  41.     3, 1, 4, 5, 4, 5, 4, 2, 1, 3
  42. };
  43.  
  44. // Array to mark whether an item has been used (0: available, 1: used)
  45. int used[TOTAL_ITEMS] = {0};
  46.  
  47. /* Blueprint from Table 3: Module-Item Assignments (C19)
  48.    Each module’s required attribute IDs are listed in blueprint order.
  49. */
  50. typedef struct {
  51.     char name[3];
  52.     int stage;
  53.     int num_req;
  54.     int req[10];      // required attribute IDs (in blueprint order)
  55.     int assign[10];   // assigned item IDs (1-indexed; 0 if not filled)
  56. } Module;
  57.  
  58. Module modules[TOTAL_MODULES] = {
  59.     {"M1", 1, 3, {1, 3, 4}, {0,0,0}},
  60.     {"M2", 2, 4, {2, 3, 1, 4}, {0,0,0,0}},
  61.     {"M3", 2, 3, {3, 5, 2}, {0,0,0}},
  62.     {"M4", 3, 3, {2, 4, 3}, {0,0,0}},
  63.     {"M5", 3, 2, {1, 5}, {0,0}}
  64. };
  65.  
  66. /* ==================== MH Black-Box Code ====================
  67.    (Do NOT change any line of logic in this block.)
  68.    Global variables used:
  69.      g_nitems: number of candidate items (for current attribute)
  70.      g_nmod: number of modules (for current attribute)
  71.      g_info[][]: candidate matrix (rows: candidate items, columns: modules)
  72. */
  73. int g_nitems;   // candidate items count
  74. int g_nmod;     // number of modules for current attribute
  75. double g_info[100][100];
  76.  
  77. double runifC() {
  78.     return (double)rand() / (double)RAND_MAX;
  79. }
  80.  
  81. double sampleGumbel() {
  82.     double u = runifC();
  83.     if(u <= 0.0) u = 1e-10;
  84.     if(u >= 1.0) u = 1 - 1e-10;
  85.     return -log(-log(u));
  86. }
  87.  
  88. /* GsampleEq: Samples x integers (1-indexed) from numbrs[1..len] using Gumbel perturbation */
  89. void GsampleEq(const int *numbrs, int len, int x, int *out) {
  90.     typedef struct {
  91.         int val;
  92.         double g;
  93.     } Gpair;
  94.     Gpair arr[100];
  95.     double constant = log(1.0 / len);
  96.     for (int i = 1; i <= len; i++) {
  97.         double gumb = sampleGumbel() + constant;
  98.         arr[i].val = numbrs[i];
  99.         arr[i].g   = gumb;
  100.     }
  101.     // Bubble sort in descending order of g
  102.     for (int i = 1; i < len; i++) {
  103.         for (int j = i + 1; j <= len; j++) {
  104.             if (arr[j].g > arr[i].g) {
  105.                 Gpair tmp = arr[i];
  106.                 arr[i] = arr[j];
  107.                 arr[j] = tmp;
  108.             }
  109.         }
  110.     }
  111.     for (int i = 1; i <= x; i++) {
  112.         out[i] = arr[i].val;
  113.     }
  114. }
  115.  
  116. double pop_sd(const double *vals, int n) {
  117.     if(n <= 1) return 0.0;
  118.     double sum = 0.0;
  119.     for (int i = 1; i <= n; i++) {
  120.         sum += vals[i];
  121.     }
  122.     double mean = sum / n;
  123.     double sse = 0.0;
  124.     for (int i = 1; i <= n; i++) {
  125.         double diff = vals[i] - mean;
  126.         sse += diff * diff;
  127.     }
  128.     return sqrt(sse / n);
  129. }
  130.  
  131. /* MH optimizer function.
  132.    It uses global variables g_nitems, g_nmod, and matrix g_info.
  133.    The output bestSelect[1..g_nmod] gives the (1-indexed) candidate chosen for each module.
  134. */
  135. void mh(int iter, double alpha, int *bestSelect, double *bestObjValue, double *objTrace) {
  136.     int itemsArray[100], modsArray[100];
  137.     for (int i = 1; i <= g_nitems; i++) {
  138.         itemsArray[i] = i;
  139.     }
  140.     for (int j = 1; j <= g_nmod; j++) {
  141.         modsArray[j] = j;
  142.     }
  143.     int citems[100];
  144.     GsampleEq(itemsArray, g_nitems, g_nmod, citems);
  145.     double cvals[100];
  146.     double sumVals = 0.0;
  147.     for (int j = 1; j <= g_nmod; j++) {
  148.         int itemIndex = citems[j];
  149.         double val = g_info[itemIndex - 1][j - 1];
  150.         cvals[j] = val;
  151.         sumVals += val;
  152.     }
  153.     double cSD = pop_sd(cvals, g_nmod);
  154.     double cObj = sumVals - cSD;
  155.     for (int j = 1; j <= g_nmod; j++) {
  156.         bestSelect[j] = citems[j];
  157.     }
  158.     double bestObj = cObj;
  159.     for (int i = 1; i <= iter; i++) {
  160.         int nselect[100];
  161.         for (int j = 1; j <= g_nmod; j++) {
  162.             nselect[j] = citems[j];
  163.         }
  164.         int chosen[10];
  165.         GsampleEq(modsArray, g_nmod, 1, chosen);
  166.         int changemod = chosen[1];
  167.         int notChosen[100];
  168.         int ncCount = 0;
  169.         for (int k = 1; k <= g_nitems; k++) {
  170.             int inSel = 0;
  171.             for (int jj = 1; jj <= g_nmod; jj++) {
  172.                 if(nselect[jj] == k) { inSel = 1; break; }
  173.             }
  174.             if(!inSel) { ncCount++; notChosen[ncCount] = k; }
  175.         }
  176.         int newOne[10];
  177.         if(ncCount > 0) {
  178.             GsampleEq(notChosen, ncCount, 1, newOne);
  179.             int newItem = newOne[1];
  180.             nselect[changemod] = newItem;
  181.         }
  182.         double nvals[100];
  183.         double newSum = 0.0;
  184.         for (int j = 1; j <= g_nmod; j++) {
  185.             int it = nselect[j];
  186.             double val = g_info[it - 1][j - 1];
  187.             nvals[j] = val;
  188.             newSum += val;
  189.         }
  190.         double newSD = pop_sd(nvals, g_nmod);
  191.         double newObj = newSum - newSD;
  192.         if(newObj > cObj) {
  193.             for (int j = 1; j <= g_nmod; j++) {
  194.                 citems[j] = nselect[j];
  195.             }
  196.             cObj = newObj;
  197.         } else {
  198.             double aprob = exp(alpha * (newObj - cObj));
  199.             if(aprob > 1.0) aprob = 1.0;
  200.             double u = runifC();
  201.             if(u < aprob) {
  202.                 for (int j = 1; j <= g_nmod; j++) {
  203.                     citems[j] = nselect[j];
  204.                 }
  205.                 cObj = newObj;
  206.             }
  207.         }
  208.         if(cObj > bestObj) {
  209.             bestObj = cObj;
  210.             for (int j = 1; j <= g_nmod; j++) {
  211.                 bestSelect[j] = citems[j];
  212.             }
  213.         }
  214.         objTrace[i] = bestObj;
  215.     }
  216.     *bestObjValue = bestObj;
  217. }
  218.  
  219. /* ==================== Extended MST Logic ==================== */
  220.  
  221. /*
  222.    For a given attribute (attr), gather candidate items (from Table 2) that have that attribute and are not used.
  223.    Returns candidate count and fills array cand[] (with 1-indexed candidate positions).
  224. */
  225. int get_candidates(int attr, int cand[]) {
  226.     int count = 0;
  227.     for (int i = 0; i < TOTAL_ITEMS; i++) {
  228.         if(!used[i] && item_attr[i] == attr) {
  229.             cand[++count] = i;  // store candidate item (0-indexed) at position count
  230.         }
  231.     }
  232.     return count;
  233. }
  234.  
  235. /*
  236.    For a single module (mod, 0-indexed) and attribute, select the candidate with highest mean information.
  237. */
  238. int select_best_for_module(int mod, int attr, int cand[], int candCount) {
  239.     int best = -1;
  240.     double bestVal = -1e9;
  241.     for (int i = 1; i <= candCount; i++) {
  242.         int itemIndex = cand[i];
  243.         double val = mean_info[itemIndex][mod];
  244.         if(val > bestVal) {
  245.             bestVal = val;
  246.             best = itemIndex;
  247.         }
  248.     }
  249.     return best;
  250. }
  251.  
  252. /*
  253.    Process a given attribute for a set of modules (modList[]) in the same stage that require it.
  254.    If only one module requires the attribute, assign directly.
  255.    If more than one require it, then (to mimic the single–attribute MH call)
  256.    we sort the list of modules in natural (ascending) order before building the candidate matrix.
  257. */
  258. void process_attribute(int attr, int modList[], int count) {
  259.     int cand[100];
  260.     int candCount = get_candidates(attr, cand);
  261.     if(candCount == 0) {
  262.         printf("No available items for attribute %d\n", attr);
  263.         return;
  264.     }
  265.     if(count == 1) {
  266.         int mod = modList[0];
  267.         int bestItem = select_best_for_module(mod, attr, cand, candCount);
  268.         for (int i = 0; i < modules[mod].num_req; i++) {
  269.             if(modules[mod].req[i] == attr && modules[mod].assign[i] == 0) {
  270.                 modules[mod].assign[i] = bestItem + 1; // store 1-indexed
  271.                 used[bestItem] = 1;
  272.                 printf("Module %s: Assigned Item_%d for attribute %d (direct selection)\n",
  273.                        modules[mod].name, bestItem+1, attr);
  274.                 break;
  275.             }
  276.         }
  277.     } else {
  278.         // Build a copy of modList and sort it in ascending order (natural order).
  279.         int orderedMods[10];
  280.         for (int i = 0; i < count; i++) {
  281.             orderedMods[i] = modList[i];
  282.         }
  283.         for (int i = 0; i < count - 1; i++) {
  284.             for (int j = i+1; j < count; j++) {
  285.                 if(orderedMods[i] > orderedMods[j]) {
  286.                     int temp = orderedMods[i];
  287.                     orderedMods[i] = orderedMods[j];
  288.                     orderedMods[j] = temp;
  289.                 }
  290.             }
  291.         }
  292.         // Use the orderedMods for the MH candidate matrix.
  293.         g_nitems = candCount;
  294.         g_nmod = count;
  295.         for (int i = 1; i <= g_nitems; i++) {
  296.             for (int j = 0; j < g_nmod; j++) {
  297.                 int mod = orderedMods[j];  // natural order (e.g., for stage 2: M2 then M3)
  298.                 g_info[i-1][j] = mean_info[cand[i]][mod];
  299.             }
  300.         }
  301.         int bestSelect[100];
  302.         double bestObj;
  303.         double objTrace[MH_ITER+1];
  304.         mh(MH_ITER, MH_ALPHA, bestSelect, &bestObj, objTrace);
  305.         // Assign the chosen candidate for each module using the same orderedMods.
  306.         for (int j = 0; j < g_nmod; j++) {
  307.             int selCandIndex = bestSelect[j+1];  // 1-indexed into cand[]
  308.             int bestItem = cand[selCandIndex];
  309.             int mod = orderedMods[j];
  310.             for (int k = 0; k < modules[mod].num_req; k++) {
  311.                 if(modules[mod].req[k] == attr && modules[mod].assign[k] == 0) {
  312.                     modules[mod].assign[k] = bestItem + 1;
  313.                     used[bestItem] = 1;
  314.                     printf("Module %s: Assigned Item_%d for attribute %d (via MH)\n",
  315.                            modules[mod].name, bestItem+1, attr);
  316.                     break;
  317.                 }
  318.             }
  319.         }
  320.     }
  321. }
  322.  
  323. /*
  324.    Process a given stage.
  325.    Collect all modules in that stage (using the stage field), sort them in descending order
  326.    (so that direct selections obey the “last module first” rule), then for each attribute (1 to 5)
  327.    required by at least one module, call process_attribute.
  328. */
  329. void process_stage(int stage) {
  330.     int modList[10];
  331.     int modCount = 0;
  332.     for (int i = 0; i < TOTAL_MODULES; i++) {
  333.         if(modules[i].stage == stage) {
  334.             modList[modCount++] = i;
  335.         }
  336.     }
  337.     // Sort modList in descending order for direct selection.
  338.     for (int i = 0; i < modCount - 1; i++) {
  339.         for (int j = i+1; j < modCount; j++) {
  340.             if(modList[i] < modList[j]) {
  341.                 int temp = modList[i];
  342.                 modList[i] = modList[j];
  343.                 modList[j] = temp;
  344.             }
  345.         }
  346.     }
  347.     // For each attribute (1 to 5), find modules (from modList) that still need that attribute.
  348.     for (int attr = 1; attr <= 5; attr++) {
  349.         int reqMods[10];
  350.         int count = 0;
  351.         for (int i = 0; i < modCount; i++) {
  352.             int mod = modList[i];
  353.             for (int j = 0; j < modules[mod].num_req; j++) {
  354.                 if(modules[mod].req[j] == attr && modules[mod].assign[j] == 0) {
  355.                     reqMods[count++] = mod;
  356.                     break;
  357.                 }
  358.             }
  359.         }
  360.         if(count > 0) {
  361.             process_attribute(attr, reqMods, count);
  362.         }
  363.     }
  364. }
  365.  
  366. /* ==================== Main ==================== */
  367. int main() {
  368.     // Use a fixed seed for reproducibility.
  369.     srand(12345);
  370.  
  371.     printf("Starting MST Item Assignment...\n\n");
  372.  
  373.     // Process stages from last to first.
  374.     // Stage 3 (modules M4 and M5)
  375.     process_stage(3);
  376.     // Stage 2 (modules M2 and M3)
  377.     process_stage(2);
  378.     // Stage 1 (module M1)
  379.     process_stage(1);
  380.  
  381.     // Print final assignments.
  382.     printf("\nFinal Module Assignments:\n");
  383.     for (int i = 0; i < TOTAL_MODULES; i++) {
  384.         printf("%s (Stage %d): ", modules[i].name, modules[i].stage);
  385.         for (int j = 0; j < modules[i].num_req; j++) {
  386.             if(modules[i].assign[j] != 0)
  387.                 printf("Item_%d ", modules[i].assign[j]);
  388.             else
  389.                 printf("None ");
  390.         }
  391.         printf("\n");
  392.     }
  393.  
  394.     return 0;
  395. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Starting MST Item Assignment...

Module M5: Assigned Item_19 for attribute 1 (direct selection)
Module M4: Assigned Item_3 for attribute 2 (direct selection)
Module M4: Assigned Item_20 for attribute 3 (direct selection)
Module M4: Assigned Item_13 for attribute 4 (direct selection)
Module M5: Assigned Item_10 for attribute 5 (direct selection)
Module M2: Assigned Item_4 for attribute 1 (direct selection)
Module M2: Assigned Item_18 for attribute 2 (via MH)
Module M3: Assigned Item_1 for attribute 2 (via MH)
Module M2: Assigned Item_11 for attribute 3 (via MH)
Module M3: Assigned Item_7 for attribute 3 (via MH)
Module M2: Assigned Item_6 for attribute 4 (direct selection)
Module M3: Assigned Item_16 for attribute 5 (direct selection)
Module M1: Assigned Item_12 for attribute 1 (direct selection)
Module M1: Assigned Item_8 for attribute 3 (direct selection)
Module M1: Assigned Item_15 for attribute 4 (direct selection)

Final Module Assignments:
M1 (Stage 1): Item_12 Item_8 Item_15 
M2 (Stage 2): Item_18 Item_11 Item_4 Item_6 
M3 (Stage 2): Item_7 Item_16 Item_1 
M4 (Stage 3): Item_3 Item_13 Item_20 
M5 (Stage 3): Item_19 Item_10
https://ideone.com/YwUO9u
language:
C (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!