CareerCup

select indexes of characters we can move. generate all permutations of them. replace chars in the original string for each permutation.

Example:

input: q1eRz
arr: [0,2,4]

possible permutations:
[0,4,2] -> q1zRe
[2,0,4] -> e1qRz
[2,4,0] -> r1zRq

etc...

if you have dictionary check if the anagram is presented in it.

In C++:

#include <string>
#include <iostream>

void anagram(std::string &word, int n)
{
	if (n <= 0) {
		std::cout << word << "\n";
		return;
	}

	if (word[n] < 'a' or word[n] > 'z') {
		anagram(word, n-1);
		return;
	}

	int i;
	for (i = n; i >= 0; --i) {
		if (word[i] < 'a' or word[i] > 'z')
			continue;

		char tmp = word[i];
		word[i] = word[n];
		word[n] = tmp;
		anagram(word, n-1);
	}
}

void print_anagrams(const std::string &w)
{
	std::string word = w;
	anagram(word, word.length()-1);
}

def comp(word, i, possi):
    if i == len(word) or len(possi) == 0:
        print(word)
        return
    if word[i].isupper() or word[i].isdigit() or (not word[i].isalpha() and not word[i].isdigit()):
        comp(word, i+1, possi)
    else:
        for s in possi:
            copyWord = list(word)
            copyWord[i] = s
            copyWord = "".join(copyWord)
            copyPossi = list(possi)
            copyPossi.remove(s)
            comp(copyWord, i+1, copyPossi)

word = "q1eRz"
import re
regex = re.compile('[^a-z]')
comp(word, 0, list(regex.sub('', word)))

public class question {
	
	public static void main (String args[]){
		String test = "Hi8Test(*!good";

		for (int i = 0; i<test.length(); i++){

			if(test.charAt(i)>= 'a' && test.charAt(i)<= 'z'){
				reorderString(test, i);
			}
		}

	}

	public static void reorderString(String test, int index){
		char [] temp = test.toCharArray();

		for (int j = 0; j<test.length(); j++){
			if(temp[j]>='a' && temp[j]<='z'){
				char tempChar = temp[index];
				temp[index] = temp[j];
				temp[j] = tempChar;
				System.out.println(new String (temp));
			}
		}
	}
}

Not optimal in terms of run time, but a quick solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication2
{
class Anagram
{
public static ArrayList al = new ArrayList();

static void Main(string[] args)
{

string str = "q1eRz";
char[] charArry = str.ToCharArray();
permute(charArry, 0, str.Length - 1);
var uniqueList = al.ToArray().Distinct();
foreach (var item in uniqueList)
{
Console.WriteLine(item);
}

Console.ReadKey();
}

static void permute(char[] arry, int i, int n)
{
int j;
string s;
if (i == n)
{

s = new string(arry);
al.Add(s);
//Console.WriteLine(s);
}
else
{
for (j = i; j <= n; j++)
{

swap(ref arry[i], ref arry[j]);
permute(arry, i + 1, n);
swap(ref arry[i], ref arry[j]); //backtrack
}
}
}

static void swap(ref char a, ref char b)
{
if ((a >= 'a' || a >= 'A') && (a <= 'z' || a <= 'Z') && (b >= 'a' || b >= 'A') && (b <= 'z' || b <= 'Z'))
{

char tmp;
tmp = a;
a = b;
b = tmp;
}

}
}
}

#include<stdio.h>

void anagram(char*,int,int);
void swap(char *,char*);
int main(void){
	char s[20]={'\0'};
	int length;

	printf("enter a string\n");
	scanf("%s",s);
	putchar('\n');
	int i;
	for(i=0;i<20;i++){
		if(s[i]=='\0'){
			length=i;
			break;
		}
	}
	anagram(s,0,length);
	return 0;
}

