CareerCup

This is trivial to do in C++ with the STL since there's a built-in function that does exactly this.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

void permute(const string &s) {
    string my_string = s;
    sort(my_string.begin(),my_string.end());
    do {
        cout << my_string << "\n";
    } while (next_permutation(my_string.begin(),my_string.end()));
}

int main(int argc, const char * argv[])
{
    std::cout << "Please enter a string to permute\n";
    string perm_string;
    std::cin >> perm_string;
    permute(perm_string);
    return 0;
}

public class Permutation {
public static void printPermutations(int[] array, int l, int h){
int i, temp, j;
boolean skip;
if(l == h){
for(int k = 0; k < h; k++)
System.out.print(array[k] + "\t");
System.out.println();
}else{
for(i = l; i < h; i++){
skip = false;
for(j = l; j < i; j++){
if(array[j] == array[i]){
skip = true;
break;
}
}
if(!skip){
temp = array[l];
array[l] = array[i];
array[i] = temp;

recursion(array, l+1, h);

temp = array[l];
array[l] = array[i];
array[i] = temp;
}
}
}
}


public static void main(String[] args) {
int[] a = {1,2,3,4};
printPermutations(a,0,4);
}

}
This should work without any issues. Duplicates also considered. The idea is to see if a[i] & a[l] are already swapped before swapping them and skip the swap.

Perform the normal "swap-and-permute-the-rest" routine. But....but.... don't swap when it is the same character as the first one.

public class Main {
    
    public static void genPerm(char[] str, int st, int end) {
        if(end - st + 1 <= 1) {
            System.out.println(String.valueOf(str));
            return;
        }
        int N = str.length;
        genPerm(str, st+1, end);
        char first = str[st];
        for(int i = st+1; i < N; i++) {
            if(str[i] != first) {
                swap(str, st, i);
                genPerm(str, st+1, end);
            }
        }
    }
    
    public static void main(String[] args) {
        genPerm("aac".toCharArray(), 0, 2);
    }
    
    private static void swap(char[] str, int src, int dest) {
            char tmp = str[src];
            str[src] = str[dest];
            str[dest] = tmp;
    }
}

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std ;
const int MAXN = 1111 ;

map< char ,int > m;
int n ;

char s[ MAXN ],t[ MAXN ];
vector< pair<char, int > > v ;

void pe(int dep) {
	if(dep != n){
		for(int p=0; p != v.size(); ++ p) if( v[p].second> 0){
			-- v[p].second;
			t[ dep ] = v[p].first ;
			pe(dep + 1);
			++ v[p].second;
		}
	}else{
		cout << t << endl ;
	}
}

int main(){
	while( cin >> s){
		m.clear(); v.clear();
		n=strlen(s); t[n]=0;
		for(int i = 0; s[i]; ++ i) m[ s[i] ] ++ ;
		for( map< char, int >::iterator p = m.begin(); p != m.end(); ++ p)
			v.push_back( make_pair(p->first, p->second));
		sort(v.begin(), v.end());
		pe(0);
	}
	
	return 0;
}

However, here is one other non-recursion algorithm.

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std ;
const int MAXN = 1111 ;

char s[ MAXN ];
int n ;

bool next_permutation( char s[], int l, int r ) {
	for(int i = r-1; i >= l+1; -- i) {
		if(s[i] > s[i-1]) {
			for(int j = r-1; j >=i; -- j) if( s[j] > s[i-1] ) {
				swap( s[i-1], s[j]);
				break;
			}
			reverse(s+i,s+r); //O(n)
			return true ;
		}
	}
	return false;
}

int main(){
	while( cin >> s){
		n=strlen(s);
		sort(s,s+n);
		do{
			puts(s);
		}while(next_permutation(s,0,n));
	}
	return 0;
}

Permute in lexicographical order and only output non repeated strings (different from the last one). You only have to memorize the last one. O(1)

public List<String> permute(String input) {
	List<String> ans  = new ArrayList<String>();
	
	if (input.length() == 1) {
		ans.add(input);
		return ans;
	}

	for (int i = 0; i < input.length(); i++) {
		List<String> childPermutes = permute(input.substring(0,i) + input.substring(i+1,input.length));
		for (String s : childPermutes) {
			ans.add(input.charAt(i) + s);
		}
	}

	return ans;
}

static Queue<String> permutationString(String input){
		Queue<String> store = new LinkedList<String>();

		store.add(input.substring(0, 1));
		for(int index = 1; index < input.length(); index++){
			int queueSize = store.size();
			String subChar = input.substring(index, index + 1);

			for(int queueIndex = 0; queueIndex < queueSize; queueIndex++){
				String sub = store.poll();

				//insert character every index
				for(int chatAt = 0; chatAt < sub.length(); chatAt++){
					String out = sub.substring(0, chatAt) + subChar + sub.substring(chatAt, sub.length());
					store.add(out);
				}
				store.add( sub + subChar);
			}
		}
		
		return store;
	}

