Все перестановки строки

Решение: Все перестановки строки

Основная идея

Используем рекурсию с backtracking:

1. Для каждой позиции пробуем все символы
2. Берём символ, рекурсивно генерируем перестановки остальных
3. Возвращаемся назад (backtrack) и пробуем следующий

Рекурсивная реализация (наиболее эффективная)

func permutations(s string) []string {
    var result []string
    permute([]rune(s), 0, &result)
    return result
}

func permute(chars []rune, start int, result *[]string) {
    // Базовый случай: достигли конца
    if start == len(chars)-1 {
        *result = append(*result, string(chars))
        return
    }
    
    // Рекурсия: пробуем каждый символ в позиции start
    for i := start; i < len(chars); i++ {
        // Swap: выносим символ на позицию start
        chars[start], chars[i] = chars[i], chars[start]
        
        // Рекурсия для оставшихся символов
        permute(chars, start+1, result)
        
        // Backtrack: возвращаем символ обратно
        chars[start], chars[i] = chars[i], chars[start]
    }
}

Сложность:

• Время: O(n! * n) — n! перестановок, каждую строим за O(n)
• Память: O(n! * n) для хранения результатов

Пример работы для "abc"

Основной вызов: permute([a,b,c], 0)

i=0: swap(0,0)='a' фиксирован
  permute([a,b,c], 1)
    i=1: swap(1,1)='b' фиксирован
      permute([a,b,c], 2)
        start==2: добавляем "abc"
    i=2: swap(1,2), becomes [a,c,b]
      permute([a,c,b], 2)
        start==2: добавляем "acb"
      swap back → [a,b,c]

i=1: swap(0,1), becomes [b,a,c]
  permute([b,a,c], 1)
    i=1: swap(1,1)='a' фиксирован
      permute([b,a,c], 2)
        start==2: добавляем "bac"
    i=2: swap(1,2), becomes [b,c,a]
      permute([b,c,a], 2)
        start==2: добавляем "bca"
      swap back → [b,a,c]
  swap back → [a,b,c]

i=2: swap(0,2), becomes [c,b,a]
  permute([c,b,a], 1)
    i=1: swap(1,1)='b' фиксирован
      permute([c,b,a], 2)
        start==2: добавляем "cba"
    i=2: swap(1,2), becomes [c,a,b]
      permute([c,a,b], 2)
        start==2: добавляем "cab"
      swap back → [c,b,a]
  swap back → [a,b,c]

Результат: [abc, acb, bac, bca, cba, cab]

Итеративная реализация (средняя сложность)

func permutations(s string) []string {
    chars := []rune(s)
    n := len(chars)
    result := []string{string(chars)}
    
    // Используем лексикографический порядок
    for {
        // Найти наибольший индекс i, где chars[i] < chars[i+1]
        i := n - 2
        for i >= 0 && chars[i] >= chars[i+1] {
            i--
        }
        
        // Если такого индекса нет, это последняя перестановка
        if i < 0 {
            break
        }
        
        // Найти наибольший индекс j > i, где chars[j] > chars[i]
        j := n - 1
        for j > i && chars[j] <= chars[i] {
            j--
        }
        
        // Swap chars[i] и chars[j]
        chars[i], chars[j] = chars[j], chars[i]
        
        // Reverse символы от i+1 до конца
        reverse(chars, i+1, n-1)
        
        // Добавляем новую перестановку
        result = append(result, string(chars))
    }
    
    return result
}

func reverse(chars []rune, start, end int) {
    for start < end {
        chars[start], chars[end] = chars[end], chars[start]
        start++
        end--
    }
}

Преимущество: Даёт перестановки в лексикографическом порядке.

Нерекурсивная с каналом (для больших данных)

func permutations(s string) []string {
    var result []string
    chars := []rune(s)
    n := len(chars)
    
    // Используем факториальную систему счисления
    perm := make([]int, n)
    for i := range perm {
        perm[i] = i
    }
    
    for {
        // Построить текущую перестановку
        current := make([]rune, n)
        used := make([]bool, n)
        
        for i := 0; i < n; i++ {
            // Пропустить уже использованные
            count := 0
            for j := 0; j < n; j++ {
                if !used[j] && count == perm[i] {
                    current[i] = chars[j]
                    used[j] = true
                    break
                }
                if !used[j] {
                    count++
                }
            }
        }
        
        result = append(result, string(current))
        
        // Увеличить факториальный счётчик
        carry := 1
        for i := n - 1; i >= 0 && carry > 0; i-- {
            perm[i] += carry
            if perm[i] < n-i {
                carry = 0
            } else {
                perm[i] = 0
            }
        }
        
        if carry > 0 {
            break
        }
    }
    
    return result
}

Простая версия с использованием слайсов

func permutations(s string) []string {
    if len(s) == 0 {
        return []string{""}
    }
    if len(s) == 1 {
        return []string{s}
    }
    
    var result []string
    
    // Для каждого символа
    for i := 0; i < len(s); i++ {
        // Берём i-й символ
        current := string(s[i])
        
        // Остальные символы
        remaining := s[:i] + s[i+1:]
        
        // Рекурсивно генерируем перестановки остальных
        for _, perm := range permutations(remaining) {
            result = append(result, current+perm)
        }
    }
    
    return result
}

Плюсы: Легко понять, чистый код Минусы: Больше аллокаций памяти (создание новых строк на каждом уровне)

Пример использования

func main() {
    fmt.Println(permutations("ab"))
    // Выведет: [ab ba] (порядок может отличаться)
    
    fmt.Println(permutations("abc"))
    // Выведет: [abc acb bac bca cab cba]
}

Сравнение методов

Ключевые моменты

• Swap backtrack лучше: Наиболее эффективен по памяти и скорости
• Генерируется ровно n! перестановок
• Порядок не определён: Если важен порядок, используй лексикографический
• Для больших строк: О(n!) памяти неизбежна
• Unicode: Используй []rune для корректной работы с многобайтовыми символами

Рекомендация

Для интервью используй swap backtrack версию — это показывает понимание алгоритмов и оптимизации.