CareerCup

void getPermutations(string[] input){
Hashmap hashMap = new Hashmap<String,List<String>();
 for(int i=0; i< input.length(); i++){
   String key = getKey(input[i]);
   if(hashMap.contains(key){
     hashMap.get(key).add(input[i]);
   }
   else{
     hashMap.add(key,new List<String>(input[i]));	
   }

 }

 foreach( key in hashMap){
   foreach(String in hashMap.getKey)
     print(string+",")
     print("\n");	
   }
}

pubic String getKey(String inpt){

int[] asciiAray;
int i=0; 

foreach(char in inpt){
asciiAray[i++]=(int)char;
}

sort asciiarray;

String key;

foreach(int in asciiArray){
key+ =(char)int;
}

return key;

}

Shouldn't the permutations for abc be {abc, acb, bac, bca, cab, cba} ?

what if we sort given input , I mean sort strings given in input ...

like abc,cba ---> abc,abc then find out matching strings....if matches then put those strings in one set.

What's the meaning of sets of permutation? Why not {abc, ba} a permutation?

This implementation would add duplicates to the set .
For example , the output would be [ ( abc,cab ) ( ba,ba ) ( b ) ]
To remove duplicates like "ba" in the example above I think we can preprocess the data or while checking for "isPermutation" instead of comparing with just one element , have a "for loop" that iterates over the entire vector .

#include <iostream>
#include <string>
#include <vector>

using namespace std ;

typedef vector<string> vectorOfStrings ;

vector<vectorOfStrings> listOfSetsOfPermutations ;

// Utility function to check if two strings
// are permutations of each other.
// Assumes an ASCII character set ( 0 - 255 ) 

bool
isPermutation( string str1 , string str2 ) {

    if( str1.length() != str2.length() ) {
        return false ;
    }

    // trackCharacters maintains the count of each
    // character's occurence in str1 . We store it
    // in the index represented by the ASCII value
    // of the character . 
 
    int trackCharacters[ 256 ] ;
    int characterValue = 0 ;

    // Initialize the array to avoid
    // undefined behaviour . 
    for( int i = 0 ; i < 256 ; i++ ) {
         trackCharacters[i] = 0 ;
    }

    for( int i = 0 ; i < str1.length() ; i++ ) {
         characterValue = str1.at(i) ;
         trackCharacters[characterValue]++;
    }

    // When parsing the 2nd string , for each
    // character that is common between the two
    // strings , we reduce the count of character
    // occurences . If at any point the count for 
    // a character goes below 0 , str2 is not a 
    // permutation of str1 .
    for( int i = 0 ; i < str2.length() ; i++ ) {
         characterValue = str2.at(i) ;
         trackCharacters[characterValue] --;
         if( trackCharacters[characterValue] < 0 ) {
             return false ;
         }
    }

    return true ;
}

vector<vectorOfStrings>
computeListOfSetsOfPermutations( vectorOfStrings inputData , int index ) {

    bool permutation = false ;

    if( index == 0 ) {
        vectorOfStrings set = vectorOfStrings() ;
        set.push_back( inputData[index] ) ;
        listOfSetsOfPermutations.push_back( set ) ;
    } else {
        for( int i = 0 ; i < listOfSetsOfPermutations.size() ; i++ ) {
             vectorOfStrings set = listOfSetsOfPermutations[i] ;
             if( isPermutation( set[0],inputData[index] ) ) {
                 listOfSetsOfPermutations[i].push_back( inputData[index] ) ;
                 return listOfSetsOfPermutations ;
             }
        }

        vectorOfStrings newSet = vectorOfStrings() ;
        newSet.push_back( inputData[index] ) ;
        listOfSetsOfPermutations.push_back( newSet ) ;
        return listOfSetsOfPermutations ;
    } 

    for( int i = 1 ; i < inputData.size() ; i++ ) {
         listOfSetsOfPermutations = computeListOfSetsOfPermutations( inputData , i );
    }

    return listOfSetsOfPermutations ; 
}

// Driver code to test 
int
main() {

    vectorOfStrings inputData = vectorOfStrings() ;

    inputData.push_back("abc") ;
    inputData.push_back("cab") ;
    inputData.push_back("ba") ;
    inputData.push_back("b") ;
    inputData.push_back("ba") ;

    listOfSetsOfPermutations = computeListOfSetsOfPermutations( inputData,0 ) ;

    cout << "[ " ;
    for( int i = 0 ; i < listOfSetsOfPermutations.size() ; i++ ) {
         vectorOfStrings permutationSubset = listOfSetsOfPermutations[i] ;
         cout << "(  " ;
         for( int j = 0 ; j < permutationSubset.size() ; j++ ) {
              cout << permutationSubset[j] << "," ;
         }
         cout << "   ) " ;
    }

    cout << "  ] " << "\n" ;

    return 1 ;
}

the following code handles cases when more then one permutation of a string is present and also deals with duplicate case

public class CheckPermutation {

	static String[] words= {"abc","cab","ba", "b", "ba","bca","ab","cba"};
	
	public static boolean checkIfPermutation(String s1,String s2)
	{
		if(s1.length()!=s2.length())
			return false;
		
			char[] lett= s1.toCharArray();
			
			for(char c:lett)
			{
				String s= Character.toString(c);
				if(!s2.contains(s))
					return false;			
			}
			return true;
	}
	
	public static void printPermutations()
	{
		boolean match=false;
		int[] id=new int[words.length];
		for(int k=0;k<id.length;k++)
		{
			id[k]=-1;
		}
		
		for(int i=0;i<words.length-1;i++)
		{
			if(id[i]!=1){
			match=false;	
			System.out.print(words[i]+" ");
			
			for(int j=i+1;j<words.length;j++){
				match=checkIfPermutation(words[i],words[j]);
				if(match==true && words[i]!=words[j]&&id[j]==-1)
				{
					id[i]=1;
					id[j]=1;
					System.out.print(words[j]+" ");
					continue;
				}
				
				if(match==true && words[i]==words[j])
				{
					id[i]=1;
					id[j]=1;
					//System.out.println(words[i]);
					continue;
				} 
			}
			System.out.println();
			}
		}
	}
	
	public static void main(String[] args) {	
		printPermutations();
	}
}

int main()
{
int i, len, j, temp, k = 0, found = 0;
char *in;
int calPrime[10] = {1, 1, 1, 1, 1, 1, 1, 1};
int pind[10];

char prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

std::string input[] = {"abc", "cab", "ba", "b", "ba", "cba", "ab", "b"};

for(i=0; i<8; i++)
{
in = (char *)input[i].c_str();
len = strlen(in);
for(j = 0; j<len; j++)
{
calPrime[i] *= prime[in[j] - 'a'];
}
printf("prime: %d\n", calPrime[i]);
}

for(i=0; i<8; i++)
{
for(int n=0; n<k; n++)
{
if(i == pind[n])
{
found = 1;
break;
}
}
if(found == 1)
{
found = 0;
continue;
}
temp = calPrime[i];
printf("pairs: (%s ", input[i].c_str());
for(j = i+1; j<8; j++)
{
if( temp == calPrime[j]) {
pind[k++] = j;
printf(", %s", input[j].c_str());
}
}
printf(")\n");
}



return 0;
}

int len = pow(2,strlen(str);
for(i=0;i<len;i++)
{
int index = 0;
while(i)
{
if(i&1)print(str[i]);
index++;
}
}

Correction in above code:
after index++ add:
i>>1;

and after the while loop, add :
"\n"

for each word, if there is a same word then no need to add to the set, and if there is an anagram exist add it to the set, repeat for all the words except for the processed words.

Insert each word in trie.
While inserting use count [26] to sort the word.
each time word is inserted at the end of trie, add the index of word as in original list,

Now traverse trie and output all words and return the index from trie.

Looks like what you want is the power set, not permutations.

How about sort by two keys,
First key is the string with sorted characters,
Secon is string itself

///
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CareerCup
{
class Program
{
static void Main(string[] args)
{
string[] inputs = { "abc", "cab", "ba", "b", "ba", "ba", "acb"};

var setMap = new Dictionary<string, HashSet<string>>();

foreach (var item in inputs)
{
var sortedCharItem = SortCharacters(item);

HashSet<string> set;

if (!setMap.TryGetValue(sortedCharItem, out set))
{
set = new HashSet<string>();
setMap.Add(sortedCharItem, set);
}

set.Add(item);
}

foreach (var set in setMap)
{
foreach (var item in set.Value)
{
Console.Write(item + " ");
}

Console.WriteLine();
}
}

static string SortCharacters(string input)
{
var chars = input.ToCharArray();
Array.Sort<char>(chars);
return new string(chars);
}
}
}
\\\

int strCompare(char a[], char b[])
{
int len = strlen(a);

if(len != strlen(b))
return 0;
for(int i=0; i<len; i++)
{
if(a[i]-b[i] != 0)
return 0;
}
return 1;
}

int isPermutation(char a[], char b[])
{
int len = strlen(a);
int i, j;

if(len != strlen(b))
return 0;
else
{
for(i=0; i<len; i++)
{
for(j=0; j<len; j++)
{
if(a[i]-b[j] == 0)
break;
}
if(j == len)
return 0;
}
return 1;
}
}


int main(void)

{

/************************************/
char *str[]={"abc", "cba", "ba", "b", "ba"};
int sn[5] = {0};//store if this string has been marked as printed
int i = 0, j = 0;

//method 1
for(i = 0; i < 5; i++)
{
if(sn[i] == 1)
continue;
//if(sn[i] == 0)
printf("%s\n\r", str[i]);
for(j=i+1; j<5 && !sn[j]; j++)
{
if(strCompare(str[i], str[j]))
{
sn[j] = 1;
}else if(isPermutation(str[i],str[j]))
{
sn[j] = 1;
printf("%s\n\r", str[j]);
}
}
}

//build list which include *str
return 0;

}

Following C++ solution can be used : (Ref: stack overflow)

int main (int argc, char * const argv[]) {
        string s = "sarp";
        bool used [4];
        permute(0, "", used, s);
}

void permute(int level, string permuted, bool used [], string &original) {
    int length = original.length();

    if(level == length) { // permutation complete, display
        cout << permuted << endl;
    } else {
        for(int i=0; i<length; i++) { // try to add an unused character
            if(!used[i]) {
                used[i] = true;
                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                used[i] = false;
            }
        }
}

import java.io.*;
import java.util.Arrays;


public class strpermut {

    public static void main(String[] args) throws IOException {

        String s,sor1,sor2;
        int t,i,j;
        char []arr1 = new char[30];
        char []arr2 = new char[30];

        String s2[]= new String[30];
        System.out.print("input");
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         s= br.readLine();
         s2=s.split(" ");
         int len=s2.length;
   

       for(i=0;i<len-1;i++){
           arr1=s2[i].toCharArray();
           Arrays.sort(arr1);
            sor1 = String.valueOf(arr1);
              
           for(j=i+1;j<len;j++){
                             
               arr2=s2[j].toCharArray();
                Arrays.sort(arr2);
                sor2 = String.valueOf(arr2);
               
                if(sor1.compareTo(sor2)==0){
                    System.out.println("pairs "+s2[i]+" "+s2[j]);
                }
                   
             }

               
           }
     
      

       
    }

  

}