2 replies to this topic

[varalu]

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?

Quote

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]

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

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[I]=(char*)malloc(l*sizeof(char)); //--------------------- int s=strlen(suffix); char *suffix_temp =(char*) malloc((s+2)*sizeof(char)); for(I=0;suffix[I]!='0';I++)   suffix_temp[I]=suffix[I]; //--------------------- for(I=0;I<l;I++) { count=0; for(j=(I+1)%l;j!=I;j=(j+1)%l) smaller[I][count++]=str[j]; smaller[I][count]='0';     suffix_temp[s]=str[I]; suffix_temp[s+1]='0'; permutation(smaller[I],suffix_temp); }}int main(){    char *str="ABCD"; permutation(str); system("pause");   return 0;}//---------------------------------------------------------