CareerCup

class StringPermutation {
    
    /**
    * @param args
    */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String input = "abb";
        permutation(input, "");
    }
    
    private static void permutation(String input, String sofar) {
        // TODO Auto-generated method stub
        
        if (input.equals("")) {
            System.out.printf("%s,", sofar);
        }
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (input.indexOf(c, i + 1) != -1)
            continue;
            permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
        }
    }
    
}

Working Python Code As below....

def dp_per(x,y):
    #print x,y
    if len(y)==1:
        print x+y
        global count
        count=count+1
    else:
        cache=[]
        dp_per(x+y[0],y[1:])
        cache.append(y[0])
        for i in range(1,len(y)):
            if y[i] not in cache:
                cache.append(y[i])
                dp_per(x+y[i],y[1:i]+y[0]+y[i+1:])
print 'enter your String !!!!'
x=raw_input()
count=0
print 'Ans as below:'
dp_per('',x)
print 'Total Ans['+str(count)+']:'

#include <hash_set>

void PrintAnagrams(char * str,
         size_t offset = 0, size_t * pLen = NULL)
{
   if (!offset) pLen = new size_t(strlen(str));

   if (offset == *pLen - 1)
      std::cout << str << std::endl;
   else {
      stdext::hash_set<char> distinct;
      distinct.insert(str[offset]);
      PrintAnagrams(str, offset + 1, pLen);

      for (int i = offset + 1; i < *pLen; ++i)
         if (distinct.find(str[i]) == distinct.end()) {
            distinct.insert(str[i]);
            std::swap(str[offset], str[i]);
            PrintAnagrams(str, offset + 1, pLen);
            std::swap(str[offset], str[i]);
         }
      }

   if (!offset) delete pLen;
}

Do it iteratively .....

<pre lang="c++" line="1" title="CodeMonkey30135" class="run-this">#include<iostream>
#include<stdio.h>
#include<string>
#include<set>

using namespace std;


void permute(set<string> &repo,string constructed, string remaining) {
if(remaining.length() == 0) {
//printf("%s\n",constructed);
repo.insert(constructed);
return;
}
for(int i=0;i<remaining.length();++i) {
permute(repo,
constructed+remaining[i],
string(remaining,0,i)+string(remaining,i+1,remaining.length()-i-1));
}
}

void print_anagrams(string input) {
set<string> repo;
permute(repo,string(""),input);
set<string>::iterator i=repo.begin();
printf("Printing permutations..\n");
while(++i!=repo.end())
printf("%s\n",i->c_str());
}


//Program to print all permutations of a string without repetition
int main(int argc, char **argv) {
string a("abad");
print_anagrams(a);
return 0;
}</pre><pre title="CodeMonkey30135" input="yes">
</pre>

All the above solutions are not scalable (aka. inefficient). Number of possible permutations are very large. So if it needs to check (either manually or using STL like set), it is not desirable approach.

I remember in Rosen's discrete mathematics book there is an iterative solution that uniquely generate the permutations w/o any check (when the given string has repeated char like "ABCDABCABA". Anyone has any idea?

Really nice solution.

Short but really hard to understand but finally i got it.

void permute(string str, string rem)
{
int len = rem.size();
if(len == 0)
{
printf("%s\n", str.c_str());
return;
}
int i = str.size() - len;
for(int x=0; x<len; x++)
{
str[i] = rem[x];
string r = rem;
r.erase(x, 1);
permute(str, r);
}
}

void printall_perm(string x)
{
permute(x,x);
}

# include <stdio.h>
# include <conio.h>


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++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j));
}
}
}


int main()
{

char a[] = "ABC";
permute(a, 0, 2);
getchar();
return 0;
}

hello

public static ArrayList<String> getPerms(String s) {
   ArrayList<String> permutations = new ArrayList<String>();
   if (s == null) { // error case
     return null;
   } else if (s.length() == 0) { // base case
     permutations.add(“”);
     return permutations;
   }
   char first = s.charAt(0); // get the first character
   String remainder = s.substring(1); // remove the first character
   ArrayList<String> words = getPerms(remainder);
   for (String word : words) {
     for (int j = 0; j <= word.length(); j++) {
       permutations.add(insertCharAt(word, first, j));
     }
   }
   return permutations;
 }
 public static String insertCharAt(String word, char c, int i) {
   String start = word.substring(0, i);
   String end = word.substring(i);
   return start + c + end;
 }