Сделано с использованием реального кода на 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 };
Уникальные перестановки с возможными повторяющимися элементами
Каркас алгоритма в этом случае очень похож на случай без дублирующихся элементов. Единственное необходимое усовершенствование — это размещение k
th элемента на i
th месте. Мы используем хеш-набор, чтобы проверить, было ли это значение уже на 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) } }
Упражняться
Наконец, освоившись с алгоритмами, потренируйтесь с любимым языком программирования здесь и здесь.