fork(2) download
copy 
  1. /// The complexity of the approach is O(n*n!)
  2. /// It finds a valid permutation in linear time 
  3. /// and in a lexicographic order, it also handles the case where there
  4. /// are duplicates present, because it implements am increasing order
  5. // hence duplicates are never used twice to generate permutations
  6.  
  7. #include<iostream>
  8. #include<algorithm>
  9. #include<time.h>
  10. using namespace std;
  11.  
  12. // Swap function
  13.  
  14. template < class T>
  15. void swap(T *i, T *j)
  16. {
  17.     T temp = *i;
  18.     *i = *j;
  19.     *j = temp;
  20. }
  21.  
  22. // function to reverse a range of values
  23. template < class T>
  24. void reverse(T *start, T *end)
  25. {
  26.     while(start < end)
  27.     {
  28.         swap(start,end);
  29.         start++;
  30.         end--;
  31.     }
  32. }
  33.  
  34. // array_end does not point to a valid element of the array
  35. // it is beyond the last element
  36.  
  37. template < class T>
  38. bool permute(T* array_start,T* array_end)
  39. {
  40.     // array does not contain any element
  41.     if(array_start == array_end)
  42.         return false;
  43.  
  44.     // array contains only 1 element
  45.     if(array_start+1 == array_end)
  46.         return false;
  47.  
  48.     T *i,*i1,*j;
  49.  
  50.     // Make the pointers point to last and the second last elements
  51.     i = array_end - 2;
  52.     i1 = array_end - 1; 
  53.  
  54.     // find two elements a,b such that a < b and index of a
  55.     // is less than the index of b
  56.  
  57.     while(true)
  58.     {
  59.         // If such a pair is found, find an element c such that
  60.         // c > a, then swap them and reverse the list from b till 
  61.         // the end
  62.         if(*i < *i1)
  63.         {
  64.             j = array_end -1;
  65.  
  66.             // worst case is that j == i1
  67.             while(!(*i < *j))
  68.                 j--;
  69.  
  70.             // This step implements the lexicographic order by 
  71.             // bringing the larger element in the front
  72.             swap(i,j);
  73.  
  74.             // Reverse the list so that we have a weak decreasing
  75.             // order in the remainder of the list
  76.             reverse(i1,array_end-1);
  77.             return true;
  78.         }
  79.  
  80.         // Now the list is in strictly decreasing order
  81.         // no more permutations are possible, return the 
  82.         // list as it was originally received
  83.         if(i == array_start)
  84.         {
  85.             reverse(array_start,array_end-1);
  86.             return false;
  87.         }
  88.  
  89.         // decrement the two pointers
  90.         i--;
  91.         i1--;
  92.     }
  93.  
  94. }
  95. template< class T>
  96. void display(T *array,T *end)
  97. {
  98.     T* i = array;
  99.     while(i < end)
  100.     {
  101.         cout << *i << "-";
  102.         i++;
  103.     }
  104.     cout << endl;
  105. }
  106.  
  107. int main()
  108. {
  109.     srand(time(NULL));
  110.  
  111.     // You can declare any type here of any size
  112.     int size = 4;
  113.     char array[size];
  114.  
  115.     cout << "Enter four numbers" << endl;
  116.     for(int i=0;i < size;i++)
  117.         cin>>array[i];
  118.  
  119.     // C++ sort function so that the permutation 
  120.     // function receives the elements in the sorted order
  121.     // in order to create a lexicographic order
  122.     sort(array,array+4);   
  123.  
  124.     // First permutation
  125.     display(array,array+4);
  126.     int count=1;
  127.  
  128.     // Call the function while you get valid permutations
  129.     while(permute(array,array+4))
  130.     {
  131.         count++;
  132.         display(array,array+4);
  133.     }
  134.  
  135.     cout << "Total permutations are " << count << endl;
  136.  
  137.     system("pause");
  138.     return 0;
  139. }
Success #stdin #stdout 0.02s 5312KB
comments (?)
stdin
copy 
3
1
4
2
stdout
copy 
Enter four numbers
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-
Total permutations are 24
https://ideone.com/sK8JH
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

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!