fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #include <string.h>
  5. #include <limits.h>
  6. /* #define DEBUG */
  7.  
  8. #if defined(DEBUG)
  9. /*--------------------------------------------*/
  10. #else
  11. #define xmalloc(x, y) malloc(x)
  12. #define xfree(x, y) free(x)
  13. #define xmallocdump()
  14. #endif
  15.  
  16. #define ID_ROOT    1001
  17. #define ID_SUB     1002
  18. #define ID_BUFF    1003
  19.  
  20. void calcPos(int idx, int *offset, int *mask) {
  21.   *offset = (idx - 1) / (CHAR_BIT * sizeof(int));
  22.   int index = (idx - 1) % (CHAR_BIT * sizeof(int));
  23.   int m = 1;
  24.   for (int i = 0; i < index; i++) m = (m << 1);
  25.   *mask = m;
  26. }
  27.  
  28. int isBitOn(int *buff, int idx) {
  29.   int offset, mask;
  30.   calcPos(idx, &offset, &mask);
  31.   return ((buff[offset] & mask) > 0) ? 1 : 0;
  32. }
  33.  
  34. void setBitOn(int *buff,int idx) {
  35.   int offset, mask;
  36.   calcPos(idx, &offset, &mask);
  37.   buff[offset] =  buff[offset] | mask;
  38. }
  39.  
  40. void permutation2(int lim, int n, int z, int *parent_buff1, int *buff2) {
  41.   if (n == 0) {
  42.     for (int i = 0; i < lim; i++) printf("%d ", buff2[i]);
  43.     putchar('\n');
  44.     return;
  45.   }
  46.  
  47.   for (int i = 1; i <= lim; i++) {
  48.     if (!isBitOn(parent_buff1, i)) {
  49.      buff2[lim - n] = i;
  50.       int *my_buff1 = xmalloc(z, ID_SUB);
  51.       if (my_buff1) {
  52.         memcpy(my_buff1, parent_buff1, z);
  53.         setBitOn(my_buff1, i);
  54.         permutation2(lim, n - 1, z, my_buff1, buff2);
  55.         xfree(my_buff1, ID_SUB);
  56.       }
  57.     }
  58.   }
  59. }
  60.  
  61. void permutation(int n) {
  62.   int z;
  63.   int *buff1 = (int *)xmalloc((z = (n + (CHAR_BIT * sizeof(int))) / (CHAR_BIT * sizeof(int))), ID_ROOT);
  64.   int *buff2 = (int *)xmalloc(n, ID_BUFF);
  65.   if (buff1 || buff2) {
  66.     for (int i = 0; i < z; i++) buff1[i] = 0;
  67.     permutation2(n, n, z, buff1, buff2);
  68.   }
  69.   xfree(buff1, ID_ROOT);
  70.   xfree(buff2, ID_BUFF);
  71. }
  72.  
  73. int main() {
  74.   permutation(4);
  75.   xmallocdump();
  76.   return 0;
  77. }
  78. /* end */
  79.  
Success #stdin #stdout 0s 4824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1
https://ideone.com/wbwxg3
language:
C (clang 8.0)
created:
5 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!