Permutaciones (backtracking)

def permutar(letras, usada, actual, res):
    """Backtracking que no repite permutaciones aunque haya letras repetidas: las letras van ordenadas y una
    letra igual a la anterior solo se elige si la anterior ya está usada en esta rama."""
    if len(actual) == len(letras):
        res.append("".join(actual))
        return
    for i in range(len(letras)):
        if usada[i]:
            continue
        if i > 0 and letras[i] == letras[i - 1] and not usada[i - 1]:   # esa letra ya se probó aquí
            continue
        usada[i] = True
        actual.append(letras[i])
        permutar(letras, usada, actual, res)
        actual.pop()
        usada[i] = False


def permutaciones(s):
    letras = sorted(s)
    res = []
    permutar(letras, [False] * len(letras), [], res)
    return res


for s in ["ABC", "AAB", "ROMA"]:
    p = permutaciones(s)
    lista = " ".join(p) if len(p) <= 6 else " ".join(p[:6]) + " …"
    print(f"{s}: {len(p)} → {lista}")

/** Backtracking que no repite permutaciones aunque haya letras repetidas: las letras van ordenadas y una
    letra igual a la anterior solo se elige si la anterior ya está usada en esta rama. */
function permutar(letras, usada, actual, res) {
    if (actual.length === letras.length) {
        res.push(actual.join(""));
        return;
    }
    for (let i = 0; i < letras.length; i++) {
        if (usada[i]) continue;
        if (i > 0 && letras[i] === letras[i - 1] && !usada[i - 1]) continue;   // esa letra ya se probó aquí
        usada[i] = true;
        actual.push(letras[i]);
        permutar(letras, usada, actual, res);
        actual.pop();
        usada[i] = false;
    }
}

function permutaciones(s) {
    const letras = [...s].sort();
    const res = [];
    permutar(letras, new Array(letras.length).fill(false), [], res);
    return res;
}

for (const s of ["ABC", "AAB", "ROMA"]) {
    const p = permutaciones(s);
    const lista = p.length <= 6 ? p.join(" ") : p.slice(0, 6).join(" ") + " …";
    console.log(`${s}: ${p.length} → ${lista}`);
}

using System;
using System.Collections.Generic;
using System.Text;

class Program {
    /// Backtracking que no repite permutaciones aunque haya letras repetidas: las letras van ordenadas y una
    /// letra igual a la anterior solo se elige si la anterior ya está usada en esta rama.
    static void Permutar(char[] letras, bool[] usada, StringBuilder actual, List<string> res) {
        if (actual.Length == letras.Length) {
            res.Add(actual.ToString());
            return;
        }
        for (int i = 0; i < letras.Length; i++) {
            if (usada[i]) continue;
            if (i > 0 && letras[i] == letras[i - 1] && !usada[i - 1]) continue;   // esa letra ya se probó aquí
            usada[i] = true;
            actual.Append(letras[i]);
            Permutar(letras, usada, actual, res);
            actual.Length--;
            usada[i] = false;
        }
    }

    static List<string> Permutaciones(string s) {
        char[] letras = s.ToCharArray();
        Array.Sort(letras);
        var res = new List<string>();
        Permutar(letras, new bool[letras.Length], new StringBuilder(), res);
        return res;
    }

    static void Main() {
        foreach (string s in new[] { "ABC", "AAB", "ROMA" }) {
            var p = Permutaciones(s);
            string lista = p.Count <= 6 ? string.Join(" ", p) : string.Join(" ", p.GetRange(0, 6)) + " …";
            Console.WriteLine(
quot;{s}: {p.Count} → {lista}");
        }
    }
}

<?php
/** Backtracking que no repite permutaciones aunque haya letras repetidas: las letras van ordenadas y una
    letra igual a la anterior solo se elige si la anterior ya está usada en esta rama. */
function permutar(array $letras, array &$usada, string $actual, array &$res): void {
    if (strlen($actual) == count($letras)) {
        $res[] = $actual;
        return;
    }
    for ($i = 0; $i < count($letras); $i++) {
        if ($usada[$i]) continue;
        if ($i > 0 && $letras[$i] === $letras[$i - 1] && !$usada[$i - 1]) continue;   // esa letra ya se probó aquí
        $usada[$i] = true;
        permutar($letras, $usada, $actual . $letras[$i], $res);
        $usada[$i] = false;
    }
}

function permutaciones(string $s): array {
    $letras = str_split($s);
    sort($letras);
    $usada = array_fill(0, count($letras), false);
    $res = [];
    permutar($letras, $usada, "", $res);
    return $res;
}

foreach (["ABC", "AAB", "ROMA"] as $s) {
    $p = permutaciones($s);
    $lista = count($p) <= 6 ? implode(" ", $p) : implode(" ", array_slice($p, 0, 6)) . " …";
    echo "$s: " . count($p) . " → $lista\n";
}

def siguiente(a):
    """Convierte a en la siguiente permutación en orden lexicográfico; False si ya era la última."""
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:                # 1. el último que tiene a su derecha uno mayor
        i -= 1
    if i < 0:
        return False
    j = len(a) - 1
    while a[j] <= a[i]:                               # 2. el menor de su derecha que le supera
        j -= 1
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])                   # 3. su derecha, de menor a mayor
    return True


