Сделано с использованием реального кода на Java, Python, C++, Go и JavaScript

Перестановка — фундаментальное понятие в математике. Перевод математической концепции в компьютерные программы поначалу труден, но как только вы поймете шаблон и логику, а также несколько раундов практики, алгоритмы перестановки кода станут второй натурой.

Перестановки с различными элементами

Подумайте о том, как построить все перестановки массива [a,b,c,d]. Пусть каждый элемент по очереди становится первым элементом перестановки. Если a является первым элементом, то остальная часть перестановки может быть сформирована путем перестановки [b,c,d] ; если b является первым элементом, то остальная часть перестановки может быть сформирована путем перестановки [a,c,d] ; и так далее. Если мы закрепим первые два элемента, скажем, b и d, то остальную часть перестановки можно будет сформировать путем перестановки [a,c]. Поскольку перестановка большего массива может быть выполнена путем закрепления префиксного подмножества элементов, а затем перестановки остальной части массива, это во всех отношениях похоже на рекурсию. На самом деле рекурсия — это именно то, что мы будем использовать.

Ниже представлен код на разных языках, чтобы представить визуальный эффект того, как внутренний алгоритм одинаков для разных языковых реализаций. В каждой реализации вот список сходств:

  • Набор перестановок называется res, а текущая перестановка, над которой мы работаем, называется perm.
  • Рекурсивная функция dfs используется для вычисления перестановки подмассива, начиная с индекса i.
  • Каждая рекурсия начинается с проверки условия завершения i==len(nums). Если условие истинно, то получается перестановка perm и добавляется к результату res. Обратите внимание, что perm необходимо глубоко скопировать в res.
  • В каждой рекурсии цикл FOR используется для перебора элементов nums, начиная с индекса i. Функция swap используется для помещения k-го элемента nums на его i-ое место и замены их обратно, когда эта ветвь рекурсии выполнена. Это хороший трюк для алгоритмов перестановки.
  • Функция permute инициализирует perm и res, а также вызывает dfs с i=0 (начиная с первого элемента).

В Java:

void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void dfs(int[] nums, int i, List<List<Integer>> res, List<Integer> perm) {
    if (i == nums.length) {
        res.add(new ArrayList<>(perm));
        return;
    }

    for (int k = i; k < nums.length; ++k) {
        swap(nums, i, k);
        perm.add(nums[i]);
        dfs(nums, i+1, res, perm);
        perm.remove(perm.size()-1);
        swap(nums, i, k);
    }
}

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> perm = new ArrayList<>();
    dfs(nums, 0, res, perm);
    return res;
}

В Питоне:

def permute(self, nums: List[int]) -> List[List[int]]:
    def swap(i, j):
        nums[i], nums[j] = nums[j], nums[i]
    def dfs(i, perm):
        if i == len(nums):
            res.append(perm[:])
            return
        for k in range(i, len(nums)):
            swap(i, k)
            perm.append(nums[i])
            dfs(i+1, perm)
            perm.pop()
            swap(i, k)
    res = []
    dfs(0, [])
    return res

In C++:

void dfs(vector<int>& nums, int i, 
vector<vector<int>>& res, vector<int> &perm) {
    if (i == nums.size()) {
        res.push_back(perm);
        return;
    }
    for (int j = i; j < nums.size(); ++j) {
        perm.push_back(nums[j]);
        swap(nums[i],nums[j]);
        dfs(nums, i+1, res, perm);
        swap(nums[i],nums[j]);
        perm.pop_back();
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> perm;
    dfs(nums, 0, res, perm);
    return res;
}

In Go:

func permute(nums []int) [][]int {
    res := [][]int{}
    perm := []int{}
    var dfs func(int)
    dfs = func(i int) {
        swap := func(i int, j int) {
            nums[i], nums[j] = nums[j], nums[i]
        }    
        if i == len(nums) {
            cpy := make([]int, len(perm))
            copy(cpy, perm)
            res = append(res, cpy)
            return
        }
        for k := i; k < len(nums); k++ {
            swap(i, k);
            perm = append(perm, nums[i])
            dfs(i+1)
            perm = perm[:len(perm)-1]
            swap(i, k);
        }
    }
    dfs(0)
    return res
}

В JavaScript:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let res = []
    let perm = []
    function dfs(i) {
        function swap(i, j) {
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
        }
        if (i == nums.length) {
            res.push([...perm])
            return
        }
        for (let k = i; k < nums.length; ++k) {
            swap(i,k)
            perm.push(nums[i])
            dfs(i+1)
            perm.pop()
            swap(i,k)
        }        
    }
    dfs(0)
    return res
};

