CareerCup

public void permutation(char[] a, int n) {
		if(n == 1){
			System.out.println(a);
			return;
		}
		
		for(int i = 0; i < n; i++){
			swap(a, i, n-1);
			permutation(a, n-1);
			swap(a, i, n-1);
		}
		
	}


	private void swap(char[] a, int i, int j) {
		char c;
		c = a[i]; a[i] = a[j]; a[j] = c;
		
	}

void permute(char s[],int k)
{
if(i==strlen(s))
cout<<s<<endl;
else
for(int j=0;j<strlen(s);++j)
{
swap(s[k],s[j]);
permute(s,k+1);
swap(s[k],s[j]);
}
}
int main()
{
char s1[5]="hello";
permute(s1,0);
return 0;
}

@Tomek..The for loop should be like this .

for(int j=k;j<strlen(s);++j)

haha, be careful with writing strlen(s) in the for-loop's condition statement.
Some interviewers may end the interview when they see this :)

Hi ,

Can any one post the correct solution for given constraint in the string like in case of "aaa" it should repeat only once .once way is to check if the string contains duplicates initially , what can be another way ... please some one suggest

void Anagram(string in, string out)
{
int len = in.length();

if (len == 0)
std::cout<< out <<"\t";
for (int i =0; i< len; i++)
{
if ( len > (i+1) && in.at(i) == in.at(i+1) )
continue; //for dupilcate alphabet
Anagram(in.substr(0,i) + in.substr(i+1,len), out+ in.at(i) );
}
}

Here is what I wrote for integers -- basically same thing.

To calculate the permutation of an array of objects, foreach object in the array, add the object to the permutations of the reminder of the group recursively.

public ArrayList<ArrayList<Integer>> findPermutations(ArrayList<Integer> integers)
    {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (integers == null || integers.size() == 0)
        {
            return result;
        }
        for (int i = 0; i < integers.size(); i++)
        {
            ArrayList<Integer> subArray = new ArrayList<Integer>();
            for (int j = 0; j < integers.size(); j++)
            {
                if (!integers.get(j).equals(integers.get(i)))
                {
                    subArray.add(integers.get(j));
                }
            }
            ArrayList<ArrayList<Integer>> subResult = this.findPermutations(subArray);
            for (ArrayList<Integer> subPerm : subResult)
            {
                subPerm.add(integers.get(i));
                result.add(subPerm);
            }
            ArrayList<Integer> selfResult = new ArrayList<Integer>();
            selfResult.add(integers.get(i));
            result.add(selfResult);
        }
        return result;
    }

So for [1, 2, 3, 4] you'll get

[4, 3, 2, 1]
[3, 2, 1]
[3, 4, 2, 1]
[4, 2, 1]
[2, 1]
[4, 2, 3, 1]
[2, 3, 1]
[2, 4, 3, 1]
[4, 3, 1]
[3, 1]
[3, 2, 4, 1]
[2, 4, 1]
[2, 3, 4, 1]
[3, 4, 1]
[4, 1]
[1]
[4, 3, 1, 2]
[3, 1, 2]
[3, 4, 1, 2]
[4, 1, 2]
[1, 2]
[4, 1, 3, 2]
[1, 3, 2]
[1, 4, 3, 2]
[4, 3, 2]
[3, 2]
[3, 1, 4, 2]
[1, 4, 2]
[1, 3, 4, 2]
[3, 4, 2]
[4, 2]
[2]
[4, 2, 1, 3]
[2, 1, 3]
[2, 4, 1, 3]
[4, 1, 3]
[1, 3]
[4, 1, 2, 3]
[1, 2, 3]
[1, 4, 2, 3]
[4, 2, 3]
[2, 3]
[2, 1, 4, 3]
[1, 4, 3]
[1, 2, 4, 3]
[2, 4, 3]
[4, 3]
[3]
[3, 2, 1, 4]
[2, 1, 4]
[2, 3, 1, 4]
[3, 1, 4]
[1, 4]
[3, 1, 2, 4]
[1, 2, 4]
[1, 3, 2, 4]
[3, 2, 4]
[2, 4]
[2, 1, 3, 4]
[1, 3, 4]
[1, 2, 3, 4]
[2, 3, 4]
[3, 4]
[4]

public class Permutation2 {
public static void main(String[] args)
{

	char[] a = "aa".toCharArray();
	Permutation2 p = new Permutation2();
	p.permutation(a,a.length);
	
	
}
public void permutation(char[] a, int n) {
	if(n == 1){
		System.out.println(a);
		return;
	}
	boolean[] b = new boolean[256];
	for(int i = 0; i < n; i++){
		if(b[(int)a[i]])continue;
		b[(int)a[i]]=true;
		swap(a, i, n-1);
		permutation(a, n-1);
		swap(a, i, n-1);
	}
	
}
private void swap(char[] a, int i, int j) {
		char c;
		c = a[i]; a[i] = a[j]; a[j] = c;
		
	}
	
}