Data Structure -- Permutations

[varalu 0]

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 !!!

[laexter 0]

$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)

[iGuest 3]

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;}//---------------------------------------------------------