Function has to first find the occurances of the each characters in the string :
for example: consider string " xaxbxc "

then counted values are x=3 , a=1, b=1,c=1.

with x=1; (avoid xx appearence)
permuatations are :
xaxbxc
xaxcxb
xbxaxc
xbxcxa
xcxbxa
xcxaxb

now with xx as single elemnet( avoid xxx) { xx,x,a,b,c}

Lastly with xxx as the single element { xxx,a,b,c}

I didnt tried it out , but i hope it helps.

Java code, call as permutation("abcd","")

static void permutation(String input, String so_far){
if(input.equals(""))
System.out.println(so_far);

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), so_far+c);
}
}

Printing the string in sorted order and just checking whether it was equal to its previous printed string will help...if it is equal then dn print it else print it

In java:
before permutation:
1. convert the input String to char array
2. sort the char array

permutation:
recursive definition of permutation:
for each chars in the string, we can place it at the first position,(swapping with first char), then we need to generate permutations for the sub-problem input-string(pos1 to length-1).

to check the duplicate, do not get a char in the first position, if you encountered the same char before.
since the array is sorted, all the same chars will be together. so you can skip all the same chars except the first one.


Complexity : O(N!), N is #chars in the input string

import java.util.ArrayList;
import java.util.Arrays;

public class Permutation{
  
  public static void permute(char[] input, int pos, ArrayList<String> result){
    
    if(pos==input.length){
      result.add( new String(input));
      return;
    }
    
    int i;
    for(i=pos;i<input.length;i++){
      
      if(i>pos && input[i]==input[i-1]) continue;
      
      char tmp = input[pos];
      input[pos] = input[i];
      input[i] = tmp;
      
      Permutation.permute(input, pos+1, result);
      
      tmp = input[pos];
      input[pos] = input[i];
      input[i] = tmp;
    }
    
  }
   
  public static void main(String[] args){
    
    ArrayList<String> result = new ArrayList<String>();
    String s = "oool";
    char [] input = s.toCharArray();
    Arrays.sort(input);
    Permutation.permute(input,0, result);
    
    Permutation.print(result);
  }
}

Very generic working C code is here

/*©jork */

#include <stdio.h>
#include <string.h>

typedef struct in_str_
{
char c;
int fl_used;
} in_str_t;

char     in_str[128], scram[128];
in_str_t in[128];
int	 len, num;

int
scramble(in_str_t *in, int pos)
{
int i;

if(pos == len) {
     printf("%d:	%s \n", ++num, scram);
     return 1;
}

for(i =0; i<len; i++) {
     if(!in[i].fl_used) {
	scram[pos] = in[i].c;
	in[i].fl_used = 1;
	pos ++;
	scramble(in, pos);
	pos--;
	in[i].fl_used = 0;
	while(i<len && (in[i].c == in[i+1].c))
		i++;
     }
}

return 1;
}

main ()
{
int i, j;
char temp_c;

printf("Enter string: \n");
scanf("%s", in_str);

memset(in, 0, 128*sizeof(in_str_t));

len = strlen(in_str);
for(i=0; i<len; i++){
	in[i].c=in_str[i];
	in[i].fl_used = 0; 
}

/* sort this */
for(i=0; i< len; i++)
	for(j=0; j<len-1; j++)
	{
		if(in[j].c > in[j+1].c){
			temp_c = in[j+1].c;
			in[j+1].c = in[j].c;
			in[j].c = temp_c;
		} 
	}

printf("input string: %s \n combinations follows.. \n", in_str);
printf("sorted string: \n");
for(i=0; i<len; i++)
	printf("%c", in[i].c);
printf("\n");

scramble(in, 0);

printf("done! \n");
return 0;
}

here's some code for java which I think works. The findPermutations method is the actual method, the permutations method is a control which cheats by using a hashset, and then I compare the result from the findPermutations method to that using the hash set. There appear to be no duplicates.

The method requires the string to be sorted first, then calls a subroutine in which the character is inserted in every position and then the next character of the same type is inserted into every subsequent position and so on.

Does not require any internal tests to reject duplicates (the tests are only there to ensure there are no duplicates, and terminate the program if there are)

import java.util.HashSet;
import java.util.Set;
import java.util.Vector;

public class GenerateAllPerms {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//This method requires the string to be sorted before being used; so I've just 
		//used a pre-sorted string
		String str = "abbbcddeee";

