[Question]: A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for array = [1,2,3], the following are all the permutations of array: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]
// TC: O(2N)
// SC: O(1)
func nextPermutation(_ nums: inout [Int]) {
let arrayCount = nums.count
var lhs = -1, rhs = -1, idx = arrayCount - 2
while idx >= 0 {
if nums[idx] < nums[idx + 1] { lhs = idx; break }
idx -= 1
}
if lhs == -1 { nums = nums.reversed(); return }
idx = arrayCount - 1
while idx > lhs {
rhs = idx
if nums[idx] > nums[lhs] { break }
idx -= 1
}
nums.swapAt(lhs, rhs)
nums.replaceSubrange(lhs + 1..<arrayCount, with: nums[lhs + 1...arrayCount - 1].reversed())
}
var permutationArr = [1,2,3];
nextPermutation( &permutationArr);
print("The next permutation is: ", permutationArr )// 1,3,2