sortingc++11permutationheaps-algorithm

Why computer takes more time in arranging different permutations?


I just learned the heap's algorithm. Well the larger the number of objects get the more time the system takes to arrange them in all possible permutations. But when i calculate the the factorial of that number of objects in a calculator the results are instant. Why does it happen that same no. of permutations take more time than calculating the factorial?

   #include <stdio.h>
   #include <stdlib.h>
   #include<iostream>
    using namespace std;
    int len;
   void swap (int *x, int *y)
  {
     int temp;
     temp = *x;
     *x = *y;
     *y = temp;
  }
   void print(const int *v)
  {
     int i;
     int size = len;
     if (v != 0) {
     for ( i = 0; i < size; i++) {
     cout<< v[i] ;
}
cout<<'\n';
}
}
void heappermute(int v[], int n) {
int i;
if (n == 1) {
    print(v);
}
else {
    for (i = 0; i < n; i++) {
        heappermute(v, n-1);
        if (n % 2 == 1) {
            swap(&v[0], &v[n-1]);
    }
        else {
            swap(&v[i], &v[n-1]);
        }
   }
  }
 }

 int main()
 {
  int num[11];
  int  i;
  cout<<"How many numbers you want to enter: ";
  cin>>len;
  cout<<"\nEnter the numbers: ";
  for ( i = 0 ; i < len; i++)
   cin>>num[i];
  heappermute(num, len);
  return 0;
 }

Solution

  • You are giving two different tasks to your computer program and to your calculator. Generating every possible permutation of a set of objects is a different problem from finding the number of such permutations.

    How many positive even numbers are there below one billion? What are they? (List them all.) Which one takes longer to figure out?

    There are ways to calculate a factorial other than listing all the possibilities. See this question that gives both the naive recursive approach (F(n) = n*F(n-1)) which is Omega(n2 log n) and also an O(n log n log log n) algorithm.

    A factorial can also be estimated, which may be close enough. I don't know exactly what method your calculator is using, but one possibility is Stirling's approximation.