def texto(a, sep):
    return sep.join(str(x) for x in a)


a = [1, 2, 3]
todas = [texto(a, "")]
while siguiente(a):
    todas.append(texto(a, ""))
print("Todas, en orden: " + " ".join(todas))
b = [1, 3, 5, 4, 2]
antes = texto(b, " ")
siguiente(b)
print(f"Después de {antes} va {texto(b, ' ')}")
c = [3, 2, 1]
print("¿Hay alguna después de 3 2 1? " + ("sí" if siguiente(c) else "no: es la última"))

/** Convierte a en la siguiente permutación en orden lexicográfico; false si ya era la última. */
function siguiente(a) {
    let i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;           // 1. el último que tiene a su derecha uno mayor
    if (i < 0) return false;
    let j = a.length - 1;
    while (a[j] <= a[i]) j--;                         // 2. el menor de su derecha que le supera
    [a[i], a[j]] = [a[j], a[i]];
    for (let x = i + 1, y = a.length - 1; x < y; x++, y--)   // 3. su derecha, de menor a mayor
        [a[x], a[y]] = [a[y], a[x]];
    return true;
}

const texto = (a, sep) => a.join(sep);

const a = [1, 2, 3];
const todas = [];
do todas.push(texto(a, "")); while (siguiente(a));
console.log("Todas, en orden: " + todas.join(" "));
const b = [1, 3, 5, 4, 2];
const antes = texto(b, " ");
siguiente(b);
console.log(`Después de ${antes} va ${texto(b, " ")}`);
const c = [3, 2, 1];
console.log("¿Hay alguna después de 3 2 1? " + (siguiente(c) ? "sí" : "no: es la última"));

using System;
using System.Collections.Generic;

class Program {
    /// Convierte a en la siguiente permutación en orden lexicográfico; false si ya era la última.
    static bool Siguiente(int[] a) {
        int i = a.Length - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;               // 1. el último que tiene a su derecha uno mayor
        if (i < 0) return false;
        int j = a.Length - 1;
        while (a[j] <= a[i]) j--;                             // 2. el menor de su derecha que le supera
        (a[i], a[j]) = (a[j], a[i]);
        Array.Reverse(a, i + 1, a.Length - i - 1);            // 3. su derecha, de menor a mayor
        return true;
    }

    static string Texto(int[] a, string sep) => string.Join(sep, a);

    static void Main() {
        int[] a = { 1, 2, 3 };
        var todas = new List<string>();
        do todas.Add(Texto(a, "")); while (Siguiente(a));
        Console.WriteLine("Todas, en orden: " + string.Join(" ", todas));
        int[] b = { 1, 3, 5, 4, 2 };
        string antes = Texto(b, " ");
        Siguiente(b);
        Console.WriteLine(
quot;Después de {antes} va {Texto(b, " ")}");
        int[] c = { 3, 2, 1 };
        Console.WriteLine("¿Hay alguna después de 3 2 1? " + (Siguiente(c) ? "sí" : "no: es la última"));
    }
}

<?php
/** Convierte $a en la siguiente permutación en orden lexicográfico; false si ya era la última. */
function siguiente(array &$a): bool {
    $i = count($a) - 2;
    while ($i >= 0 && $a[$i] >= $a[$i + 1]) $i--;     // 1. el último que tiene a su derecha uno mayor
    if ($i < 0) return false;
    $j = count($a) - 1;
    while ($a[$j] <= $a[$i]) $j--;                    // 2. el menor de su derecha que le supera
    [$a[$i], $a[$j]] = [$a[$j], $a[$i]];
    for ($x = $i + 1, $y = count($a) - 1; $x < $y; $x++, $y--)   // 3. su derecha, de menor a mayor
        [$a[$x], $a[$y]] = [$a[$y], $a[$x]];
    return true;
}

function texto(array $a, string $sep): string {
    return implode($sep, $a);
}

$a = [1, 2, 3];
$todas = [];
do $todas[] = texto($a, ""); while (siguiente($a));
echo "Todas, en orden: " . implode(" ", $todas) . "\n";
$b = [1, 3, 5, 4, 2];
$antes = texto($b, " ");
siguiente($b);
echo "Después de $antes va " . texto($b, " ") . "\n";
$c = [3, 2, 1];
echo "¿Hay alguna después de 3 2 1? " . (siguiente($c) ? "sí" : "no: es la última") . "\n";