Adobe Interview Question
# 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;
}
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;
}
<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?
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;
}
anagrams("Hello",0,5);
public static void print anagrams(String str, int start, int n)
{
if(start == n)
{
System.out.println(str);
}else{
for(int i = start; i < n ; i++)
{
swap(str,start,i);
anagrams(str,start+1,n)
swap(str,start,i);
}
}
}
public static void swap(char str[],int i, int j){
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
#include <iostream>
#include <set>
#include <string>
using namespace std;
void printPermut(string s, string prefix = "") {
if (s.empty()) {
if (!prefix.empty()) {
cout << prefix << endl;
}
}
set<char> visited;
string cpy;
for (int i = 0; i < s.length(); ++i) {
if (visited.find(s[i]) == visited.end()) {
visited.insert(s[i]);
cpy = string(s);
cpy.erase(i, 1);
printPermut(cpy, prefix + s[i]);
}
}
}
int main(int argc, char **argv) {
if (argc == 2) {
printPermut(string(argv[1]));
}
}
function getPerms(str) {
if (!str) return [];
if (str.length === 1) return [str];
var chars = str.split('');
var a = [];
var s = new Set();
var n = chars.length;
for (var i = 0; i < n; i++) {
var rest = str.replace(chars[i], '');
var perms = getPerms(rest);
for (var j = 0; j < perms.length; j++) {
var newStr = chars[i] + perms[j];
if (!s.has(newStr)) s.add(newStr);
}
}
return Array.from(s);
}
function getPerms(str) {
if (!str) return [];
if (str.length === 1) return [str];
var chars = str.split('');
var a = [];
var s = new Set();
var n = chars.length;
for (var i = 0; i < n; i++) {
var rest = str.replace(chars[i], '');
var perms = getPerms(rest);
for (var j = 0; j < perms.length; j++) {
var newStr = chars[i] + perms[j];
if (!s.has(newStr)) s.add(newStr);
}
}
return Array.from(s);
}
- MaYanK July 23, 2010