050_next_permutation.sio

//@ run-pass
// HumanEval 050: Next Permutation
//
// Generate the next lexicographically greater permutation in-place.
// If the array is the last permutation (descending), wrap to the
// first (ascending). Algorithm:
// 1. Find largest i such that arr[i] < arr[i+1] (pivot)
// 2. Find largest j > i such that arr[j] > arr[i]
// 3. Swap arr[i] and arr[j]
// 4. Reverse arr[i+1..n-1]
// If no pivot exists, just reverse the whole array.

struct Buf { data: [i64; 256] }

fn reverse_range(buf: &!Buf, start: i64, end: i64) with Mut, Panic, Div {
    var lo = start
    var hi = end
    while lo < hi {
        let tmp = buf.data[lo]
        buf.data[lo] = buf.data[hi]
        buf.data[hi] = tmp
        lo = lo + 1
        hi = hi - 1
    }
}

fn next_permutation(buf: &!Buf, n: i64) with Mut, Panic, Div {
    if n <= 1 { return }

    // Step 1: Find pivot (rightmost i where buf[i] < buf[i+1])
    var pivot: i64 = 0 - 1
    var i: i64 = n - 2
    while i >= 0 {
        if buf.data[i] < buf.data[i + 1] {
            pivot = i
            break
        }
        i = i - 1
    }

    if pivot == 0 - 1 {
        // No pivot: last permutation, wrap to first
        reverse_range(buf, 0, n - 1)
        return
    }

    // Step 2: Find rightmost j > pivot where buf[j] > buf[pivot]
    var j: i64 = n - 1
    while j > pivot {
        if buf.data[j] > buf.data[pivot] {
            break
        }
        j = j - 1
    }

    // Step 3: Swap pivot and j
    let tmp = buf.data[pivot]
    buf.data[pivot] = buf.data[j]
    buf.data[j] = tmp

    // Step 4: Reverse elements after pivot
    reverse_range(buf, pivot + 1, n - 1)
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [1, 2, 3] -> [1, 3, 2]
    var b1 = Buf { data: [0; 256] }
    b1.data[0] = 1
    b1.data[1] = 2
    b1.data[2] = 3
    next_permutation(&!b1, 3)
    assert(b1.data[0] == 1)
    assert(b1.data[1] == 3)
    assert(b1.data[2] == 2)

    // Test 2: [3, 2, 1] -> [1, 2, 3] (wrap around)
    var b2 = Buf { data: [0; 256] }
    b2.data[0] = 3
    b2.data[1] = 2
    b2.data[2] = 1
    next_permutation(&!b2, 3)
    assert(b2.data[0] == 1)
    assert(b2.data[1] == 2)
    assert(b2.data[2] == 3)

    // Test 3: [1, 3, 2] -> [2, 1, 3]
    var b3 = Buf { data: [0; 256] }
    b3.data[0] = 1
    b3.data[1] = 3
    b3.data[2] = 2
    next_permutation(&!b3, 3)
    assert(b3.data[0] == 2)
    assert(b3.data[1] == 1)
    assert(b3.data[2] == 3)

    // Test 4: [1, 1, 5] -> [1, 5, 1]
    var b4 = Buf { data: [0; 256] }
    b4.data[0] = 1
    b4.data[1] = 1
    b4.data[2] = 5
    next_permutation(&!b4, 3)
    assert(b4.data[0] == 1)
    assert(b4.data[1] == 5)
    assert(b4.data[2] == 1)

    // Test 5: single element [7] -> [7] (unchanged)
    var b5 = Buf { data: [0; 256] }
    b5.data[0] = 7
    next_permutation(&!b5, 1)
    assert(b5.data[0] == 7)

    // Test 6: [1, 2, 3, 4] -> [1, 2, 4, 3]
    var b6 = Buf { data: [0; 256] }
    b6.data[0] = 1
    b6.data[1] = 2
    b6.data[2] = 3
    b6.data[3] = 4
    next_permutation(&!b6, 4)
    assert(b6.data[0] == 1)
    assert(b6.data[1] == 2)
    assert(b6.data[2] == 4)
    assert(b6.data[3] == 3)

    // Test 7: [2, 3, 1] -> [3, 1, 2]
    var b7 = Buf { data: [0; 256] }
    b7.data[0] = 2
    b7.data[1] = 3
    b7.data[2] = 1
    next_permutation(&!b7, 3)
    assert(b7.data[0] == 3)
    assert(b7.data[1] == 1)
    assert(b7.data[2] == 2)

    println("050_next_permutation: ALL TESTS PASSED")
    0
}