		//Use method A, the method that does not generate any duplicates
		Vector<String> s = findPermutations(str, 0, "");
		Set<String> permutationsMethodA = new HashSet<String>();
		for (String item : s) {
			//This checks to make sure we don't have any duplicates
			if (permutationsMethodA.contains(item))
			{
				System.err.println("Already contains " + item);
				System.exit(-1);
			}
//			System.out.println(item);
			permutationsMethodA.add(item);
		}
		
		Set <String> permutationsMethodB = permutation(str);
//Comment in to see perms by method B
//		for(String s2 : permutationsMethodB)
//		{
//			System.out.println(s2);
//		}

		//Show number of permutations for both methods
		System.out.println(permutationsMethodB.size() + ", " + permutationsMethodA.size());
		
		//If there were any non-overlapped permutations, this would show them
		System.out.println("Non-overlapped: ");
		permutationsMethodB.removeAll(permutationsMethodA);
		for(String s3 : permutationsMethodB)
		{
			System.out.println(s3);
		}

		// str = "abbcdd";
		// s = findPermutations(str, 0, "");
		// dupes = new HashSet();
		// for(String item : s)
		// {
		// if(dupes.contains(item))
		// System.err.println("Already contains " + item);
		// System.out.println(item);
		// dupes.add(item);
		// }

	}

	//This is the 'smart' method which doesn't generate dupes; it stores in a vector, 
	//nowhere does it filter
	static Vector<String> findPermutations(String in, int at, String soFar)
	{
		Vector<String> strings = new Vector<String>();
		if (at >= in.length()) {
			strings.add(soFar);
			return strings;
		} else {
			int cur = at;
			int charAt = in.charAt(at);
			int chars = 0;
			while (cur < in.length() && in.charAt(cur) == charAt) {
				chars++;
				cur++;
			}
			Vector<String> perms = findPermutationsSameCharHelper(soFar, chars,
					in.charAt(cur - 1), 0);

//			System.out.println("Got " + perms.size() + " perms");
			Set<String> permTest = new HashSet<String>();
			boolean bad = false;
			for (String perm : perms) {
				if (!permTest.contains(perm)) {
//					System.out.println("Perm: " + perm);
					permTest.add(perm);
				} else {
					System.err.println("Already Contains Perm: " + perm);
					bad = true;
				}
			}
			if (bad)
				System.exit(-1);

			for (String perm : perms) {
				strings.addAll(findPermutations(in, at + chars, perm));
			}
			return strings;
		}
	}

	//The smart method's helper for generating permutations from a character
	static Vector<String> findPermutationsSameCharHelper(String soFar,
			int nrOfCharLeft, char curChar, int charAtInStr) {
		Vector<String> v = new Vector<String>();
		if (nrOfCharLeft == 0) {
			v.add(soFar);
			return v;
		} else {
			for (int i = charAtInStr; i <= soFar.length(); i++) {
				String newStr = soFar.substring(0, i) + curChar
						+ soFar.substring(i, soFar.length());
				v.addAll(findPermutationsSameCharHelper(newStr,
						nrOfCharLeft - 1, curChar, i + 1));
			}
		}
		return v;
	}

	//Below is the 'dumb' method which is used as control; it generates all permutations and stores 
	//'em in a set; we then compare the permutations generated the 'dumb' way with those generated
	// the 'smart' way
	public static Set <String> permutation(String str) {
		return permutation("", str);
	}

	private static Set <String> permutation(String prefix, String str) {
		Set <String> s = new HashSet();
		int n = str.length();
		if (n == 0)
		{
			//System.out.println(prefix);
			s.add(prefix);
		}
		else {
			for (int i = 0; i < n; i++)
				s.addAll(permutation(prefix + str.charAt(i),
						str.substring(0, i) + str.substring(i + 1, n)));
			return s;
		}
		return s;
	}
}

this question main prob is storing of permutate string.because we have to without using hash map and hash table so we have only one efficient option of trie as data structure.
so if no is already exist in trie we will mark those as duplicate not include in our solution.

Hi Guys:
The difference between permutation and combination is that for combination the order does not matter. Remember something similar? Yes, for HashSet order does not matter! So, if your actual permutation implementation returns a ArrayList<ArrayList<Integer>> then for this question all you have to do is to replace the 2nd ArrayList with HashSet, i.e., ArrayList<HashSet<Integer>> . The code should look like this:

public static HashSet<ArrayList<Integer>> permute(ArrayList<Integer> input){
	  if(input.size()==1){
		  HashSet<ArrayList<Integer>> b=new HashSet<ArrayList<Integer>>();
		  b.add(input);
		  return b;
	  }
	  HashSet<ArrayList<Integer>>ret= new HashSet<ArrayList<Integer>>();
	  int len=input.size();
	  for(int i=0;i<len;i++){
		  Integer a = input.remove(i);
		  HashSet<ArrayList<Integer>>temp=permute((ArrayList<Integer>) input.clone());
		  for(ArrayList<Integer> t:temp)
			  t.add(a);
		  ret.addAll(temp);
		  input.add(i, a);
	  }
	  return ret;
  }

