API tools faq
paste
Advertisement
algorithmuscanorj

A207324: Sequencer program based on the SJT algorithm (C)

algorithmuscanorj
Dec 28th, 2012
345
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 14.62 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  * SeaDragon 0.91 - A sequencer program for A207324 at oeis.org
  3.  *
  4.  * 2012 Sept. R.J. Cano <aallggoorriitthhmmuuss@gmail.com>
  5.  *
  6.  * This program was devised and written for documentation purposes and is
  7.  * subject to the terms of use of the On Line Encyclopedia Of Integer Sequences.
  8.  *
  9.  *
  10.  * Changes:
  11.  *
  12.  *  This update has no leaks at all, and  runs a litte bit faster than older versions.
  13.  *
  14.  * About A055998 and the memory leaks present in older versions of this code:
  15.  *
  16.  * The counting of memory blocks leaked by missed calls to free(), a bug already fixed for
  17.  * the present version of this program, behaved as an arithmetical progession documented
  18.  * in oeis.org as the A055998 sequence adding 2 in each one of its terms. Such +2 addition
  19.  * was caused by an implementation mistake of the author. The actual counting is the shown
  20.  * by A055998. Also, the leaks were caused by a forgotten "memory release instruction",
  21.  * omited by the author when translating his pseudocode interpretation of the SJT Algorithm
  22.  * into a C program. There is no design errors neither in the SJT Algorithm nor in the
  23.  * operational interpretation made of it.
  24.  *
  25.  * Hints:
  26.  *
  27.  *  For authors and contributors about C programs:
  28.  *
  29.  *      It is suggested when compiling C programs verify if it's written in an
  30.  *      acceptable way using a command like: "gcc -O2 -W -Wall my_oeis_program.c"
  31.  *
  32.  *  (Thanks to: Joerg Arndt)
  33.  *
  34.  *
  35.  */
  36.  
  37. #include <stdio.h>
  38. #include <stdlib.h>
  39.  
  40. /*---------> non-standard datatype definitions <-----------------------------------------------------------*/
  41.  
  42. typedef struct matrix_linear_stack {
  43.  
  44.   long integer_value;
  45.   struct matrix_linear_stack *arrow;
  46.  
  47. } matrix_linear_stack;
  48.  
  49.  
  50. /*---------> non-standard constant values definition <------------------------------------------------------*/
  51.  
  52.  const long __mode_ZERO = 0;
  53.  const long __mode_EQUAL = 1;
  54.  const long __mode_DETERMINANT = 2;
  55.  const long __TOKEN_TEMPLATE   = 0;
  56.  const long __UNIT    = 1;
  57.  long generator_settings = 0;
  58.  long __config_generator[3][2];
  59.  
  60. /*---------> Suitable globals <-----------------------------------------------------------------------------*/
  61.  
  62. matrix_linear_stack *__the_ring_stckPointerReference_HEAD, *__the_ring_stckPointerReference_TAIL;
  63.  
  64. // About the ring:
  65. // Warning: After calling close__the_ring() a first time, don't call it again before a call to open_the_ring() of course
  66. // for the same parameter list (Else it would have possible harmful and unpredictible consequences).
  67.  
  68. /*---------> non-standards called by main(); <-----------------------------------------------------*/
  69.  
  70. void configure_modes(void);
  71.  
  72. void runSequencer(int, long);
  73.  
  74. /*---------> non-standards called by others; <-----------------------------------------------------*/
  75.  
  76. void finalizer_matrix(matrix_linear_stack **, matrix_linear_stack**);
  77.  
  78. void print_matrix(matrix_linear_stack **);
  79.  
  80. void apply_SteinhausJohnsonTrotterAlgorithm(matrix_linear_stack**, matrix_linear_stack**, long);
  81.  
  82. void mode_matrix_waterfall(void);
  83.  
  84. matrix_linear_stack* generate_square_matrix(matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**, long);
  85.  
  86. void initializer_matrix(matrix_linear_stack **, matrix_linear_stack**);
  87.  
  88. matrix_linear_stack* extract_first_nodes(matrix_linear_stack**, matrix_linear_stack**, long);
  89.  
  90. void concat_matrices_node_by_node(matrix_linear_stack**, matrix_linear_stack**, matrix_linear_stack**);
  91.  
  92. /*---------> additional non-standards (some of them called by more than one function); <-----------------------------------------------------*/
  93.  
  94. long only_initialized(matrix_linear_stack**);
  95.  
  96. long absolute_value(long);
  97.  
  98. matrix_linear_stack* insert_new_node(long, matrix_linear_stack**);
  99.  
  100. void close__the_ring(matrix_linear_stack**, matrix_linear_stack**);
  101.  
  102. void open_the_ring(matrix_linear_stack**, matrix_linear_stack**);
  103.  
  104. long LeibnitzLaplaceSignature(long);
  105.  
  106. /*------------------------------------------------------------------------------------------------------------------------------*/
  107.  
  108. int main(void) {
  109.  
  110.   int j, _OScurrentExecutionFeedbackCode = EXIT_SUCCESS;
  111.   long N;
  112.  
  113.   configure_modes(); // Don't change this, it is for initialization.
  114.  
  115.   printf("%s%s","\n\nDemonstration program: ", "\n\n\tShould be run the sequencer only for a particular SJT-array? (1=yes, 0=No) ");  
  116.   scanf("%i", &j);
  117.   getchar();  
  118.   printf("%s","\n\n\tWhich is the upper size? (try first 1-11 on 32-bit machines): ");
  119.   scanf("%li", &N);
  120.   getchar();
  121.  
  122.   runSequencer(j, N);
  123.  
  124.   return _OScurrentExecutionFeedbackCode;
  125.  
  126. }
  127.  
  128. /*------------------------------------------------------------------------------------------------------------------------------*/
  129.  
  130. void configure_modes(void) {
  131.  
  132.   __config_generator[__mode_ZERO][__TOKEN_TEMPLATE] = 0;
  133.   __config_generator[__mode_ZERO][__UNIT]  = 0;
  134.  
  135.   __config_generator[__mode_EQUAL][__TOKEN_TEMPLATE] = 0;
  136.   __config_generator[__mode_EQUAL][__UNIT]  = 1;
  137.  
  138.   __config_generator[__mode_DETERMINANT][__TOKEN_TEMPLATE] = 1;
  139.   __config_generator[__mode_DETERMINANT][__UNIT]  = 0;
  140.  
  141. }
  142.  
  143. /*------------------------------------------------------------------------------------------------------------------------------*/
  144.  
  145. void runSequencer(int just_for_the_Nth_array, long N) {
  146.  
  147.   long k;
  148.  
  149.   matrix_linear_stack *J0_head, *J0_tail;
  150.  
  151.   for (k=(just_for_the_Nth_array ? N : 1);k<=N;k++) {
  152.     apply_SteinhausJohnsonTrotterAlgorithm(&J0_head, &J0_tail, k);
  153.     print_matrix(&J0_head);
  154.     finalizer_matrix(&J0_head, &J0_tail);
  155.   }
  156.  
  157.   printf("\n\n\tSequencer execution completed successfully.\n");    
  158.  
  159. }
  160.  
  161. /*------------------------------------------------------------------------------------------------------------------------------*/
  162.  
  163. void finalizer_matrix(matrix_linear_stack **stckPointerReference_HEAD, matrix_linear_stack **stckPointerReference_TAIL) {
  164.  
  165.   while (*stckPointerReference_HEAD != NULL) {
  166.  
  167.     (*stckPointerReference_TAIL) = (*stckPointerReference_HEAD);
  168.    
  169.     (*stckPointerReference_HEAD) = (*stckPointerReference_HEAD)->arrow;
  170.    
  171.     free( *stckPointerReference_TAIL );
  172.  
  173.   }
  174.  
  175.     (*stckPointerReference_TAIL) = NULL;
  176.  
  177. }
  178.  
  179. /*------------------------------------------------------------------------------------------------------------------------------*/
  180.  
  181. void print_matrix(matrix_linear_stack **stckPointerReference_HEAD) {
  182.  
  183.   matrix_linear_stack* focus= *stckPointerReference_HEAD;
  184.  
  185.   if ( NULL == focus ) {
  186.  
  187.     printf(" Not initialized! ");
  188.  
  189.   } else {
  190.  
  191.     if ( -1 == (focus->integer_value) ) {
  192.  
  193.       focus = (*stckPointerReference_HEAD)->arrow;
  194.  
  195.       if ( NULL == focus ) {
  196.  
  197.     printf(" initialized but empty. ");
  198.  
  199.       } else {;}
  200.  
  201.     } else {
  202.  
  203.     }
  204.  
  205.     while ( NULL != focus ) {
  206.  
  207.       printf("\n%li", (focus->integer_value) );
  208.  
  209.       focus = focus->arrow;
  210.     }
  211.  
  212.   }
  213.  
  214. }
  215.  
  216. /*------------------------------------------------------------------------------------------------------------------------------*/
  217.  
  218. void apply_SteinhausJohnsonTrotterAlgorithm(matrix_linear_stack **J_head, matrix_linear_stack **J_tail, long _SIZE) {
  219.  
  220.   matrix_linear_stack *JJ_head;
  221.   matrix_linear_stack *JJ_tail;
  222.   matrix_linear_stack *P_head;
  223.   matrix_linear_stack *P_tail;
  224.   matrix_linear_stack *Q_head;
  225.   matrix_linear_stack *Q_tail;
  226.  
  227.   long diagonal;
  228.  
  229.   long _CASE = 1;
  230.  
  231.   mode_matrix_waterfall();
  232.  
  233.   initializer_matrix(J_head, J_tail);
  234.   insert_new_node(1, J_tail);
  235.  
  236.   while (_CASE < _SIZE) {
  237.  
  238.     _CASE++;
  239.     diagonal = -1;
  240.     initializer_matrix(&JJ_head, &JJ_tail);
  241.  
  242.     while ( !only_initialized(J_head) ) {
  243.  
  244.       P_head = extract_first_nodes(J_head, &P_tail, (_CASE-1)) ;
  245.       generate_square_matrix(&P_head, &P_tail, &Q_head, &Q_tail, _CASE*diagonal);
  246.       concat_matrices_node_by_node(&JJ_tail, &Q_head, &Q_tail);
  247.       finalizer_matrix(&P_head, &P_tail);
  248.  
  249.       diagonal *= -1;
  250.  
  251.     }
  252.  
  253.     finalizer_matrix(J_head, J_tail);
  254.     *J_head = JJ_head;
  255.     *J_tail   = JJ_tail;
  256.     JJ_head = NULL;
  257.     JJ_tail   = NULL;
  258.  
  259.   }
  260.  
  261. }
  262.  
  263. /*------------------------------------------------------------------------------------------------------------------------------*/
  264.  
  265. void  mode_matrix_waterfall(void) {
  266.  
  267.   generator_settings = __mode_DETERMINANT;
  268.  
  269. }
  270.  
  271. /*------------------------------------------------------------------------------------------------------------------------------*/
  272.  
  273. matrix_linear_stack* generate_square_matrix(matrix_linear_stack **baseRef_head, matrix_linear_stack **baseRef_tail, matrix_linear_stack **ref_answer_head, matrix_linear_stack **ref_answer_tail, long TOKEN_TEMPLATE) {
  274.  
  275.   long counting_L = 1;
  276.   long counting_X = 1;
  277.   long counting_Y = 1;
  278.   long matrix_size = absolute_value(TOKEN_TEMPLATE);
  279.   long newValuetobeIncluded;
  280.  
  281.   matrix_linear_stack* BASE_head = *baseRef_head;
  282.   matrix_linear_stack* BASE_tail = *baseRef_tail;
  283.  
  284.   close__the_ring(&BASE_head, &BASE_tail);
  285.  
  286.   initializer_matrix(ref_answer_head, ref_answer_tail);
  287.  
  288.   matrix_size = absolute_value(TOKEN_TEMPLATE);
  289.  
  290.   while (counting_L <= (matrix_size*matrix_size)) {
  291.  
  292.     if (BASE_head->integer_value == -1) { BASE_head = BASE_head->arrow; }
  293.  
  294.     newValuetobeIncluded = (TOKEN_TEMPLATE < 0) ? ( ( counting_X + counting_Y == (matrix_size+1) ) ? (matrix_size*__config_generator[generator_settings][__TOKEN_TEMPLATE] + __config_generator[generator_settings][__UNIT]) : (0) ) : ( (counting_X - counting_Y == 0) ? (matrix_size*__config_generator[generator_settings][__TOKEN_TEMPLATE] + __config_generator[generator_settings][__UNIT]) : (0) );
  295.  
  296.     if ( ( 0 == newValuetobeIncluded ) && ( __mode_ZERO != generator_settings) ) {
  297.  
  298.       newValuetobeIncluded+= (BASE_head->integer_value);
  299.       BASE_head = BASE_head->arrow;
  300.  
  301.     }
  302.  
  303.     insert_new_node(newValuetobeIncluded, ref_answer_tail);
  304.  
  305.     counting_L++;
  306.     counting_X++;
  307.     if (counting_X > matrix_size) {
  308.       counting_X = 1;
  309.       counting_Y++;
  310.     }
  311.   }
  312.  
  313.   open_the_ring(&BASE_head, &BASE_tail);
  314.  
  315.   return (*ref_answer_head);
  316. }
  317.  
  318. /*----------------------------------------------------------------------------------------------------------------------(OJO)---*/
  319.  
  320. void initializer_matrix(matrix_linear_stack **stckPointerReference_HEAD, matrix_linear_stack **stckPointerReference_TAIL) {
  321.  
  322.   (*stckPointerReference_HEAD) = NULL;
  323.   (*stckPointerReference_TAIL) = insert_new_node( -1, stckPointerReference_HEAD );
  324.  
  325. }
  326.  
  327. /*------------------------------------------------------------------------------------------------------------------------------*/
  328.  
  329. matrix_linear_stack* extract_first_nodes(matrix_linear_stack** refSource, matrix_linear_stack** refRemainderTail, long extractions) {
  330.  
  331.   matrix_linear_stack* newRefSource= *refSource;
  332.   matrix_linear_stack* answer= (*refSource)->arrow;
  333.   matrix_linear_stack* cursor= (*refSource);
  334.   long steps= (0 == extractions) ? 1 : extractions;
  335.   long counter=0;
  336.   while (counter < steps) {
  337.     cursor= cursor->arrow;
  338.     counter++;
  339.   }
  340.   newRefSource->arrow= cursor->arrow;
  341.   cursor->arrow= NULL;
  342.   (*refRemainderTail)= cursor;
  343.   *refSource = newRefSource;
  344.  
  345.   return answer;
  346.  
  347. }
  348.  
  349. /*------------------------------------------------------------------------------------------------------------------------------*/
  350.  
  351. void concat_matrices_node_by_node(matrix_linear_stack **operand_left_tail, matrix_linear_stack **operand_right_head, matrix_linear_stack **operand_right_tail) {
  352.  
  353.   matrix_linear_stack *slayer = *operand_right_head;
  354.   *operand_right_head = NULL;
  355.   (*operand_left_tail)->arrow = slayer->arrow;
  356.   slayer->arrow               = NULL;
  357.   free(slayer);
  358.   *operand_left_tail          = *operand_right_tail;
  359.   *operand_right_tail         = NULL;
  360.  
  361. }
  362.  
  363. /*------------------------------------------------------------------------------------------------------------------------------*/
  364.  
  365. long  only_initialized(matrix_linear_stack** stckPointerReference_HEAD) {
  366.  
  367.  
  368.  
  369.   if ( 0 != ( NULL != stckPointerReference_HEAD ) ) {
  370.     if ( 0 != ( NULL != *stckPointerReference_HEAD ) ) {
  371.       if ( 0 != ( NULL == (*stckPointerReference_HEAD)->arrow ) ) {
  372.     if ( -1 == (*stckPointerReference_HEAD)->integer_value ) {
  373.       return 1;
  374.     }
  375.       }
  376.     }
  377.   }
  378.  
  379.   return 0;
  380.  
  381. }
  382.  
  383. /*------------------------------------------------------------------------------------------------------------------------------*/
  384.  
  385. long absolute_value(long argument) {
  386.  
  387.   return ( argument * LeibnitzLaplaceSignature(argument) );
  388.  
  389. }
  390.  
  391. /*------------------------------------------------------------------------------------------------------------------------------*/
  392.  
  393. matrix_linear_stack* insert_new_node(long value_assigned, matrix_linear_stack **stckPointerReference_TAIL) {
  394.  
  395.   matrix_linear_stack *focus;
  396.   matrix_linear_stack *inserto = (matrix_linear_stack *)( malloc( sizeof( matrix_linear_stack ) ) );
  397.  
  398.   matrix_linear_stack *answer_ref = inserto;
  399.   inserto->integer_value  = value_assigned;
  400.   inserto->arrow = NULL;
  401.  
  402.   if (( NULL == (*stckPointerReference_TAIL) ) && (-1 == value_assigned)) {
  403.  
  404.     (*stckPointerReference_TAIL) = inserto;
  405.  
  406.   } else if ( NULL != (*stckPointerReference_TAIL) ) {
  407.  
  408.       focus = (*stckPointerReference_TAIL);
  409.       while ( NULL != focus->arrow ) { focus = focus->arrow; }
  410.       focus->arrow = inserto;
  411.       if ( focus == (*stckPointerReference_TAIL) ) { (*stckPointerReference_TAIL) = inserto; }
  412.  
  413.   }
  414.  
  415.   return answer_ref;
  416. }
  417.  
  418. /*------------------------------------------------------------------------------------------------------------------------------*/
  419.  
  420. void close__the_ring(matrix_linear_stack** stckPointerReference_HEAD, matrix_linear_stack** stckPointerReference_TAIL) {
  421.  
  422.   __the_ring_stckPointerReference_HEAD = *stckPointerReference_HEAD;
  423.   __the_ring_stckPointerReference_TAIL   = *stckPointerReference_TAIL;
  424.   (*stckPointerReference_TAIL)->arrow = *stckPointerReference_HEAD;
  425.  
  426. }
  427.  
  428. /*------------------------------------------------------------------------------------------------------------------------------*/
  429.  
  430. void open_the_ring(matrix_linear_stack** stckPointerReference_HEAD, matrix_linear_stack** stckPointerReference_TAIL) {
  431.  
  432.   (*stckPointerReference_HEAD)       = __the_ring_stckPointerReference_HEAD;
  433.   (*stckPointerReference_TAIL)         = __the_ring_stckPointerReference_TAIL;
  434.   (*stckPointerReference_TAIL)->arrow = NULL;
  435.  
  436. }
  437.  
  438. /*------------------------------------------------------------------------------------------------------------------------------*/
  439.  
  440. long LeibnitzLaplaceSignature(long argument) {
  441.  
  442.   long answer;
  443.  
  444.   answer = (argument < 0) ? (-1) : (1) ;
  445.  
  446.   return answer;
  447.  
  448. }
  449.  
  450. /*
  451.  *
  452.  *      << If people do not believe that mathematics is simple, it is only because
  453.  *          they do not realize how complicated life is. >>
  454.  *
  455.  *                  --John von Neumann
  456.  *
  457.  */
  458.  
  459. // The end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!