Finding Permutation

permutation.py

#/////////////////////////////////////////////////////
#---------------Permutations-------------------------
#///////////////////////////////////////////////////

'''
1st attempt

Logic : 
    This is a recursive solution
    This method will only work with natural numbers

    Suppose we have given [1,2,3,4]
    we will start with index 0

    [ 1 , 2 , 3 , 4]
      -- [2 , 3 , 4]    // Fix first index. We will make all permutations which will start with 1
         --  [3 , 4]    // Fix second index also. We will make all permutations which start with 2 
              _____     // Now we have 2 numbers. We can make permutations of these 2. We will get 34 and 43
                        // Now we go back to what we have fixed previously. i.e 2 
                        // Place 2 in front of 34 and 43. Then we will get 234,243.
                        // that is all permutation we can make starting with 2 
         [3 , 4 , 2]    // Now we will put 2 at the last
         --  [4 , 2]    // Fix 3 and make permutation of remaining two elements. We will get 24,42
                        // go back to last fixed position and place that element in front of permutations we got
                        // Then we will have 324,342
         [4 , 2 , 3]    // Move 3 to the last
         --  [2 , 3]    // FIx 4 and make permutation of remaining, we will get 23 , 32
                        // go back to last fixed position and place that element in front of permutations we got
                        // we will get 423,432
                        // we have seen all 3 elements. Now return back to the last fixed position
                        // Place that element in front of all permutations we got
                        // We will get 1234,1243,1324,1342,1423,1432
                        // These are all permutations which will start with 1
    [ 2 , 3 , 4 , 1]    // Now move 1 back
                        // Repeat the process
    
    Permutation (array, n)  // where n is length of array

    Permutation([1,2,3,4],4)
        result = []
        I = 0
        ---------------------->| Permutation([2,3,4],3)
                               |    result = []
                               |     I = 0
                               |     ---------------------------------> | Permutation ([3,4],2)
                               |                                        |     n = 2
                               |            <---------------------------| return ([34,43])
                               |    result = [234,243]
                               |    array = [3,4,2]
                               |
                               |    i = 1
                               |       -------------------------------> | Permutation ([4,2],2)
                               |                                        |     n = 2
                               |             <--------------------------| return ([42,24])
                               |    result = [234,243,342,324]
                               |    array = [4,2,3]
                               |
                               |    i = 2
                               |      --------------------------------> | Permutation ([2,3],2)
                               |                                        |     n = 2
                               |             <--------------------------| return ([23,32])
                               |    result = [234,243,342,324,423,432]
            <------------------| return result
        result = [1234,1243,1342,1324,1423,1432]
        array = [2,3,4,1]

        i = 1
            ------------------> | Permutation ([3,4,1],3)
                                |   result = []
                                |       I = 0
                                |          --------------------> | Permutation ([4,1],2)


        ////////// Similar to I =0 same process will repeat ///////////////////

    at last we will get  

    [1234, 1243, 1342, 1324, 1423, 1432, 2341, 2314, 2413, 2431, 2134, 2143,
     3412, 3421, 3124, 3142, 3241, 3214, 4123, 4132, 4231, 4213, 4312, 4321]
'''

def permutation1(array,n):
    result = []
    if n == 2 :
        result.append(array[0]*10**(n-1) + array[1])
        result.append(array[1]*10**(n-1) + array[0])
        return result
    for i in range(n):
        perm = permutation1(array[1:],n-1)
        temp = array[0]*10**(n-1)
        for j in perm:
            result.append(temp + j)
        x = array.pop(0)
        array.append(x)
    return result

print(permutation1([1,2,3],3))
print("--------------------------------------------")

