API tools faq
paste
Advertisement
m4ly

Jakies permutacje

m4ly
Jan 2nd, 2016
114
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 10.87 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. Jack Real Butcher‎  do  SysOps / DevOps Polska
  3. 20 godz. ·
  4.  
  5. Siemka ;] szybkie zadanko moze ktos mi pomoze. Ja nigdy nie bylem jakis super dobry z programowania. Chce napisac skrypta oczywiscie bashowego lub jakis kod w C ktory by mi robil to:
  6.  
  7. Parametr wejsciowy: cyfra
  8. wyjściowo plik który będzie miał zawartość zależną od cyfry z wejściowego czyli:
  9. 1. Dla 1 :
  10. (A+B)
  11. 2. Dla 2 :
  12. (A+B)
  13. (A+C)
  14. (B+C)
  15. ((A+B)+C)
  16. ((A+C)+B)
  17. 3. Dla 3 :
  18. (A+B)
  19. (A+C)
  20. (A+D)
  21. (B+C)
  22. (B+D)
  23. (C+D)
  24. ((A+B)+C)
  25. ((A+B)+D)
  26. ((A+C)+D)
  27. ((B+C)+D)
  28. ((A+C)+B)
  29. ((A+D)+B)
  30. ((A+D)+C)
  31. ((B+D)+C)
  32. ((B+C)+A)
  33. ((B+D)+A)
  34. ((C+D)+A)
  35. ((C+D)+B)
  36. (((A+B)+C)+D)
  37. (((A+B)+D)+C)
  38. (((A+C)+B)+D)
  39. (((A+C)+D)+B)
  40. (((A+D)+B)+C)
  41. (((A+D)+C)+B)
  42. (((B+C)+A)+D)
  43. (((B+C)+D)+A)
  44. (((B+D)+A)+C)
  45. (((B+D)+C)+A)
  46. (((C+D)+A)+B)
  47. (((C+D)+B)+A)
  48. ((A+B)+(C+D))
  49. ((A+C)+(B+D))
  50. ((A+D)+(B+C))
  51.  
  52. Itp. pewnie da się to prostą listą ogarnąć
  53. Emotikon smile
  54. pomożecie?
  55. Emotikon smile
  56.  
  57. Dziękuję
  58. */
  59.  
  60.  
  61.  
  62. /*
  63. Author: Dawid Mocek <[email protected]>
  64. 2016-01-02
  65.  
  66. Nie jest to ani seksi ani zoptymalizowane ale działa... chyba :-)
  67. */
  68. #include <stdlib.h>
  69. #include <string.h>
  70. #include <stdio.h>
  71.  
  72. #define AB_SIZE 23
  73. static const char ab[] = { 'A', 'B', 'C', 'D', 'E',
  74.                            'F', 'G', 'H', 'I', 'J',
  75.                            'K', 'L', 'M', 'N', 'O',
  76.                            'P', 'R', 'S', 'T', 'U',
  77.                            'W', 'Y', 'Z' };
  78.  
  79. static const char chars[] = { '(', ')', '+' };
  80.  
  81.  
  82. struct node_s {
  83.     char *record;
  84.     size_t record_size;
  85.     struct node_s *next;
  86. };
  87.  
  88.  
  89. /*
  90. * Obsluga erroru alokacji w linedlist
  91. *
  92. */
  93. void error_alloc_node(struct node_s **node, const char *msg) {
  94.     free(*node);
  95.     fprintf(stderr, "struct node* memory allocation error: %s", msg);
  96.     *node = NULL;
  97.     exit(EXIT_FAILURE);
  98. }
  99.  
  100. /*
  101.  * Dodaje noda na początek listy jednokierunkowej
  102.  * Bez sortowania
  103.  * */
  104. void lpush_front(struct node_s **head, char *rec, size_t rec_size) {
  105.  
  106.     // Jeśli początek jest null to glowa = nowy element
  107.     if (*head == NULL) {
  108.         *head = (struct node_s *)malloc(sizeof(struct node_s));
  109.         if (!*head) error_alloc_node(head, "head, insert_front()");
  110.         (*head)->record = rec;
  111.         (*head)->record_size = rec_size;
  112.         (*head)->next = NULL;
  113.     }
  114.     else {
  115.         struct node_s *n = (struct node_s *)malloc(sizeof(struct node_s));
  116.         if (!n) error_alloc_node(&n, "n, insert_front()");
  117.         n->record_size = rec_size;
  118.         n->record = rec;
  119.         n->next = *head;
  120.         *head = n;
  121.     }
  122. }
  123.  
  124. /*
  125.  * Dodaje noda na koniec listy jednokierunkowej
  126.  * Bez sortowania
  127.  */
  128. void lpush_back(struct node_s **head, char *rec, size_t record_size) {
  129.     // Jeśli początek jest null to glowa = nowy element
  130.     if (*head == NULL) {
  131.         *head = (struct node_s *)malloc(sizeof(struct node_s));
  132.         if (!*head) error_alloc_node(head, "nowy, insert_back()");
  133.         (*head)->record = rec;
  134.         (*head)->record_size = record_size;
  135.         (*head)->next = NULL;
  136.     }
  137.     else {
  138.         struct node_s *node = *head;
  139.         for (; node->next != NULL; node = node->next);
  140.         node->next = (struct node_s *)malloc(sizeof(struct node_s));
  141.         if (!node->next) error_alloc_node(&node->next, "node->next, insert_back()");
  142.         node->next->next = NULL;
  143.         node->next->record = rec;
  144.         node->next->record_size = record_size;
  145.       }
  146. }
  147.  
  148. /**
  149.  * Drukuj liste
  150.  */
  151. void lprint(struct node_s *head) {
  152.     for (; head != NULL; head = head->next)
  153.         printf("%s %d | %p -> %p\n", head->record, (int)(head->record_size - sizeof(char)), head, head->next);
  154. }
  155.  
  156.  
  157.  
  158. /**
  159.  * Usuwa liste z pamieci
  160.  *
  161.  */
  162. void ldestroy(struct node_s **head) {
  163.     struct node_s *tmp = NULL;
  164.     for (; tmp != NULL;) {
  165.         tmp = (*head)->next;
  166.         //Zwlania węzeł
  167.         free((*head)->record);
  168.         (*head)->record = NULL;
  169.         free((*head));
  170.         (*head) = NULL;
  171.         *head = tmp;
  172.     }
  173.     *head = NULL;
  174. }
  175.  
  176. /**
  177.  * Drukuj ostatnie permutacje
  178.  */
  179. void lprintp(struct node_s *head, int c) {
  180.     struct node_s *tmp = NULL;
  181.     int i = 0, k = 0, j = 0;
  182.    
  183.     // MAGIC
  184.     for( i = 0 ; i < c; i++) {
  185.         fprintf(stdout, "(%s", head->record);
  186.         tmp = head;
  187.         k = (2*c - 2*i)-1;
  188.         //printf("k: %d\n", k);
  189.         for ( j = 0; j < k ; j++) {
  190.             tmp = tmp->next;
  191.         }
  192.         if(tmp != NULL)
  193.             fprintf(stdout, "+%s)\n", tmp->record);
  194.         else {
  195.             perror("zla matematyka !");
  196.             ldestroy(&head);
  197.             exit(EXIT_FAILURE);
  198.         }
  199.         if(head->next != NULL)
  200.             head = head->next;
  201.     }
  202.     /*for (; (*head) != NULL && (*head)->used == 0 ; (*head) = (*head)->next) {
  203.         // pierwszy wolny wyraz
  204.             fprintf(stdout, "(%s+", (*head)->record);
  205.             (*head)->used = 1;
  206.  
  207.                 next = (*head)->next;
  208.                 if(next != NULL) {
  209.                 // znajdz ostatnio wolny
  210.                 for (; next != NULL; next = next->next) {
  211.                     if(next->next == NULL) {
  212.                         printf("jest null\n");
  213.                         fprintf(stdout, "%s)\n", (next->record));
  214.                         next->used = 1;
  215.                         break;
  216.  
  217.                     } else if (next->used == 0) {
  218.                         fprintf(stdout, "%s)\n", (next->record));
  219.                         next->used = 1;
  220.  
  221.  
  222.                         }
  223.  
  224.                     }
  225.                 }
  226.         }
  227.     }*/
  228.     /*(*head)->used = 1;
  229.         fprintf(stdout, "(%s+", (*head)->record);
  230.         tmp = (*head);
  231.         // wskocz na ostatnio wolny (used)  wyraz w liscie od aktualnej pozycji
  232.         for (; tmp != NULL; tmp = tmp->next)
  233.             fprintf(stdout, "%s)\n", tmp->record);
  234.             tmp->used = 1;
  235.  
  236.  
  237.     fprintf(stdout, "\n");*/
  238.  
  239. }
  240.  
  241. int main(int argc, char **argv) {
  242.     int i, j, k, l, m, offset, c = 5;
  243.     size_t record_size, new_record_size, newest_record_size;
  244.     char new_glue[4], newest_glue[4], record[6];
  245.     struct node_s *list = NULL;
  246.  
  247.     int is_even = ((c + 1) % 2 == 0) ? 1 : 0;
  248.  
  249.     if((c + 1) >= AB_SIZE) {
  250.         fprintf(stderr, "Za malo literek (w) AlfaBecie");
  251.         exit(EXIT_FAILURE);
  252.     }
  253.  
  254.  
  255.     // wyzerujmey sobie pamiec
  256.     memset(&record, 0, 6 * sizeof(char));
  257.     memset(&new_glue, 0, 4 * sizeof(char));
  258.     memset(&newest_glue, 0, 4 * sizeof(char));
  259.  
  260.  
  261.     // Bob budowniczy..
  262.  
  263.     // ustawimy poczatkowe wartosc - znaki ( ) i +
  264.     record[0] = chars[0];
  265.     record[2] = chars[2];
  266.     record[4] = chars[1];
  267.  
  268.     new_glue[0] = chars[2];
  269.     new_glue[2] = chars[1];
  270.  
  271.     newest_glue[0] = chars[2];
  272.     newest_glue[2] = chars[1];
  273.  
  274.     for(i = 0; i < (c + 1); i++) {
  275.         for(k = c; k > i; k--) {
  276.             // malloc '(' + ')' + '+' + (ab * 2) + 'null terminator'
  277.             //record_size = (sizeof(char) + sizeof(char) + sizeof(char) + (sizeof(char) * 2) + sizeof(char));
  278.             //record = (char *) malloc(record_size);
  279.             //if(record == NULL) {
  280.             //    perror("Malloc");
  281.             //    exit(EXIT_FAILURE);
  282.             //}
  283.  
  284.             // Generujemy wiersz
  285.             //record[0] = chars[0];
  286.             record[1] = ab[i];
  287.             //record[2] = chars[2];
  288.             record[3] = ab[k];
  289.             //record[4] = chars[1];
  290.             //record[5] = (char)'\0';
  291.  
  292.             // printf("i:%d k:%d %s\n", i, k, record);
  293.  
  294.             // a taki hackerski trick azeby sensownie poukladac rekordy w liscie.
  295.             //  nie mialem na to pomyslu strict algorytmicznego aby wygenerowac dla np n=3
  296.             // ciag znakow w atkiej kolejnosci jak ponizej:
  297.             // ((A+B)+(C+D))
  298.             // ((A+C)+(B+D))
  299.             // ((A+D)+(B+C))
  300.             //
  301.             //  wymaga pamieci heap
  302.  
  303.  
  304.             if(is_even) {
  305.                 if( k % c  == 0)
  306.                     lpush_back(&list, strdup(record), sizeof(record) * sizeof(char));
  307.                 else if(k % 2 == 0)
  308.                     lpush_back(&list, strdup(record), sizeof(record) * sizeof(char));
  309.                 else
  310.                     lpush_front(&list, strdup(record), sizeof(record) * sizeof(char));
  311.             }
  312.  
  313.  
  314.  
  315.              fprintf(stdout, "%s\n", record);
  316.             // doklej nastpne  char y za wyjatkiem wykorzystanych powyzej
  317.                 for(l = 0; l < (c + 1); l++) {
  318.                     if(i != l && l != k) {
  319.                         // fprintf(stdout, "%s+%c)", record, ab[l]);
  320.  
  321.                         //new_record_size = sizeof(char) + sizeof(char) + sizeof(char);
  322.                         //new_record = (char *)malloc(record_size + new_record_size);
  323.                         //memset(new_record, 0, record_size + new_record_size);
  324.  
  325.                         new_glue[1] = ab[l];
  326.  
  327.                         //new_glue[3] = (char)'\0';
  328.                         //memcpy(new_record, record, record_size);
  329.                         //offset = record_size - sizeof(char);
  330.                         //memcpy(new_record + offset, &glue, (sizeof(char) * 3));
  331.                         //lpush_front(&list, new_record, record_size + new_record_size);
  332.                         fprintf(stdout, "%s%s\n", record, new_glue);
  333.                         // doklej resztke
  334.                         for(j = 0; j < (c + 1); j++) {
  335.                             if((ab[j] != ab[l]) && (ab[j] != ab[i]) && (ab[j] != ab[k])) {
  336.                                 //newest_record_size = sizeof(char) + sizeof(char) + sizeof(char) +  record_size + new_record_size;
  337.                                 //newest_record = (char *)malloc(newest_record_size);
  338.                                // memset(newest_record, 0, newest_record_size);
  339.  
  340.                                 //newest_glue[0] = chars[2];
  341.                                 newest_glue[1] = ab[j];
  342.                                 //newest_glue[2] = chars[1];
  343.                                 //newest_glue[3] = (char)'\0';
  344.                                 //memcpy(newest_record, new_record, record_size + new_record_size);
  345.                                // printf("newest_record = %s", newest_record);
  346.                                 ///offset = record_size + new_record_size - sizeof(char);
  347.                                 //printf(" , glue = %s\n", glue);
  348.                                 ///memcpy(newest_record + offset, &glue, (sizeof(char) * 3));
  349.                                 //printf("finally: %s\n",  newest_record);
  350.                                 ///lpush_front(&list, newest_record, new_record_size + newest_record_size);
  351.  
  352.                                 fprintf(stdout, "%s%s%s\n",record,new_glue, newest_glue);
  353.                             }
  354.                         }
  355.  
  356.                     }
  357.  
  358.                 }
  359.  
  360.                 //free(record);
  361.             //    record = NULL;
  362.         }
  363.    }
  364.    if(is_even) {
  365.         lprintp(list, c);
  366.         ldestroy(&list);
  367.     }
  368.     return EXIT_SUCCESS;
  369. }
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!