Print the two possible permutations from a given sequence | Function to check if the sequence is concatenation of two permutations or not ; Computing the sum of all the elements in the array ; Computing the prefix sum for all the elements in the array ; Iterating through the i from lengths 1 to n - 1 ; Sum of first i + 1 elements ; Sum of remaining n - i - 1 elements ; Lengths of the 2 permutations ; Checking if the sums satisfy the formula or not ; Function to print the two permutations ; Print the first permutation ; Print the second permutation ; Function to find the two permutations from the given sequence ; If the sequence is not a concatenation of two permutations ; Find the largest element in the array and set the lengths of the permutations accordingly ; Driver code
def checkPermutation ( arr , n ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE DEDENT prefix = [ 0 for i in range ( n + 1 ) ] NEW_LINE prefix [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] + arr [ i ] NEW_LINE DEDENT for i in range ( n - 1 ) : NEW_LINE INDENT lsum = prefix [ i ] NEW_LINE rsum = sum - prefix [ i ] NEW_LINE l_len = i + 1 NEW_LINE r_len = n - i - 1 NEW_LINE if ( ( ( 2 * lsum ) == ( l_len * ( l_len + 1 ) ) ) and ( ( 2 * rsum ) == ( r_len * ( r_len + 1 ) ) ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def printPermutations ( arr , n , l1 , l2 ) : NEW_LINE INDENT for i in range ( l1 ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( " " , end ▁ = ▁ " " ) ; NEW_LINE for i in range ( l1 , n , 1 ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT def findPermutations ( arr , n ) : NEW_LINE INDENT if ( checkPermutation ( arr , n ) == False ) : NEW_LINE INDENT print ( " Not ▁ Possible " ) NEW_LINE return NEW_LINE DEDENT l1 = 0 NEW_LINE l2 = 0 NEW_LINE l1 = max ( arr ) NEW_LINE l2 = n - l1 NEW_LINE s1 = set ( ) NEW_LINE s2 = set ( ) NEW_LINE for i in range ( l1 ) : NEW_LINE INDENT s1 . add ( arr [ i ] ) NEW_LINE DEDENT for i in range ( l1 , n ) : NEW_LINE INDENT s2 . add ( arr [ i ] ) NEW_LINE DEDENT if ( len ( s1 ) == l1 and len ( s2 ) == l2 ) : NEW_LINE INDENT printPermutations ( arr , n , l1 , l2 ) NEW_LINE DEDENT else : NEW_LINE INDENT temp = l1 NEW_LINE l1 = l2 NEW_LINE l2 = temp NEW_LINE printPermutations ( arr , n , l1 , l2 ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 1 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1 , 10 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE findPermutations ( arr , n ) NEW_LINE DEDENT