'''
Second Attempt
    Logic is same as above approch is different 

    Permutation(array,l,h)       // here l is lower bound and h is upper bound
    Permutation([1,2,3,4],0,4)
        result = []
        i = 0
        ---------------------->| Permutation([1,2,3,4],1,4)
                               |    result = []
                               |     i = 1
                               |    swap(i,l)
                               |     ---------------------------------> | Permutation ([1,2,3,4],2,4)
                               |                                        |     l - h = 2
                               |                                        |   swap (l,h-1)  // save
                               |                                        |   swap (l,h-1)  // Save
                               |            <---------------------------| return [[1,2,4,3],[1,2,3,4]]
                               |    result = [ [1,2,4,3] , [1,2,3,4] ]
                               |    swap(i,l)
                               |
                               |    i = 2
                               |    swap (i,l)
                               |       -------------------------------> | Permutation ([1,3,2,4],2,4)
                               |                                        |      l - h = 2
                               |                                        |   swap (l,h-1)  // save
                               |                                        |   swap (l,h-1)  // Save
                               |             <--------------------------| return [[1,3,4,2],[1,3,2,4]]
                               |
                               |    result = [ [1,2,4,3] , [1,2,3,4] , [1,3,4,2] , [1,3,2,4] ]
                               |    swap(i,l)
                               |
                               |    i = 3
                               |    swap(i,l)
                               |      --------------------------------> | Permutation ([1,4,3,2],2,4)
                               |                                        |     l - h = 2
                               |                                        |   swap (l,h-1)  // save
                               |                                        |   swap (l,h-1)  // Save
                               |             <--------------------------| return [[1,4,2,3],[1,4,3,2]]
                               |
                               |    result = [ [1,2,4,3] , [1,2,3,4] , [1,3,4,2] , [1,3,2,4] , [1,4,2,3] , [1,4,3,2] ]
                               |    swap(i,l)
            <------------------| return result

        result = [ [1,2,4,3] , [1,2,3,4] , [1,3,4,2] , [1,3,2,4] , [1,4,2,3] , [1,4,3,2] ]

        i = 1
        swap (i,l)
            ------------------> | Permutation ([2,1,3,4],1,3)
                                |   result = []
                                |       i = 1
                                |       swap(l,i)
                                |          --------------------> | Permutation ([1,2,3,4],2,4)

    ///////////////////// Similar Process ///////////////////////////////////////////////////

    At last we will get
    [ [1, 2, 4, 3], [1, 2, 3, 4], [1, 3, 4, 2], [1, 3, 2, 4], [1, 4, 3, 2], [1, 4, 2, 3], [4, 1, 3, 2], 
      [4, 1, 2, 3], [4, 2, 3, 1], [4, 2, 1, 3], [4, 3, 2, 1], [4, 3, 1, 2], [1, 3, 2, 4], [1, 3, 4, 2], 
      [1, 4, 2, 3], [1, 4, 3, 2], [1, 2, 4, 3], [1, 2, 3, 4], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], 
      [4, 3, 2, 1], [4, 1, 3, 2], [4, 1, 2, 3] ]

'''

def permutation2(array,l,h):
    result = []
    if (h-l) == 2 :
        array[l],array[h-1] = array[h-1], array[l]
        result.append(array[:])
        array[l],array[h-1] = array[h-1], array[l]
        result.append(array[:])
        return result
    for i in range(l,h):
        array[l],array[i] = array[i], array[l]
        result.extend(permutation2(array,l+1,h))
        array[l],array[i] = array[i], array[l]
    return result

print(permutation2([1,2,3,4],0,4))
print('-----------------------------------------------------------------')


'''
Third Attempt

Same logic as above. Just the difference is except swapping in less

'''

def permutation3(array,l,h):
    result = []
    if (h-l) == 1 :
        result.append(array[:])
    else:
        for i in range(l,h):
            array[l],array[i] = array[i], array[l]
            result.extend(permutation3(array,l+1,h))
            array[l],array[i] = array[i], array[l]
    return result

print(["".join(x) for x in permutation3(['a','b','c','d'],0,4)])

print('--------------------------------------------------------------------------')


'''
Fourth Attempt:
    Same logic as previous
    But below code will word with string array only
'''
given = 'abcd'
given1 = 1234
def permutation4(array,l,h):
    result = []
    if (h-l) == 1 :
        result.append("".join(array))
    else:
        for i in range(l,h):
            array[l],array[i] = array[i], array[l]
            result.extend(permutation4(array,l+1,h))
            array[l],array[i] = array[i], array[l]
    return result

print([int(x) for x in permutation4(list(str(given1)),0,len(str(given1)))])
print('-------------------------------------------------------------------------------')
print(permutation4(list(str(given)),0,len(str(given))))