void anagram(char*s,int i,int length){
	int j;
	if(i==length)
		printf("%s\n",s);
	if(s[i]>'z' || s[i]<'a'){
		anagram(s,i+1,length);
		return;
	}
	for(j=i;j<length;j++){
		if(s[j]<='z' && s[j]>='a'){
			swap(&s[i],&s[j]);
			anagram(s,i+1,length);
			swap(&s[i],&s[j]);
		}
		else
			anagram(s,i+1,length);
	}
}
void swap(char* a, char* b){
	char c=*a;
	*a=*b;
	*b=c;
}

#include<stdio.h>

void anagram(char*,int,int);
void swap(char *,char*);
int main(void){
	char s[20]={'\0'};
	int length;

	printf("enter a string\n");
	scanf("%s",s);
	putchar('\n');
	int i;
	for(i=0;i<20;i++){
		if(s[i]=='\0'){
			length=i;
			break;
		}
	}
	anagram(s,0,length);
	return 0;
}

void anagram(char*s,int i,int length){
	int j;
	if(i==length)
		printf("%s\n",s);
	if(s[i]>'z' || s[i]<'a'){
		anagram(s,i+1,length);
		return;
	}
	for(j=i;j<length;j++){
		if(s[j]<='z' && s[j]>='a'){
			swap(&s[i],&s[j]);
			anagram(s,i+1,length);
			swap(&s[i],&s[j]);
		}
		else
			anagram(s,i+1,length);
	}
}
void swap(char* a, char* b){
	char c=*a;
	*a=*b;
	*b=c;
}

public static void main (String args[]){
		String input = "AbcDe";
                reorderString(input, "");
 

	}

	public static void reorderString(String test, String res){
            
            //char[] temp = test.toCharArray();
            System.out.println(res+test);
            
            if (test.length()==1){
                System.out.println(res+test);
            } else {
                int i;
            for (i=0;i<test.length();i++){
                if ('a'<=test.charAt(i)&& test.charAt(i)<='z'){
                    for (int j=i+1;j<test.length();j++){
                     
                        if ('a'<=test.charAt(j)&& test.charAt(j)<='z'){
                        
                         char[] temp = test.toCharArray();
                         char tempchar = temp[i];
                         temp[i]=temp[j];
                         temp[j]= tempchar;
                         String newString=new String (temp);
                         
                         reorderString(newString.substring(i+1,test.length()), res+newString.substring(0,i+1));
                        }
                    }
                
                }
            }
            
            }
            
        }

public static void main (String args[]){
String input = "AbcDe";
reorderString(input, "");


}

public static void reorderString(String test, String res){

//char[] temp = test.toCharArray();
System.out.println(res+test);

if (test.length()==1){
System.out.println(res+test);
} else {
int i;
for (i=0;i<test.length();i++){
if ('a'<=test.charAt(i)&& test.charAt(i)<='z'){
for (int j=i+1;j<test.length();j++){

if ('a'<=test.charAt(j)&& test.charAt(j)<='z'){

char[] temp = test.toCharArray();
char tempchar = temp[i];
temp[i]=temp[j];
temp[j]= tempchar;
String newString=new String (temp);

reorderString(newString.substring(i+1,test.length()), res+newString.substring(0,i+1));
}
}

}
}

}

}

def find_anagram(word):
    if len(word) <= 1:
        return set(word)

    result = set([word])
    for i in range(len(word)):
        if 64 < ord(word[i]) < 91:
            continue
        for j in range(i+1,len(word)):
            if 96 < ord(word[j]) < 123:
                word_ = str(word)
                t = word_[i]
                word_ = word_[:i] + word_[j] + word_[i+1:]
                word_ = word_[:j] + t + word_[j+1:]
                inter = set([word_[:i+1]+x for x in find_anagram(word_[i+1:])])
                result = result.union(inter)
    return result

def find_anagram(word):
    if len(word) <= 1:
        return set(word)

    result = set([word])
    for i in range(len(word)):
        if 64 < ord(word[i]) < 91:
            continue
        for j in range(i+1,len(word)):
            if 96 < ord(word[j]) < 123:
                word_ = str(word)
                t = word_[i]
                word_ = word_[:i] + word_[j] + word_[i+1:]
                word_ = word_[:j] + t + word_[j+1:]
                inter = set([word_[:i+1]+x for x in find_anagram(word_[i+1:])])
                result = result.union(inter)
    return result

