Click here to Skip to main content
Click here to Skip to main content

String Permutations - How to Generate Permutations of String or Numbers

, 18 May 2014
Rate this:
Please Sign up or sign in to vote.
Learn how to generate permutations of Strings

Introduction

Today, I will be telling you how to print all the possible permutations of a string provided by the user. I will show you the recursive way to do this. The programming paradigm that we use in case of Recursion is backtracking.

What do you mean by Permutations?

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.
For more information, visit http://mathworld.wolfram.com/Permutation.html.

Recursion

This is a bad method for printing permutations since it's time complex, i.e., it takes more time to execute than the iterative method. This is because of the extensive use of the call stack. Now the following image explains the recursion technique. The image presents the recursion tree of the method of permutations generation. We take the example string that we permute as "GOD".

In order to find all possible combinations for a given string, start at a position i, then find and place all possible letters in position i. Every time we put a new letter in position i, we should then find all the possible combinations at position i+1 – this would be the recursive call that we make.

[Image: permute_zps699764b7.png]

Here's the C++ implementation string permutation.

Code

#include <iostream> 
#include <cstring> 

using namespace std; 

void swap(char* src, char* dst) 
{ 
 char ch = *dst; 
 *dst = *src; 
 *src = ch; 
} 

void permuteString(char* s, int beg, int end) 
{ 
 int i; 
 int range = end - beg; 
 if (range == 1) { 
 cout<<s<<endl; 
 } else { 
 for(i=0; i<range; i++) { 
 swap(&s[beg], &s[beg+i]); 
 permuteString(s, beg+1, end); 
 swap(&s[beg], &s[beg+i]);
 } 
 } 
}

int main() 
{
 char str[] = "GOD";
 cout<<"The permutations are :- "<<endl; 
 permuteString(str, 0, strlen(str)); 
 getchar();
 return 0; 
}

Now the above code will print all the permutations of the string "GOD" without repetition. But if you want to print them in lexicographic manner, i.e., where the repetitions of the characters are included, then read the matter below.

Since we are going in lexicographic order, we have to do the following. It's pretty much understandable. (Note: The numbers represent index and 1 means the starting index, we will not use 0 for the first index as we do it in programming.)

  • Start with index '1' and then recurse over rest of the 'n - 1' numbers.
    • Start with '2' and then recurse over rest of the 'n - 2' numbers.
    • Start with '3' and then recurse over rest of the 'n - 2' numbers.
      :
      :
    • Start with 'i' and then recurse over rest of the 'n - 2' numbers.
      :
      :
    • Start with 'n' and then recurse over rest of the 'n - 2' numbers.
  • Start with a '2' and then recurse over rest of the 'n - 1' numbers.
    • Start with '1' and then recurse over rest of the 'n - 2' numbers.
    • Start with '3' and then recurse over rest of the 'n - 2' numbers.
      :
      :
    • Start with 'i' and then recurse over rest of the 'n - 2' numbers.
      :
      :
    • Start with 'n' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'i' and then recurse over rest of the 'n - 1' numbers.:

    :

  • Start with 'n' and then recurse over rest of the 'n - 1' numbers.
The important thing to note is, in every recursion, you start with the minimum numbers left, to be printed, and then keep picking the next minimum, and so on, till you exhaust all the 'n' numHebers.

Here's the C code for Lexicographical Permutations.

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Following function is used by the library qsort() function to sort an array of chars */
int compare (const void * a, const void * b);

/* this function recursively prints all repeated permutations of the given string.*/
void LRecurse (char *str, char* data, int last, int index)
{
 int i, len = strlen(str);

 // One by one fix all characters at the given index and recur for the subsequent indexes
 for ( i=0; i<len; i++ )
 {
 // Fix the ith character at index and if this is not the last index then recursively call for higher indexes
 data[index] = str[i] ;

// If this is the last index then print the string stored in data
 if (index == last)
 printf("%s\n", data);
 else 
 LRecurse (str, data, last, index+1);
 }
}

/* This function sorts input string, allocate memory and calls LRecurse() for printing all permutations */
void LSort(char *str)
{
 int len = strlen (str) ;

 char *data = (char *) malloc (sizeof(char) * (len + 1)) ;
 data[len] = '\0';

 // Sort the input string so that we get all output strings in lexicographically sorted order
 qsort(str, len, sizeof(char), compare);
 LRecurse (str, data, len-1, 0);
 free(data);// Free data to avoid memory leak
}

// Needed for library function qsort()
int compare (const void * a, const void * b)
{
 return ( *(char *)a - *(char *)b );
}

int main()
{
 char str[] = "GOD";
 printf("All permutations of %s in Lexicographic order are : \n", str);
 LSort(str);
 getchar();
 return 0;
} 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Psycho_Coder
Student
India India
My name is Animesh Shaw, Currently I am pursuing B. Tech in Computer Science. My Screen name is Psycho_Coder. I am active in many Security or Ethical Hacking forums. I love programming and exploring the depths of Computer Science.
 
Programming Languages know : C, C++,Java, Python and PHP.
 
You can even contact me on the following :-
 
1, CS - Computer Science Lovers : https://www.facebook.com/CSComputerScienceLovers. Please like it.
 
2. CS(Computer Science) Lovers : https://www.facebook.com/groups/csloversforever/
My facebook group to discuss programming. You can join this group if you are serious about computer science and programming.
 
3. You can mail me at psychocoder@outlook.com
 

My Interests :
 
I have great interests in the following topics in Computer Science :-
 
1. Programming Language Concepts and Methodologies.
2. Computational Linguistics.
3. Cryptography.
 
Github Profile : https://github.com/PsychoCoderHC
Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web03 | 2.8.140821.2 | Last Updated 18 May 2014
Article Copyright 2014 by Psycho_Coder
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid