xisto Community

# Data Structure -- Permutations

## Recommended Posts

Write an algorithm to print all the permutations of a string.

Input: man

Output: man

mna

amn

anm

nam

nma

Give solutions optimized for Speed. Optimize for Size too.

What is a permutation?

Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation. For example, with the numerals one to six, each possible ordering consists of a complete list of the numerals, without repetitions. There are 720 total permutations of these numerals, one of which is: "4, 5, 6, 1, 2, 3".

The general concept of permutation can be defined more formally in different contexts:

* In set theory, a permutation is an ordered sequence containing each symbol from a set once, and only once. A permutation is distinct from a set or combination, in that the ordering of elements in a set is not considered relevant for sets or combinations. In other words, the set-theoretic definition of permutation is that of a one-to-one correspondence, or bijection, of labeled elements with "positions" or "places" which are arranged in a straight line.

* In abstract algebra and related areas, the elements of permutation may not be arranged in a linear order, or indeed in any order at all. Under this refined definition, a permutation is a bijection from a finite set, X, onto itself. This allows for the definition of groups of permutations; see permutation group.

* In combinatorics, the term permutation also has a traditional meaning which includes ordered lists without repetition and where one or more elements from the list are omitted from the distinguishable orderings; for example, a permutation of "1,2,4,3" with "5" and "6" omitted.

Here i have one possible solution from my friend.... (Pallavi)

1.Concat the input string with itself : manman

2. initialise the ptr to first element

3. Print it length of the string

4. Move the ptr by one position ( keep incrementing till length times) and perform step 3

5. reverse the whole string and repeat steps 2, 3, 4

Any better solutions? WELCOME !!!

##### Share on other sites
`\$tmp = array();\$s = 'the string you wish to permute, in the example, e.g. man';\$out = '';\$ctr=0;function perm(\$ctr) {	global \$out;	global \$s;	global \$tmp;	//echo \$out;	if (\$ctr == strlen(\$s)) {		echo \$out . "\n";	}	else {		for (\$i=0;\$i<strlen(\$s);\$i++) {			//echo 'a';			if (!\$tmp[\$i]) {				\$tmp[\$i]=TRUE;				\$out .= \$s[\$i];				perm(\$ctr+1);				\$tmp[\$i]=FALSE;				\$out = substr(\$out, 0, -1);			}		}	}}perm(0);`

is something I have in my computer. (it is PHP if you haven't noticed)

##### Share on other sites
permutation of a string.....solutionData Structure -- Permutations

#include<iostream>#include<cstring>Using namespace std;Void permutation(char *str,char *suffix=""){ if(strlen(str)==0) {printf("%sand",suffix); return;}     int I,j,count,l=strlen(str); char *smaller[l]; for(I=0;I<l;I++) smaller=(char*)malloc(l*sizeof(char)); //--------------------- int s=strlen(suffix); char *suffix_temp =(char*) malloc((s+2)*sizeof(char)); for(I=0;suffix!='0';I++)   suffix_temp=suffix; //--------------------- for(I=0;I<l;I++) { count=0; for(j=(I+1)%l;j!=I;j=(j+1)%l) smaller[count++]=str[j]; smaller[count]='0';     suffix_temp=str; suffix_temp[s+1]='0'; permutation(smaller,suffix_temp); }}int main(){    char *str="ABCD"; permutation(str); system("pause");   return 0;}//---------------------------------------------------------

## Create an account

Register a new account