fork download
copy 
  1. #include <time.h>
  2. #include <ctype.h>
  3. #include <stdio.h>
  4. #include <stddef.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. void print_combinations_aux(char *s, size_t pos) {
  9.   if(s[pos] == '\0') {
  10.     puts(s);
  11.   } else if(isalpha(s[pos])) {
  12.     s[pos] = toupper(s[pos]);
  13.     print_combinations_aux(s, pos + 1);
  14.     s[pos] = tolower(s[pos]);
  15.     print_combinations_aux(s, pos + 1);
  16.   } else {
  17.     print_combinations_aux(s, pos + 1);
  18.   }
  19. }
  20.  
  21. void print_combinations_inplace(char *s) {
  22.   print_combinations_aux(s, 0);
  23. }
  24.  
  25. void print_combinations(char const *s) {
  26.   char *p = malloc(strlen(s) + 1);
  27.   strcpy(p, s);
  28.   print_combinations_inplace(p);
  29.   free(p);
  30. }
  31.  
  32. char *next_combination(char *s) {
  33.   // upper -> 0, lower -> 1
  34.   char *p;
  35.  
  36.   if(*s == '\0') { return NULL; }
  37.  
  38.   for(p = s; *p; ++p) {
  39.     if(!isalpha(*p)) {
  40.       continue;
  41.     } else if(isupper(*p)) {
  42.       *p = tolower(*p);
  43.       return s;
  44.     } else {
  45.       *p = toupper(*p);
  46.     }
  47.   }
  48.  
  49.   return NULL;
  50. }
  51.  
  52. void analyze(const char *c, unsigned *bitmask, unsigned *combos, char *togglecase)
  53. {
  54.   unsigned bit=1;
  55.   int i;
  56.  
  57.   *bitmask = 0;
  58.   *combos = 1;
  59.   for (; *c; c++, bit<<=1)
  60.     if (isalpha(*c))
  61.       *combos <<= 1;
  62.     else
  63.       *bitmask |= bit;
  64.  
  65.   for (i=0; i<256; i++)
  66.     togglecase[i] = isupper(i) ? tolower(i) : toupper(i);
  67. }
  68.  
  69. void next_bit_combination(char *c, unsigned *pbitmask, unsigned startmask, const char *togglecase) {
  70.   unsigned bitmask = *pbitmask;
  71.   *pbitmask = bitmask + 1;
  72.   unsigned diff = (bitmask ^ *pbitmask) & ~startmask;
  73.   *pbitmask = *pbitmask | startmask;
  74.   unsigned least_index;
  75.   if (diff == 1)
  76.     c[0] = togglecase[(unsigned char)c[0]];
  77.   else
  78.     do {
  79.       least_index = __builtin_ctz(diff);
  80.       c[least_index] = togglecase[(unsigned char)c[least_index]];
  81.     } while ((diff -= 1u<<least_index));
  82. }
  83.  
  84. int main() {
  85.  
  86.   clock_t start, end;
  87.   //char buf[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZA";
  88.   //char buf[] = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z !";
  89.  
  90.   // für ideone
  91.   char buf[] = "A B C";
  92.  
  93.   start = clock();
  94.  
  95.   unsigned bitmask, combos, startmask;
  96.   char table[256];
  97.   analyze(buf, &bitmask, &combos, table);
  98.   startmask = bitmask;
  99.   for (; combos--; next_bit_combination(buf, &bitmask, startmask, table)) {
  100.     puts(buf);
  101.   }
  102.  
  103.   end = clock();
  104.  
  105.   fprintf(stderr, "bittig: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);
  106.  
  107.   puts(buf);
  108.   puts(buf);
  109.   puts(buf);
  110.   puts(buf);
  111.  
  112.   start = clock();
  113.  
  114.   do {
  115.     puts(buf);
  116.   } while(next_combination(buf));
  117.  
  118.   end = clock();
  119.  
  120.   fprintf(stderr, "iterativ: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);
  121.  
  122.   start = clock();
  123.  
  124.   print_combinations_inplace(buf);
  125.  
  126.   end = clock();
  127.  
  128.   fprintf(stderr, "rekursiv: %lf\n", (double) (end - start) / CLOCKS_PER_SEC);
  129.  
  130.   return 0;
  131. }
  132.  
  133.  
Success #stdin #stdout #stderr 0s 1788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
A B C
a B C
A b C
a b C
A B c
a B c
A b c
a b c
A B C
A B C
A B C
A B C
A B C
a B C
A b C
a b C
A B c
a B c
A b c
a b c
A B C
A B c
A b C
A b c
a B C
a B c
a b C
a b c
stderr
copy 
bittig: 0.000000
iterativ: 0.000000
rekursiv: 0.000000
https://ideone.com/KvjCzg
language:
C (gcc 8.3)
created:
12 years 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!