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), removeIndex(i, str));

$\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);
                                }
                            }
                        }
                    }

Combination or (m Choose n) in Haskell

        Explanation:
        1 2 3 4

        1 2 3 4      2 3 4        3 4         4           []
        1 (c(n-1))   2 (c(n-1))   3(c(n-1))   4(c(n-1))   
          2 3 4        3 4          4
            3 4          4
              4

        combination::Int -> [a] -> [[a]]
        combination 0 _  = [[]]
        combination n cx = [ x:cy | x:cx' <- L.tails cx
                              ,cy <- combination (n-1) cx']

Combination in Java, Facebook interview question

      public static void combination(List prefix, List ls, Integer n){
          if( n == 0){
             printList(prefix);
          }else{
             for(int i = 0; i < ls.size(); i++){
                var rs = drop(i + 1, ls);
                var a = ls.get(i);
                combination(append(prefix, a), rs, n - 1);
             }
          }
      }