this functions prints all the permutations of a given string

import java.util.Hashtable;
import java.io.Console;

public class PermutationsString
{
public static void main(String[] args)
{
System.out.println("Example \"The eyes\" and \"They see\"");
String str1;

Console console = System.console();
str1 = console.readLine("Enter the first string: ");
permutations(str1);
}

private static void permutations(String str)
{
permutation("", str);
}

private static void permutation(String prefix, String str)
{
int n = str.length();
if (n == 0)
{
System.out.println(prefix);
}
else
{
for (int i = 0; i < n; i++)
{
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
}
}

OK when they say without duplicates do they mean no duplicate permutations or no duplicate characters ?
If no duplicate permutations then we should sort the characters and skip the duplicates before recursive call.

#include <stdio.h>
#define N  5


int main(char *argv[],int argc)
{
  char list[5]={'a','b','c','d','e'};
  permute(list,0,N);
  return(0);
}


void permute(char list[],int k, int m)
{
  int i;
  char temp;

  if(k==m)
  {
    /* PRINT A FROM k to m! */
    for(i=0;i<N;i++){printf("%c",list[i]);}
    printf("\n");
  }
  else
  {
     for(i=k;i<m;i++)
     {
        /* swap(a[i],a[m-1]); */ 
        temp=list[i];
        list[i]=list[m-1];
        list[m-1]=temp;

        permute(list,k,m-1);

        /* swap(a[m-1],a[i]); */ 

        temp=list[m-1];
        list[m-1]=list[i];
        list[i]=temp;
       }
  }
}

import java.util.HashSet;

public class StringPermutations {


public String insertAt(String word, char ch, int pos){
String start = word.substring(0, pos);
String end = word.substring(pos);
return start + ch + end;
}

public HashSet<String> getPerms(String str){
if(str == null)
return null;

HashSet<String> list = new HashSet<String>();
if(str.length() == 0){
list.add("");
return list;
}
char first = str.charAt(0);
String remaining = str.substring(1);
HashSet<String> list2 = getPerms(remaining);
for (String string : list2) {
for(int i=0;i<=string.length();i++){
list.add(insertAt(string, first, i));
}
}
return list;
}
public static void main(String[] args) {
StringPermutations sp = new StringPermutations();
HashSet<String> perms = sp.getPerms("AABC");
System.out.println(perms.size());
for (String string : perms) {
System.out.println(string);
}
}
}

static Set<String> map = null;
public static void main(String[] args) {
map = new TreeSet<String>();
permutationOfString(null, new String("1112"));
System.out.println(map);
}

private static void permutationOfString(String soFar, String lefts) {
char[] left = lefts.toCharArray();
if (lefts.length() == 1) {
String s = soFar + lefts;

map.add(s);
return;
}
if (soFar == null) {
soFar = "";
}
for (int i = 0; i < lefts.length(); i++) {
char[] leftChar = new char[lefts.length() - 1];
String str = soFar + left[i];
for(int k = 0; k < i; k++){
leftChar[k] = left[k];
}
for (int j = i; j <= lefts.length() - 2; j++) {
leftChar[j] = left[j+1];
}

System.out.println(str);
System.out.println(leftChar);
permutationOfString(str, new String(leftChar));

}


}

void permutation(char str[], int i, int len)
{
   if(i==len) { cout<<str<<endl; return; }
   
   for(int j=0; j<len; j++)
   { 
      swap(str[i], str[j]);
	  permutaiton(str, i+1, len);
	  swap(str[i], str[j]);
	}  
}

This is the logic now modify this accordingly based on string, array or character or something else.

The recursive solution is straightforward. The iterative solution - look at

gpranjan.wordpress.com/2012/06/08/generating-permutations-an-iterative-approach/

public static void main(String[] args) {

String input = "abc";
StringBuffer inputSB = new StringBuffer(input);
StringBuffer output = new StringBuffer();
printPrem(inputSB,output );
//System.out.print("dfdd");
}

private static void printPrem(StringBuffer input, StringBuffer output) {
if(input.length()==0){
System.out.println(output);
}
else{
for(int i=0;i<input.length();i++)
{
StringBuffer tempi = new StringBuffer(input.toString());
StringBuffer tempo = new StringBuffer(output.toString());
printPrem(tempi.deleteCharAt(i) , tempo.append(input.charAt(i)));
}
}
}