Program to generate permutation of characters

Iterative C program


#include 
#define SIZE 3
int main(char *argv[],int argc)
{
  char list[3]={'a','b','c'};
  int i,j,k;

  for(i=0;i
    for(j=0;j
      for(k=0;k
        if(i!=j && j!=k && i!=k)
          printf("%c%c%c\n",list[i],list[j],list[k]);

  return(0);
}



Recursive C program


#include 
#define N  5


int main(char *argv[],int argc)
{
  char list[5]={'a','b','c','d','e'};
  permute(list,0,N);
  return(0);
}


void permute(char list[],int k, int m)
{
  int i;
  char temp;

  if(k==m)
  {
    /* PRINT A FROM k to m! */
    for(i=0;i
    printf("\n");
  }
  else
  {
     for(i=k;i
     {
        /* swap(a[i],a[m-1]); */
        temp=list[i];
        list[i]=list[m-1];
        list[m-1]=temp;

        permute(list,k,m-1);

        /* swap(a[m-1],a[i]); */

        temp=list[m-1];
        list[m-1]=list[i];
        list[i]=temp;
       }
  }
}

To determine whether machine is Little-Endian and Big-Endian?

What Little-Endian and Big-Endian? How can I determine whether a machine's byte order is big-endian or little endian? How can we convert from one to another?

First of all, Do you know what Little-Endian and Big-Endian mean?

Little Endian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address. That is, the little end comes first.

For example, a 4 byte, 32-bit integer


    Byte3 Byte2 Byte1 Byte0


will be arranged in memory as follows: 
    Base_Address+0   Byte0 
    Base_Address+1   Byte1 
    Base_Address+2   Byte2 
    Base_Address+3   Byte3 


Intel processors use "Little Endian" byte order.


"Big Endian" means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.


  Base_Address+0   Byte3
  Base_Address+1   Byte2
  Base_Address+2   Byte1
  Base_Address+3   Byte0


Motorola, Solaris processors use "Big Endian" byte order.

In "Little Endian" form, code which picks up a 1, 2, 4, or longer byte number proceed in the same way for all formats. They first pick up the lowest order byte at offset 0 and proceed from there. Also, because of the 1:1 relationship between address offset and byte number (offset 0 is byte 0), multiple precision mathematic routines are easy to code. In "Big Endian" form, since the high-order byte comes first, the code can test whether the number is positive or negative by looking at the byte at offset zero. Its not required to know how long the number is, nor does the code have to skip over any bytes to find the byte containing the sign information. The numbers are also stored in the order in which they are printed out, so binary to decimal routines are particularly efficient.


Here is some code to determine what is the type of your machine


int num = 1;
if(*(char *)&num == 1)
{
  printf("\nLittle-Endian\n");
}
else
{
  printf("Big-Endian\n");
}



And here is some code to convert from one Endian to another.



int myreversefunc(int num)
{
  int byte0, byte1, byte2, byte3;  

  byte0 = (num & x000000FF) >>  0 ;
  byte1 = (num & x0000FF00) >>  8 ;
  byte2 = (num & x00FF0000) >> 16 ;
  byte3 = (num & xFF000000) >> 24 ;

  return((byte0 << 24) | (byte1 << 16) | 
(byte2 << 8) | (byte3 << 0));
}
 
What Little-Endian and Big-Endian? How can I determine whether a machine's byte order is big-endian or little endian? How can we convert from one to another?

First of all, Do you know what Little-Endian and Big-Endian mean?

Little Endian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address. That is, the little end comes first.

For example, a 4 byte, 32-bit integer


    Byte3 Byte2 Byte1 Byte0


will be arranged in memory as follows: 
    Base_Address+0   Byte0 
    Base_Address+1   Byte1 
    Base_Address+2   Byte2 
    Base_Address+3   Byte3 


Intel processors use "Little Endian" byte order.


"Big Endian" means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.


  Base_Address+0   Byte3
  Base_Address+1   Byte2
  Base_Address+2   Byte1
  Base_Address+3   Byte0


Motorola, Solaris processors use "Big Endian" byte order.

In "Little Endian" form, code which picks up a 1, 2, 4, or longer byte number proceed in the same way for all formats. They first pick up the lowest order byte at offset 0 and proceed from there. Also, because of the 1:1 relationship between address offset and byte number (offset 0 is byte 0), multiple precision mathematic routines are easy to code. In "Big Endian" form, since the high-order byte comes first, the code can test whether the number is positive or negative by looking at the byte at offset zero. Its not required to know how long the number is, nor does the code have to skip over any bytes to find the byte containing the sign information. The numbers are also stored in the order in which they are printed out, so binary to decimal routines are particularly efficient.


Here is some code to determine what is the type of your machine


int num = 1;
if(*(char *)&num == 1)
{
  printf("\nLittle-Endian\n");
}
else
{
  printf("Big-Endian\n");
}



And here is some code to convert from one Endian to another.



int myreversefunc(int num)
{
  int byte0, byte1, byte2, byte3;  

  byte0 = (num & x000000FF) >>  0 ;
  byte1 = (num & x0000FF00) >>  8 ;
  byte2 = (num & x00FF0000) >> 16 ;
  byte3 = (num & xFF000000) >> 24 ;

  return((byte0 << 24) | (byte1 << 16) | 
(byte2 << 8) | (byte3 << 0));
}
 

pow function

Brute force C program


int pow(int x, int y)
{
  if(y == 1) return x ;
  return x * pow(x, y-1) ;
}



Divide and Conquer C program


#include 
int main(int argc, char*argv[])
{
  printf("\n[%d]\n",pow(5,4));
}

int pow(int x, int n)
{
  if(n==0)return(1);
  else if(n%2==0)
  {
    return(pow(x,n/2)*pow(x,(n/2)));
  }
  else
  {
    return(x*pow(x,n/2)*pow(x,(n/2)));
  }
}


Swapping 2 variables using macro

 #define swap(type,a,b) type temp;temp=a;a=b;b=temp;

Now, think what happens if you pass in something like this


swap(int,temp,a) //You have a variable called "temp" (which is quite possible).



This is how it gets replaced by the macro


int temp;
temp=temp;
temp=b;
b=temp;

Swapping 2 variables without 3rd variable

Method1 (The XOR trick)

a ^= b ^= a ^= b;


Although the code above works fine for most of the cases, it tries to modify variable 'a' two times between sequence points, so the behavior is undefined. What this means is it wont work in all the cases. This will also not work for floating-point values. Also, think of a scenario where you have written your code like this



swap(int *a, int *b)
{
  *a ^= *b ^= *a ^= *b;
}


Now, if suppose, by mistake, your code passes the pointer to the same variable to this function. Guess what happens? Since Xor'ing an element with itself sets the variable to zero, this routine will end up setting the variable to zero (ideally it should have swapped the variable with itself). This scenario is quite possible in sorting algorithms which sometimes try to swap a variable with itself (maybe due to some small, but not so fatal coding error). One solution to this problem is to check if the numbers to be swapped are already equal to each other.


swap(int *a, int *b)
{
  if(*a!=*b)
  {
    *a ^= *b ^= *a ^= *b;
  }
}




Method2

This method is also quite popular


 a=a+b;
 b=a-b;
 a=a-b;


But, note that here also, if a and b are big and their addition is bigger than the size of an int, even this might end up giving you wrong results.