Уникальные перестановки с возможными повторяющимися элементами

Каркас алгоритма в этом случае очень похож на случай без дублирующихся элементов. Единственное необходимое усовершенствование — это размещение kth элемента на ith месте. Мы используем хеш-набор, чтобы проверить, было ли это значение уже на iместе в предыдущих FOR итерациях цикла, только запускаем рекурсию вниз, когда iместо находится совершенно новое значение. В приведенном ниже коде, поскольку по сравнению с предыдущим случаем изменена только функция dfs, остальные функции опущены.

В Java:

void dfs(int[] nums, int i, List<List<Integer>> res, List<Integer> perm) {
    if (i == nums.length) {
        res.add(new ArrayList<>(perm));
        return;
    }
    HashSet<Integer> seen = new HashSet<>();
    for (int k = i; k < nums.length; ++k) {
        if (seen.contains(nums[k])) continue;
        seen.add(nums[k]);
        swap(nums, i, k);
        perm.add(nums[i]);
        dfs(nums, i+1, res, perm);
        perm.remove(perm.size()-1);
        swap(nums, i, k);
    }
}

В Питоне:

def dfs(i, perm):
    if i == len(nums):
        res.append(perm[:])
        return
    seen = set()
    for k in range(i, len(nums)):
        if nums[k] in seen:
            continue
        seen.add(nums[k])
        swap(i, k)
        perm.append(nums[i])
        dfs(i+1, perm)
        perm.pop()
        swap(i, k)

In C++:

void dfs(vector<int>& nums, int i, 
vector<vector<int>>& res, vector<int>& perm) {
    if (i == nums.size()) {
        res.push_back(perm);
        return;
    }
    unordered_set<int> seen;
    for (int k = i; k < nums.size(); ++k) {
        // same value in perm[i] cannot happen again
        if (seen.find(nums[k]) != seen.end()) continue;
        // kth element in nums as ith element in perm
        seen.insert(nums[k]);
        swap(nums[i], nums[k]);
        perm.push_back(nums[i]);
        dfs(nums, i+1, res, perm);
        perm.pop_back();
        swap(nums[i], nums[k]);
    }
}

In Go:

dfs = func(i int) {
    swap := func(i int, j int) {
        nums[i], nums[j] = nums[j], nums[i]
    }    
    if i == len(nums) {
        cpy := make([]int, len(perm))
        copy(cpy, perm)
        res = append(res, cpy)
        return
    }
    seen := make(map[int]bool)
    for k := i; k < len(nums); k++ {
        if _, ok := seen[nums[k]]; ok {
            continue
        }
        seen[nums[k]] = true
        swap(i, k);
        perm = append(perm, nums[i])
        dfs(i+1)
        perm = perm[:len(perm)-1]
        swap(i, k);
    }
}

В JavaScript

function dfs(i) {
    function swap(i, j) {
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }
    if (i == nums.length) {
        res.push([...perm])
        return
    }
    const seen = new Set()
    for (let k = i; k < nums.length; ++k) {
        if (seen.has(nums[k])) continue
        seen.add(nums[k])
        swap(i,k)
        perm.push(nums[i])
        dfs(i+1)
        perm.pop()
        swap(i,k)
    }        
}

Упражняться

Наконец, освоившись с алгоритмами, потренируйтесь с любимым языком программирования здесь и здесь.