Program to print permutations of given elements [closed]

Solution 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.

Solution 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);
    }
}

Solution 3:

Here is an iterative solution:

First sort the array.

• Find maximum index i a[i+1]. (if no such index exists there are no more permutations left)

Find maximum index j

Swap a[i] and a[j].

Reverse a[i+1]..a[n-1] and go to step *.