Surface, Curve, Algorithm, Geometry, Algebra

Print all permuation of given a string.

void perm(String prefix, String str)
    if str.length == 0
        print prefix
    else{
        for i=0 i < str.length i++
            perm(prefix + str.charAt(i), remove(str, i));
        
String remove(String s, int i)
    StringBuffer sb = new StringBuffer(s);
    return sb.deleteCharAt(i)

$\langle {\large{\color{red}\alpha}} \rangle$ Print all the permutations of an array of characters
This is very popular question for software engineer technical interview.

$\langle {\large{\color{red}\zeta}} \rangle$ Understand the question first
This is very easy question to understand, but it is not so easy to code it up in 45 minutes. Let's try to understand that question.

Given array, char[] array = {'a', 'b', 'c'}, the following are all the permutations
a b c
a c b
c b a
c a b
b a c
b c a

The question is how we algorithmically print out the permutation?

1. If we fix the letter 'a', and permutate['b', 'c']
here is what we got?
a, [b, c]
a, [c, b]

2. we can swap 'a' to each char in [b c] and [c b]
swap{a,b} $\Rightarrow$ b [a c] and swap{a,c} $\Rightarrow$ c [b a]
swap{a,c} $\Rightarrow$ c [a b] and swap{a,b} $\Rightarrow$ b [c a]

[a b c] $\Rightarrow$ [b a c] and [c b a]
[a c b] $\Rightarrow$ [c a b] and [b c a]

all the permutations from 'a', 'b', 'c'
[a b c]
[b a c]
[c b a]
[a c b]
[c a b]
[b c a]

$\langle {\large{\color{red}\psi}} \rangle$ Fix the order of a partial string
Given char 'a' and string "123" and we fix the order of "123", how many different string[lenght=4] we can generate from 'a' and "123"
Please remember the order of "123" is fixed,[e.g "213a" is not allowed]
Obviously we can generate all the strings as following:
a123
1a23
12a3
123a

$\langle {\large{\color{red}\omega}} \rangle$ Use the power of swap[index, index] operation
a123 swap[0, 0] $\Rightarrow$ a123
a123 swap[0, 1] $\Rightarrow$ 1a23
a123 swap[0, 2] $\Rightarrow$ 12a3
a123 swap[0, 3] $\Rightarrow$ 123a

Permutation Algorithm in Java

// generate all permutation from given char[], e.g. ['a', 'b']
    public static void permutation(char[] arr, int index){
        if(index == arr.length){
            Aron.printArray(arr);
        }else{
            if(arr != null){
                int len = arr.length;
                for(int i=index; i < len; i++){
                    Aron.swap(arr, i, index);
                    permutation(arr, index + 1);
                    Aron.swap(arr, i, index);
                } 
            }
        }
    }

Print all permutations in sorted order lexicographically

0. Previous algorithm does not generate sorted order permutations lexicographically.
1. Following algorithm generates sorted order permutations

0. Previous algorithm does not generate sorted order permutations lexicographically.

1. Following algorithm generates sorted order permutations

// permutations are in sorted ordering in lexicographically
    public static void permutationPrefix(String prefix, String str){
        if(str != null){
            if(str.length() == 0){
                Print.p(prefix);
            }else{
                int len = str.length();
                for(int i=0; i< len; i++){
                    String s = str.charAt(i) + "";
                    permutationPrefix(prefix + s, remove(str, i));
                } 
            }
        }
    }
    public static String remove(String str, int index){
        String s = "";
        for(int i=0; i< str.length(); i++){
            if(i != index)
                s += str.charAt(i) + "";
        } 
        return s;
    }

Permutaiton Algorithm in C++

                   
void permutate(int* array, int size, int k) {
        if(k == size) {
            for(int i=0; i < size; i++)
                std::cout< < "["< < array[i]< < "] ";
            std::cout<< std::endl;
        }
        else {
            for(int i=k; i< size; i++) {
                swap(array, i, k);

                for(int j=0; j< k; j++)
                    std::cout< <"[--]";
                std::cout<<"(i="<< i < < ",k="< < k < <")"<< std::endl;
                permutate(array, size, i+1);
                swap(array, i, k);
            }
        }
    }

$C(m, n)$, Given $m$ elements, choose $n$ elements without any repeatition,

1. Use the same prefix permutation algorithm
2. Instead print all paths from the root to the leaf, take all the nodes horizontally, and remove the repeating node

public static void permPrefixChoose(String prefix, String s, int k, HashSet set){
    if(s != null){
        if(s.length() == k){
            set.add(s);
        }else{
            for(int i=0; i< s.length(); i++){
                String str = s.charAt(i) + "";
                permPrefixChoose(prefix + str, dropIndex(i, s), k, set);
            }
        }
    }
}