CareerCup

void print_permutations(const string &s) {
  auto t = s;
  sort(t.begin(), t.end());
  while (true) {
    cout << t << endl;
    if (!next_permutation(t.begin(), t.end())) {
      break;
    }
  }
}

This question has been asked several times... Cost O(n!)

def string_permutations(s):
    if len(s) == 1: return s
    
    solutions = []
    for x in xrange(len(s)):
        solutions.extend(map(lambda r: s[x] + r,
                             string_permutations(s[:x]+s[x+1:])))
    return solutions

public class TestPermutation {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String input = "abc";
		int setPos[] = new int[input.length()];
		getPermutation(input, "", setPos);
	}

	public static void getPermutation(String input, String output,
			int[] setPos) {

		if (null == input | null == output) {
			return;
		}

		if (output.length() == input.length()) {
			System.out.println(output);
			return;
		}

		StringBuilder s = new StringBuilder();
		s.append(output);
		for (int i = 0; i < input.length(); i++) {
			if (setPos[i] == 0) {
				s.append(input.charAt(i));
				setPos[i] = 1;
				getPermutation(input, s.toString(), setPos);
				setPos[i] = 0;
				s.deleteCharAt(output.length());
			}
		}

	}

}

A naive recursionless code is possible:

/* 
A nice trick to find permutations is use integers with base b.
Suppose there is a string of length b, with all unique characters.
Now, that means, the string can be represented as a base b integer.
Permutaions, of the string can be now found by incrementing the number, 
such that all digits are unique.
Now a demonstration:
abc : 3 chars.
3 digit number, and base 3.
The digits are: a:0, b:1, c:2
012 021 102 120 201 210 
--> map_back to -->
abc acb bac bca cab cba 
and we are done.
This can be easily implemented:
*/
def map_back(encoded, string){
  str( encoded.value ,'' ) -> { string[int($.o)] }
}

def permutations( string ) {
    // imagine all chars are unique, else there will be repeatation 
    b = size(string)
    // start with min.
    min_str = '0' + str( [1:b] , '' ) -> { str($.o,b) }
    max_str = min_str ** -1
    min = int(min_str,b,0)
    max = int(max_str,b,0)
    perms = list()
    perms += map_back(min_str,string) 
    for ( x : [ min + 1 : max  ] ){
      str_x = str(x,b)
      if ( size(str_x) < b ){ str_x = '0' + str_x }
      if ( size( set(str_x.value) ) == b ){
          // all different - map it 
          perms += map_back(str_x,string)
      }  
    }  
    perms += map_back(max_str,string) 
}
p = permutations( "abc" )
println(p)

public class Permutations {
	public static void findPermutations(String str){
		permutations("",str);
	}
	
	public static void permutations(String prefix, String str){
		if(str.length()==0){
			System.out.println(prefix);
		}
		for(int i =0;i<str.length();i++){
			permutations(prefix+str.charAt(i),str.substring(0,i)+str.substring(i+1,str.length()));
		}
		
	}
	
	public static void main(String []args){
		findPermutations("abc");
	}
	

}

std::vector<char> out;
std::queue<char> in;

void permute(std::queue<char> &in, std::vector<char> &out) {
    // take from the front, add to out, and then push back into the queue
    if (in.empty()) {
        for(std::vector<char>::iterator it = out.begin(); it != out.end(); ++it) {
            cout << *it;
        }
        cout <<"\n";
        return;
    }
    
    for(int i = 0; i < in.size(); i++) {
        out.push_back(in.front());
        in.pop();
        permute(in, out);
        // the element is not in the in queue. 
        in.push(out.back());
        out.pop_back();
    }
    
}

int main() {
    std::string input("abcd");
    for(int i = 0; i < input.length(); i++) {
        in.push(input[i]);
    }
    permute(in, out);
	// your code goes here
	return 0;
}

or you can use the backtracking with recursion

void swap(string &str, int a, int b) {
    if (a==b){
        return;
    }
    char k = str[a];
    str.replace(a, 1,1, str[b]);
    str.replace(b, 1,1, k);
}

// backtracking
void permu(std::string &str, int index) {
    if (index == str.length()) {
        cout <<str <<"\n";
        return;
    }
    for(int i = index; i < str.length(); i++) {
        swap(str, i,index);
        permu(str, index+1);
        swap(str, index, i);
    }
    
}