fork download 
  1. #include <iostream>
  2. #include <cassert>
  3. #include <cstdint>
  4.  
  5. // convenience types
  6. typedef unsigned uint;
  7. typedef std::uint64_t uint64;
  8.  
  9. // number of elements 2 <= N < 16
  10. enum { N = 3 }; 
  11.  
  12. // class to store a set of digits in one uint64
  13. class Set16 {
  14.   public:
  15.     enum { size = N };
  16.  
  17.   private:
  18.     uint64 _store; // storage
  19.  
  20.   public:
  21.     // initializes the set in ascending order.
  22.     // (This is a premise to start permutation at first result.)
  23.     Set16(): _store()
  24.     {
  25.       for (uint i = 0; i < N; ++i) elem(i, i + 1);
  26.     }
  27.  
  28.     // get element with a certain index.
  29.     uint elem(uint i) const { return _store >> (i * 4) & 0xf; }
  30.     // set element with a certain index to a certain value.
  31.     void elem(uint i, uint value)
  32.     {
  33.       i *= 4;
  34.       _store &= ~((uint64)0xf << i);
  35.       _store |= (uint64)value << i;
  36.     }
  37.     // swap elements with certain indices.
  38.     void swap(uint i1, uint i2)
  39.     {
  40.       uint temp = elem(i1);
  41.       elem(i1, elem(i2));
  42.       elem(i2, temp);
  43.     }
  44.     // reverse order of elements in range [i1, i2)
  45.     void reverse(uint i1, uint i2)
  46.     {
  47.       while (i1 < i2) swap(i1++, --i2);
  48.     }
  49. };
  50.  
  51. // re-orders set to provide next permutation of set.
  52. // returns true for success, false if last permutation reached
  53. bool nextPermutation(Set16 &set)
  54. {
  55.   assert(Set16::size > 2);
  56.   uint i = Set16::size - 1;
  57.   for (;;) {
  58.     uint i1 = i, i2;
  59.     if (set.elem(--i) < set.elem(i1)) {
  60.       i2 = Set16::size;
  61.       while (set.elem(i) >= set.elem(--i2));
  62.       set.swap(i, i2);
  63.       set.reverse(i1, Set16::size);
  64.       return true;
  65.     }
  66.     if (!i) {
  67.       set.reverse(0, Set16::size);
  68.       return false;
  69.     }
  70.   }
  71. }
  72.  
  73. std::ostream& operator<<(std::ostream &out, const Set16 &set)
  74. {
  75.   const char *sep = "";
  76.   for (uint i = 0; i < Set16::size; ++i, sep = ", ") out << sep << set.elem(i);
  77.   return out;
  78. }
  79.  
  80. // main
  81. int main()
  82. {
  83.   Set16 set;
  84.   // output all permutations of sample
  85.   unsigned n = 0; // permutation counter
  86.   do {
  87. #if 1 // for demo:
  88.     std::cout << set << std::endl;
  89. #else // the OP wants instead:
  90.     /// @todo check whether sample builds a magic square
  91. #endif // 1
  92.     ++n;
  93.   } while(nextPermutation(set));
  94.   std::cout << n << " permutations found." << std::endl;
  95.   // done
  96.   return 0;
  97. }
Success #stdin #stdout 0s 4424KB
comments ()
stdin 
Standard input is empty
stdout 
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
6 permutations found.
https://ideone.com/ULSksM
language:
C++ (gcc 8.3)
created:
7 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!