Epic Systems Interview Question Software Engineer / Developers
0of 0 votesget a string(word) from user, then make every possible permutation words.
Ex)intput: tree => output : tree, rtee, rete, reet, etre, eetr, eert, eter, eret, teer, reet...
Country: United States
Interview Type: Written Test
you also can use next_permutation to eliminate the repeated output, but it needs to sort array first
vector<char> v;
sort(v.begin(), v.end());
do {
// output elements in v
} while (next_permutation(v.begin(), v.end());
This was very helpful. I spent a couple hours breaking my head trying to figure out what the code is doing. And it just blew me. This program is also careful not to print duplicates. Thanks!!
Just an improvement to save some unnecessary swap function calls. Call the swap function only if i is not equal to j. This holds for both the forward swap and the backtrack swap.
if ( i != j ) {
swap ( a + i , a + j ) ;
}
<pre lang="" line="1" title="CodeMonkey7469" class="run-this">class Perm {
static void p(char[] text, int i){
if (i==text.length)
System.out.println(text);
else for (int j=i;j<text.length; j++){
swap(text, i, j);
p(text, i+1);
swap(text, i, j);
}
}
static void swap(char[] text, int i, int j){
char c = text[i];
text[i]=text[j];
text[j]=c;
}
public static void main(String[] args) throws Exception{
p("tree".toCharArray(), 0);
}
}
</pre><pre title="CodeMonkey7469" input="yes">
</pre>
int Mycount = 0;
void permute(int n , bool *isVisited, int level, string crtString)
{
if(level == n)
{
Mycount++;
cout<<crtString<<endl;
}
else
{
for(int i = 0 ; i < n ; ++ i)
{
if(isVisited[i] == 0)
{
isVisited[i] = 1;
char tmp = i + '0';
permute(n, isVisited, level+1, crtString+tmp);
isVisited[i] = 0;
}
}
}
}
int main (int argc, const char * argv[])
{
int n = 5;
bool *isVisited = new bool[n];
for(int i = 0; i < n ; ++ i )
{
isVisited[i] = 0;
}
permute(n, isVisited, 0, "");
cout<<"count = "<<Mycount<<endl;
return 0;
}
String text="tree";
char[] perm = text.toCharArray();
System.out.println();
int count=0;
int charLength = perm.length;
Set<String> set = new HashSet<String>();
while(charLength!=0){
charLength--;
for (int j = 0,i=1; j <perm.length-1; j++,i++) {
if(i!=j){
char temp = perm[j];
perm[j]= perm[i];
perm[i] = temp;
String x = new String(perm);
// System.out.println(x);
set.add(x);
// count++;
}
else{
System.out.println("i==j");
}
}
}
Iterator<String> it = set.iterator();
while(it.hasNext()){
count++;
System.out.println("Perm WOrds Are : "+it.next());
}
System.out.println("Total "+count);
}
here is the recursive code
- getjar.com/todotasklist my android app on December 18, 2011 Edit | Flag Reply#include <cstdlib> #include <iostream> using namespace std; /* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } void permute(char *a, int i, int n) { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { if (a[i] == a[j] && i != j) continue; swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } } int main(int argc, char *argv[]) { char a[] = "ABC"; permute(a, 0, 2); system("PAUSE"); return EXIT_SUCCESS; }