Program to print permutations of given elements [closed]

Question

I recently took part in ACM certified programming competition. This is the question which I could not do at that time:

"Given an array of integers having n elements, write a program to print all the permutations."

Please tell me how to do this question. Is there any algorithm to do this kind of questions?

Answer 1

assuming there are no repeats: just change each element with all possible following elements, and recursively invoke the function.

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

You can see the code with auxilary functions swap() and printArray() performing with a basic test case at ideone

Bonus: This is similar to the idea of fisher-yates shuffle, but in here - intead to swapping the element at i with randomly chosen following element - you swap it with all of them - each at a time.

Answer 2

A recursive approach should do fine:

If the list is empty
    Return the only possible permutation, an empty list.

Else
    For each element of the list
        Put the element at the first place (i.e. swap it with the first element)
          (If the element is same as the first one, don't swap)
        Recursively find all the permutations of the rest of the list

This algorithm won't generate repeated permutations.

Here's a python implementation:

def permute(s):
    if len(s) == 0:
        return [[]]

    ret = [s[0:1] + x for x in permute(s[1:])]

    for i in range(1, len(s)):
        if s[i] == s[0]:
            continue
        s[0], s[i] = s[i], s[0]
        ret += [s[0:1] + x for x in permute(s[1:])]

    return ret

s = [0, 1, 2, 3]
for x in permute(s):
    print x

The similar thing in C should be like this:

void swap(char* str, int i, int j)
{
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

void permute(char *string, int start, int end)
{
    if(start == end)
    {
        printf("%s\n", string);
        return;
    }

    permute(string, start + 1, end);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(string[start] == string[i])
            continue;
        swap(string, start, i);
        permute(string, start + 1, end);
        swap(string, start, i);
    }
}