Trova la prossima permutazione in ordine alfabetico.

next_permutation.js

function partial_reverse (arr, i, j)
{
    var tmp;

    j--;
    while (i < j) {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++; j--;
    }

    return arr;
}


// Trova la prossima permutazione in ordine alfabetico.
//
// Es: > next_permutation(["a", "b", "c"]);
//     ["a", "c", "b"]
function next_permutation (arr)
{
    var i, j, tmp;

    // se l'array ha un solo elemento o è vuoto, ritorno l'array stesso.
    if (arr.length <= 1)
        return arr;

    // L'algoritmo è il seguente:
    //
    // 1. devo trovare la più lunga coda dell'array che è ordinata in modo
    //    decrescente. Es. in `3, 2, 5, 3, 1`, la coda è `5, 3, 1`
    // 2. devo scambiare l'elemento subito precedente alla coda (nell'esempio
    //    è il `2`) con l'elemento subito più grande appartenente alla coda
    //    (nell'esempio è `3`). Quindi `3, 2, 5, 3, 1` diventa `3, 3, 5, 2, 1`
    // 3. devo rovesciare l'ordine degli elementi della coda, in modo che
    //    siano in ordine crescente (al momento sono già ordinati in ordine
    //    decrescente). Es. `3, 3, 5, 2, 1` diventa `3, 3, 1, 2, 5`.
    // 4. `3, 3, 1, 2, 5` è la permutazione successiva di `3, 2, 5, 3, 1`.
    // 
    // Quando al punto 1. la coda più lunga risulta essere l'intero array,
    // allora sono arrivato all'ultima permutazione possibile e ritorno
    // `undefined`.

    // Cerco la coda piu' lunga ordinata in modo decrescente.
    // `i` vale 1 o più.
    i = arr.length - 1;
    while (i > 0 && arr[i] < arr[i - 1])
        i--;

    // Se sono arrivato all'ultima permutazione possibile rovescio l'array per
    // riportarlo alla prima permutazione.
    if (i === 0) {
        return arr.reverse();
    } else {
        i--;
    }

    // Cerco l'elemento appartenente alla coda che è più grande dell'elemento
    // arr[i].
    j = arr.length - 1;
    while (arr[i] >= arr[j])
        j--;

    // Scambio arr[i] con arr[j]
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;

    // Infine, rovescio la coda
    partial_reverse(arr, i + 1, arr.length);
    return arr;
}