
"""simple docstring"""



import operator






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					list     ,  SCREAMING_SNAKE_CASE:					bool = False     ,  SCREAMING_SNAKE_CASE:					list | None = None						):






							"""simple docstring"""



							_lowerCAmelCase  	=			operator.lt if reverse else operator.gt
							_lowerCAmelCase  	=			solution or []

							if not arr:
														return solution

							_lowerCAmelCase  	=			[arr.pop(0						)]
							for i, item in enumerate(SCREAMING_SNAKE_CASE						):
														if _operator(SCREAMING_SNAKE_CASE     ,  sublist[-1]						):
																					sublist.append(SCREAMING_SNAKE_CASE						)
																					arr.pop(SCREAMING_SNAKE_CASE						)

    #  merging sublist into solution list
							if not solution:
														solution.extend(SCREAMING_SNAKE_CASE						)
							else:
														while sublist:
																					_lowerCAmelCase  	=			sublist.pop(0						)
																					for i, xx in enumerate(SCREAMING_SNAKE_CASE						):
																												if not _operator(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						):
																																			solution.insert(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						)
																																			break
																					else:
																												solution.append(SCREAMING_SNAKE_CASE						)

							strand_sort(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						)
							return solution


if __name__ == "__main__":
							assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
							assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]








"""simple docstring"""



def 	__snake_case  (    SCREAMING_SNAKE_CASE:					list[int]						):






							"""simple docstring"""



							_lowerCAmelCase  	=			[]
							if len(SCREAMING_SNAKE_CASE						) == 1:
														return [nums.copy()]
							for _ in range(len(SCREAMING_SNAKE_CASE						)						):
														_lowerCAmelCase  	=			nums.pop(0						)
														_lowerCAmelCase  	=			permute(SCREAMING_SNAKE_CASE						)
														for perm in permutations:
																					perm.append(SCREAMING_SNAKE_CASE						)
														result.extend(SCREAMING_SNAKE_CASE						)
														nums.append(SCREAMING_SNAKE_CASE						)
							return result






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					Any						):






							"""simple docstring"""



							def backtrack(SCREAMING_SNAKE_CASE:					Tuple						):
														if start == len(SCREAMING_SNAKE_CASE						) - 1:
																					output.append(nums[:]						)
														else:
																					for i in range(SCREAMING_SNAKE_CASE     ,  len(SCREAMING_SNAKE_CASE						)						):
																												_lowerCAmelCase	,		_lowerCAmelCase  	=			nums[i], nums[start]
																												backtrack(start + 1						)
																												_lowerCAmelCase	,		_lowerCAmelCase  	=			nums[i], nums[start]  # backtrack

							_lowerCAmelCase  	=			[]
							backtrack(0						)
							return output


if __name__ == "__main__":
	import doctest

	# use res to print the data in permute2 function
	_snake_case          =						permutea([1, 2, 3])
	print(res)
	doctest.testmod()