public class PermutationOfString {
    public static void main(String[] args){
        String s = "q1zRe";
        
        Set<String> output = findPermutations2(s);
        for(String w: output)
        {
            System.out.println(w);
        }
        
    }
    
    public static Set<String> findPermutations(String s){
        Set output = new HashSet();
        if(s == null){
            return null;
        }
        else if(s.length() == 0)
        {
            output.add("");
            return output;
        }
        
        char ch = s.charAt(0);
        String remString = s.substring(1);
        Set<String> remainingSet = findPermutations(remString);
        for(String newString : remainingSet)
        {
            for(int i = 0; i <= newString.length(); i++)
            {
                output.add(addCharAtPosition(newString, ch, i));
            }
        }
        
        return output;
    }
    
    public static String addCharAtPosition(String s, char ch, int i){
        return (s.substring(0, i) + ch + s.substring(i));
    }
    
    public static Set<String> findPermutations2(String s){
        Set output = new HashSet();
        HashMap<Integer, Character> indices = new HashMap<Integer, Character>();
        StringBuilder indexString = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
            {
                indices.put(i, s.charAt(i));
                indexString.append(i);
            }            
        }
        
        int index1 = 0, index2 = 0;
        char[] sArray = s.toCharArray();
        Set<String> permutations = findPermutations(indexString.toString());
        for(String perm : permutations){
            sArray = s.toCharArray();
            for(int i = 0; i<indexString.length(); i++)
            {
               index1 = Integer.parseInt(perm.charAt(i)+ "");
               index2 = Integer.parseInt(indexString.charAt(i) + "");
               sArray[index2] = indices.get(index1);
            }
            output.add(new String(sArray));
        }
        
        return output;
    }
}

package Strings;

import java.util.ArrayList;

public class AnagramsOfLettersOnly {

	public static void main(String[] args) {
		String input = "Hello";
		StringBuilder indexesOfLetters = new StringBuilder();
		for(int i = 0; i < input.length(); i++) {
			if(input.charAt(i) > 'a' && input.charAt(i) < 'z')
				indexesOfLetters.append(i);
		}
		
		if(indexesOfLetters.length() == 0 || indexesOfLetters.length() == 1) {
			System.out.println("No anagrams for this string");
			return;
		}
		
		ArrayList<String> permutationsOfIndexes = getPermutations(indexesOfLetters.toString());
		
		for(String eachPermutation: permutationsOfIndexes) {
			StringBuilder builder = new StringBuilder(input);
			for(int i = 0; i < eachPermutation.length(); i++) {
				builder.setCharAt(Character.getNumericValue(indexesOfLetters.charAt(i)), input.charAt(Character.getNumericValue(eachPermutation.charAt(i))));
			}
			System.out.println(builder);
		}
	}
	
	public static ArrayList<String> getPermutations(String str) {
		ArrayList<String> permutations = new ArrayList<String>();

		if(str == null)
			return null;
		
		if(str.length() == 0) {
			permutations.add(str);
			return permutations;
		}
		
		char currentChar = str.charAt(0);
		String remainingString = str.substring(1);
		ArrayList<String> words = getPermutations(remainingString);
		for(String word : words) {
			for(int i = 0; i <= word.length(); i++) {
				String newWord = addCharAt(word, i, currentChar);
				permutations.add(newWord);
			}
		}
		
		return permutations;
	}

	public static String addCharAt(String word, int i, char currentChar) {
		return word.substring(0, i) + currentChar + word.substring(i, word.length());
	}
}

