CareerCup

You can use this python code to generate all permutation of an array. Complexity O(n!).

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p
            xs[low], xs[i] = xs[i], xs[low]

# generate permuation of array [1,2,3]
for p in permute([1, 2, 3]):
    print p

Approach from "Cracking the coding interview:

public static void main(String[] args) {

		List<String> list = printCombos(new Integer(1234).toString());
		System.out.println(list);
	}

	static List<String> printCombos(String num) {
		
		List<String> methodList = new ArrayList<>();
		
		if (num.length() == 1) {
			methodList.add(num);
			return methodList;
		}
		else{
			int lastIndex = num.length() -1;
			
			char lastIndexItem = num.charAt(lastIndex);
			String firstPart = num.substring(0, lastIndex);
			
			methodList = permutate(printCombos(firstPart), lastIndexItem);
			return methodList;
		}
	}
	
	static List<String> permutate(List<String> firstPart, char lastIndexItem){
		
		List<String> methodList = new ArrayList<>();
		
		for(String s : firstPart){
			
			for(int i = 0; i <= s.length(); i++){
				
				String tempString = new StringBuilder(s).insert(i, lastIndexItem).toString();
				methodList.add(tempString);
			}
		}
		
		return methodList;
	}

create permutations of a number looks easy, but actually we should
take care of special cases. Let's assume, it's about positive
integers (no decimal and no sign). Let's further assume, the integer
may allow repetition of a digit (e.g. 112) and it's desired to get
only unique permutations.

I work with strings here, because it's simpler to understand / work.

The problem becomes: find all unique permutations of a string when
I tolerate leading '0's in input and output.

1) let's assume the string has only unique digits (e.g. "123") in
it. The recursion would look:

recursion(string, pos) = string is a permutation, if pos = 0
                         recurse(swap(string, pos, j), pos - 1), 
                                                for j = pos - 1 to 0

swap(string, i, j): creates a new string that is equal to string with
characters at position i and j exchanged.

the recursion tree would look like this:

pos = 2                          "123"   
                  ------------------------------------
                 /                 |                  \           
pos = 1       "123"              "213"              "312"        
              ------            ------              ------
             /      \          /      \            /      \    
pos = 0   "123"    "132"    "213"    "231"      "312"    "321"

2) ensure uniqueness of the result if the input contains repeating digits:

one way to do that is by maintaining a set of generated results and then
only create a result if it's not already in that set. That's fine, but
looking up the hash table will require to create a hash and thus it
will not behave ideally at runtime to O(n*n!) instead of O(n!)

It's okay, but not elegant. A more elegant approach for me was to better
understand the recursion and prevent duplication out of this understanding.

What happens with the recursion is, that it starts with a suffix (or
prefix in 'illustrations' above) of size 0 and grows that prefix
("", "1", "12", "123") while it recurses on the suffix which creates all
permutations of that suffix. That said, if the prefix repeats,
the suffix, will be a permutation of an other suffix, for the same prefix
that results in duplicates. So, it seems it's enough to avoid repeating
prefixes since for the suffixes all permutations will anyway be created.

the creating of a repeated prefix is simple, just avoid placing the same
character twice to the same position when extending a prefix.

e.g. when extending "" with "1" it's "1" and if I extend it again with "1", I
have a repeating prefix:

pos = 2                          "112"   
                  -----------------------------------------
                 /                 X: 2nd 1                \           
pos = 1       "112"                                       "211"        
              ------                                     ------
             /      \                                   /     X: 2nd 1
pos = 0   "112"    "121"                             "211"

or an other example

pos = 2                          "100"   
                  -----------------------------------------
                 /                 |                      X
pos = 1       "100"              "010"                    
              -----             ------                   
             /    X            /      \               
pos = 0   "100"             "010"    "001"

this will as well create a better runtime in case n > E, where
E is the number of characters in the alphabet (10 in the case of numbers)
and n the length of the string.

Because it's O(max(E^n,n!)), for reasonable small alphabets, for example
binary, this is then O(2^n) vs. O(n!) - an improvement.

the code in python 3

def unique_permutations(str):
    def aux(pos):
        if pos == 0: 
            # create string from byarray and append to results
            result.append("".join(map(lambda x: chr(x), bstr)))
        else:
            used_chars = set() 
            for j in range(pos, -1, -1):
                if bstr[j] in used_chars: 
                    continue
                used_chars.add(bstr[j])
                bstr[pos], bstr[j] = bstr[j], bstr[pos] # swap
                aux(pos - 1)
                bstr[pos], bstr[j] = bstr[j], bstr[pos] # swap back
        
    result = []
    bstr = bytearray(str, 'ascii')

    aux(len(bstr) - 1)
    return result

print(unique_permutations("123"))
print(unique_permutations("111"))
print(unique_permutations("100"))
print(unique_permutations("1010101"))
print(unique_permutations("0000001"))

#output:
#['123', '213', '132', '312', '321', '231']
#['111']
#['100', '010', '001']
#['1010101', '0110101', '1100101', '1001101', '0101101', '0011101', '1011001', '0111001', \
'1101001', '1110001', '1010011', '0110011', '1100011', '1001011', '0101011', '0011011', \
'1000111', '0100111', '0010111', '0001111', '1010110', '0110110', '1100110', '1001110', \
'0101110', '0011110', '1011010', '0111010', '1101010', '1110010', '1011100', '0111100', \
'1101100', '1110100', '1111000']
#['0000001', '0000010', '0000100', '0001000', '0010000', '0100000', '1000000']

#include <iostream>
#include <set>
using namespace std;

set<string>hs;
set<string>::iterator it;

string s;
unsigned int count=0;

void perm(string toP,unsigned int i)
{
	if(i==s.size()){
		count++;
		hs.insert(toP);
//		cout<<toP<<"\n";
		return;
	}
	string tt=toP;
	for(unsigned int j=0;j<=i;j++){
		tt=toP;
		tt.insert(tt.begin()+j,s[i]);
		perm(tt,i+1);
	}
}

int main()
{
	cin>>s;
	perm("",0);

	for(it = hs.begin(); it!=hs.end() ; ++it){
		cout<<*it<<" ";
	}

	return 0;
}

5390

#include <iostream>
#include <set>
using namespace std;

set<string>hs;
set<string>::iterator it;

string s;
unsigned int count=0;

void perm(string toP,unsigned int i)
{
if(i==s.size()){
count++;
hs.insert(toP);
// cout<<toP<<"\n";
return;
}
string tt=toP;
for(unsigned int j=0;j<=i;j++){
tt=toP;
tt.insert(tt.begin()+j,s[i]);
perm(tt,i+1);
}
}

int main()
{
cin>>s;
perm("",0);

for(it = hs.begin(); it!=hs.end() ; ++it){
cout<<*it<<" ";
}

return 0;
}