import java.util.*;
import java.util.Map.Entry;
class new1{
	public static void main(String[] args){
		
		anagram("a1bGc2deP*");
	}
	
	
	public static void anagram(String org){
		if(org==null) return;
		if(org.length()==0 || org.length()==1) return;
		int len=org.length();
		HashMap<Integer,Character> map = new HashMap<Integer,Character>();
		
		String resort="";
		for(int i=0;i<len;i++){
			if(org.charAt(i)>='a' && org.charAt(i)<='z'){
				resort+=org.charAt(i);
			}else{
				map.put(i, org.charAt(i));
			}
			
			
			
		}
		
		
		String tem="";
		String curr=resort;
		int resort_len=resort.length();
		List<String> res = new ArrayList<String>();
		
		helper(resort,curr,resort_len,tem,res);
		//Iterator<Entry<Integer, Character>> iter = map.entrySet().iterator();
		for(String s:res){
			for(Entry<Integer, Character> entry:map.entrySet()){
				int i=entry.getKey();
				char c=entry.getValue();
				s=s.substring(0,i)+c+s.substring(i);
			
				
			}
			System.out.println(s);
		}
		
		
	}
	
	public static void helper(String resort,String curr,int resort_len,String tem,List<String> res){
		if(resort_len==0 && !tem.equals(resort)){
			res.add(tem);
			return;
		}
		
		
		for(int i=0;i<resort_len;i++){
			helper(resort,curr.substring(0,i)+curr.substring(i+1,resort_len),resort_len-1,tem+curr.charAt(i),res);
		}
		
		
		
	}
	
	
	
	
	
	
}

import java.util.*;
import java.util.Map.Entry;
class new1{
	public static void main(String[] args){
		
		anagram("a1bGc2deP*");
	}
	
	
	public static void anagram(String org){
		if(org==null) return;
		if(org.length()==0 || org.length()==1) return;
		int len=org.length();
		HashMap<Integer,Character> map = new HashMap<Integer,Character>();
		
		String resort="";
		for(int i=0;i<len;i++){
			if(org.charAt(i)>='a' && org.charAt(i)<='z'){
				resort+=org.charAt(i);
			}else{
				map.put(i, org.charAt(i));
			}
			
			
			
		}
		
		
		String tem="";
		String curr=resort;
		int resort_len=resort.length();
		List<String> res = new ArrayList<String>();
		
		helper(resort,curr,resort_len,tem,res);
		//Iterator<Entry<Integer, Character>> iter = map.entrySet().iterator();
		for(String s:res){
			for(Entry<Integer, Character> entry:map.entrySet()){
				int i=entry.getKey();
				char c=entry.getValue();
				s=s.substring(0,i)+c+s.substring(i);
			
				
			}
			System.out.println(s);
		}
		
		
	}
	
	public static void helper(String resort,String curr,int resort_len,String tem,List<String> res){
		if(resort_len==0 && !tem.equals(resort)){
			res.add(tem);
			return;
		}
		
		
		for(int i=0;i<resort_len;i++){
			helper(resort,curr.substring(0,i)+curr.substring(i+1,resort_len),resort_len-1,tem+curr.charAt(i),res);
		}
		
		
	}
		
	
}

import java.util.*;
import java.util.Map.Entry;
class new1{
public static void main(String[] args){

anagram("a1bGc2deP*");
}


public static void anagram(String org){
if(org==null) return;
if(org.length()==0 || org.length()==1) return;
int len=org.length();
HashMap<Integer,Character> map = new HashMap<Integer,Character>();

String resort="";
for(int i=0;i<len;i++){
if(org.charAt(i)>='a' && org.charAt(i)<='z'){
resort+=org.charAt(i);
}else{
map.put(i, org.charAt(i));
}



}


String tem="";
String curr=resort;
int resort_len=resort.length();
List<String> res = new ArrayList<String>();

helper(resort,curr,resort_len,tem,res);
//Iterator<Entry<Integer, Character>> iter = map.entrySet().iterator();
for(String s:res){
for(Entry<Integer, Character> entry:map.entrySet()){
int i=entry.getKey();
char c=entry.getValue();
s=s.substring(0,i)+c+s.substring(i);


}
System.out.println(s);
}


}

public static void helper(String resort,String curr,int resort_len,String tem,List<String> res){
if(resort_len==0 && !tem.equals(resort)){
res.add(tem);
return;
}


for(int i=0;i<resort_len;i++){
helper(resort,curr.substring(0,i)+curr.substring(i+1,resort_len),resort_len-1,tem+curr.charAt(i),res);
}



}






}