chapter_backtracking/permutations_problem/

[giscus[bot]]

chapter_backtracking/permutations_problem/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_backtracking/permutations_problem/

[qyh20011114]

大佬写得真的简单易懂,牛!!!

[krahets]

谢谢鼓励奥

[lt421]

对应力扣题目：
https://leetcode.cn/problems/VvJkup/
https://leetcode.cn/problems/7p8L0Z/

[lt421]

评论错了本来要在根评论下面评论的，发现删不了。。。

[zhuasdfg]

这个duplicated有点难，每轮选择都有一个，duplicated设置在for循环遍历前面实在是太讲究了

[WhiteRhinos]

每次固定数组的一位值
我自己想了一个,是根据全排列个数公式的来的,不过效率不高,就是求n个数的全排列先求前n-1个数的全排列在将第n个数插入全排列中

  public static void main(String[] args)
    {
        int[] arr = {1, 1, 2};
        allQuery(arr, 0, arr.length - 1);
    }

    public static void allQuery(int[] arr, int start, int end)
    {
        if (start == end)
        {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int i = start; i <= end; i++)
        {
            // 选取一个固定在start位置
            change2(arr, start, i);
            allQuery(arr, start + 1, end);
            // 恢复
            change2(arr, start, i);
        }

    }

    public static void change(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void change2(int[] arr, int i, int j)
    {
        if (i == j)
        {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

[krahets]

Hi ，分享代码可以用

```java
code...
```

的格式奥，有高亮

[lyl625760]

不重复元素全排列的那个代码，是不是时间复杂度也挺高？ 至少是 n*n! 吧 ？ 因为每次都需要遍历choices数组

[krahets]

是的，全排列的时间复杂度是“排列数量 $O(n!)$” 乘以 “记录排列所需时间 $O(n)$” 。

[xuanjiYUU]

假如有一nums[1,2,3,1]，那么当nums[0]使用后被放入哈希表，直接判断元素不存在于哈希表就可以完成剪枝掉重复元素和表达selected了吧？

[krahets]

用哈希表代替 selected 也可以的，不过要用索引来做 key 而不应该用元素值，这样在有重复元素时也能保证正确性

[ChinaYong]

你说的情况得另找一个哈希表，一个哈希表存放当前状态已经存放了哪些数值，一个存放当前状态进行一轮数字选择时已经添加了哪些值。（你的意思应该是想用一个哈希表做两种剪枝吧）

[noobcodemaker]

“相等元素剪枝：每轮选择（即每个开启的 backtrack 函数）都包含一个 duplicated 。它记录的是在遍历中哪些元素已被选择过，作用是保证相等元素只被选择一次。”
感觉这里面的‘’它记录的是在遍历中哪些元素已被选择过……”改成“它记录的是本轮对应的位置上哪些元素已被选择过，作用是保证每一轮要处理的位置上相同元素只被选择一次”会不会更好理解一些，因为duplicated的作用是在每一轮中体现的，而不是在整个遍历过程中

[krahets]

Hi，谢谢建议！这里的“遍历”指的就是当前轮中的 for 遍历哈～你提到的“整个遍历过程”指的应该是“搜索解空间”的过程。

[caolib]

可以加一个回溯和分支界限的对比吗

[chen-xiao-yu]

是不是可以这么理解

• 重复节点剪枝是看这条路径上有没有重复节点，是剪的子节点，
• 相等元素剪枝是看和前面也有的路径是不是重复的，剪掉的兄弟节点。
  所以说判断重复节点的数组需要在每次递归的方法里面传递， 而判断相等元素的数组不用在递归方法里面传递，只需要在遍历兄弟节点的循环外定义。

[VegetableChicken504]

我在c#的实现中看到了如下写法，但我没有找到相关文档，这种方式是否有误

HashSet<int> duplicated = [];

[hpstory]

Hi @VegetableChicken504， 这是C# 12新引入的特性集合表达式，欢迎更新.NET 8 SDK体验 : )

[zhuiyueya]

你好，请问“假设元素两两之间互不相同，则 𝑛 个元素共有 𝑛! 种排列（阶乘）；在记录结果时，需要复制长度为 𝑛 的列表，使用 𝑂(𝑛) 时间。因此时间复杂度为 𝑂(𝑛!𝑛) 。”这里的“需要赋值长度为n的列表”指的是if (state.size() == choices.size()) {
res.push_back(state);
return;
}里的res.push_back(state);操作么？

[krahets]

Hi，是的，这一步隐式地将 state 复制了一份，并添加进 res

[Fulin-Gao]

请问duplicated的O(n^2)空间复杂度如何推算呢？

[krahets]

Hi，考虑 choices = [1, 2, ..., n] ，那么会形成一个高度为 n 的递归树。观察递归树中右下角的节点，存在 n 个未返回递归函数，每个递归函数中包含一个 duplicated ，长度分别为 n, n-1, ..., 2, 1 ，因此空间复杂度为 $O(n^2)$

[maxkwok]

如果需要排列数字的离散程度很大，duplicated的size将需要很大，会造成很大的空间浪费；如果使用哈希表将会有所缓解。这样的理解正确吗？

[krahets]

@maxkwok 是的，当不知道数字范围时，一般用哈希表（文中也使用的是哈希表）

[Temmp1e]

duplicated = set[int]() 这不是创造一个集合吗， 不是哈希表吧

[Fulin-Gao]

当成只有键，没有值的哈希

[RENHJa]

有相同元素的情况，可不可以写个函数先把重复的元素剔除，然后就和第一种情况一样了，这样会不会更简单一些？

[krahets]

不可以，例如 [1, 2, 2] 删除重复后为 [1, 2] ，得到的全排列为 [1, 2], [2, 1] 。这并不是 [1, 2, 2] 的全排列

[RENHJa]

噢噢，对喔，不好意思，是我思考的少了

[linvsCode]

go语言版本都没有在记录解刹车，还让它多秏了点油

[Tianyu-Huang-letsgo]

着实是茅塞顿开了，
剪枝1是通过在递归函数签名中导入《记录数组》，故在整条递归链中都可以记录哪个元素被遍历过，且随着树节点的返回需要把记录清楚。
剪枝2是在当前层状态下引入的，可以看作一个当前层的属性，也就是说每一层（兄弟节点）都有独立的duplicated数组用于记录哪个元素被选过了，之前的状态完全是由祖先节点决定的，也就是一样的，这样就可以剪掉一样的兄弟节点。

[Tianyu-Huang-letsgo]

把记录清楚->把记录清除

[480284856]

hello，K神，我记得你说空间复杂度统计的是暂存与输出空间，那么这个全排列问题的空间复杂度统计应该要算res的大小吧？

[yangping4271]

写的真好，感谢

[akfc58]

两种剪枝方式介绍的深入浅出，写的真好！！

[MambaFly]

两种剪枝实现的目的不同！
剪枝1：selected数组，防止同一个元素重复选择，否则就不是排列了，所以selected数组的长度和原数组长度相等，并且是贯穿递归过程，并且回溯时需要还原的
剪枝2：duplicated集合，防止相等元素重复选择，否则最后会得到重复排列，只在当前一层生效

[beitso]

duplicated.find(choice) == duplicated.end()
不应该是不相等吗？当前元素没有出现过，所以才继续执行下面的操作，出现过了，即出现重复元素，不是被剪枝了吗，也就不执行下面的操作了

[MaikieMaiky]

您提出了一个很好的问题。让我解释一下 unordered_set 的 find 方法和这行代码的工作原理：

1. unordered_set 的 find 方法：
   当 find 方法没有找到元素时，它会返回 unordered_set::end() 迭代器。这个迭代器指向容器的末尾，表示搜索已经到达集合的末端而没有找到匹配的元素。
   判断条件的工作原理：
   duplicated.find(choice) == duplicated.end() 这个表达式在 choice 不在 duplicated 集合中时为真。

• 如果 choice 在集合中，find 返回指向该元素的迭代器，不等于 end()。
• 如果 choice 不在集合中，find 返回 end() 迭代器，等于 end()。

3. 完整条件的含义：
   !selected[i] && duplicated.find(choice) == duplicated.end()
   这个条件检查两件事：

• !selected[i]：确保当前索引 i 的元素还没被选择。
• duplicated.find(choice) == duplicated.end()：确保当前的 choice 在这一轮递归中还没被使用过。
  因此，这行代码有效地判断了一个元素是否可以被选择：它既没有在全局范围内被使用（由 selected 数组控制），也没有在当前递归层级中被重复选择（由 duplicated 集合控制）。
  这种方式既简洁又高效，是 C++ 中常用的判断元素是否存在于集合中的惯用写法。

[beitso]

懂了，谢谢佬

[Asce-ops]

def backtrack(
    state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
    """回溯算法：全排列 I"""
    # 当状态长度等于元素数量时，记录解
    if len(state) == len(choices):
        res.append(list(state))
        return
    # 遍历所有选择
    for i, choice in enumerate(choices):
        # 剪枝：不允许重复选择元素
        if not selected[i]:
            # 尝试：做出选择，更新状态
            selected[i] = True
            state.append(choice)
            # 进行下一轮选择
            backtrack(state, choices, selected, res)
            # 回退：撤销选择，恢复到之前的状态
            selected[i] = False
            state.pop()

def permutations_i(nums: list[int]) -> list[list[int]]:
    """全排列 I"""
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res

里为什么把res.append(list(state))改成res.append(state)结果就不对了呢，想不明白呀，state本来不就是个列表吗？

[Asce-ops]

明白了，引用和复制的区别，按照代码流程state最后肯定会变成一个空数组

[syutengu]

学习笔记，js版。

  /* 全排列，有重复元素，回溯法，可指定子集长度 */
  // @param {arr | str} nums
  // @param {int} [len=nums.length]
  // @returns {array}
  // @example 'aabb',2 -> ['a','a'],['a','b'],['b','a'],['b','b']
  function permute_backtracking(arr, len = arr.length) {
    // 可接受字符串输入
    const d = typeof arr === 'string' ? arr.split('') : arr
    const [
      res,
      idxes, //计数各元素，以确保"全局范围内"同一元素不被重复使用
      p, //具体排列（子集）
    ] = [[], [], []]
    backtrack(len)
    return res

    function backtrack(len) {
      // 计数各值，以确保"当前递归内"同一值不被重复展开递归
      const vals = new Set()
      /* 当状态长度等于元素数量时，记录解 */
      if (p.length === len) {
        return res.push([...p])
      }

      /* 遍历所有选择 */
      d.map((e, i) => {
        /* 剪枝 不允许重复选择同一元素，且不允许选择同值元素 */
        if (idxes[i] || vals.has(e)) return
        /* 尝试 做出选择，更新状态 */
        idxes[i] = (idxes[i] ?? 0) + 1
        vals.add(e)
        p.push(e)
        backtrack(len)
        /* 回退 撤销选择，恢复状态 */
        idxes[i]--
        // vals.delete(e) //vals只存活于当前栈帧(stack frame)内，不会影响前后递归，故不必
        p.pop()
      })
    }
  }

[JFWind-0323]

C#框架的泛型优化（扩展实现了全排列），作者说完形填空就可以，个人认为如果要追求在极致的框架下完型填空，那么必须解开类型的枷锁，否则换成树或者链表或者其他类型又要重新复制粘贴一份
public class FullPermutation
{
private int n;

public FullPermutation()
{
    n = int.Parse(Console.ReadLine());
    List<int> nums = new List<int>();
    for (int i = 0; i < n; i++)
    {
        nums.Add(i + 1);
    }
    
    foreach (var item in PermutationsI(nums))
    {
        var result = string.Join(" ", item);
        Console.WriteLine(result);
    }
}

/* 全排列 I */
List<List<int>> PermutationsI(List<int> nums)
{
    List<List<int>> res = new List<List<int>>();
    bool[] selected = new bool[n];
    Backtrack([], nums, selected, res);
    return res;
}

/* 回溯算法框架 */

/* 判断当前状态是否为解 */
bool IsSolution<TState>(List<TState> state)
{
    return state.Count == n;
}

/* 记录解 */
void RecordSolution<T>(List<T> state, List<List<T>> res)
{
    res.Add(new List<T>(state));
}

/* 判断在当前状态下，该选择是否合法 */
bool IsValid<T>(List<T> state, List<T> choices, T choice, bool[] selected, int index)
{
    return !selected[index];
}

/* 更新状态 */
void MakeChoice<T>(List<T> state, List<T> choices, T choice, bool[] selected, int index)
{
    selected[index] = true;
    state.Add(choice);
}

/* 恢复状态 */
void UndoChoice<T>(List<T> state, List<T> choices, T choice, bool[] selected, int index)
{
    selected[index] = false;
    state.RemoveAt(state.Count - 1);
}

void Backtrack<T>(List<T> state, List<T> choices, bool[] selected, List<List<T>> res)
{
    // 检查是否为解
    if (IsSolution(state))
    {
        // 记录解
        RecordSolution(state, res);
    }

    // 遍历所有选择
    for (var i = 0; i < choices.Count; i++)
    {
        var choice = choices[i];
        // 剪枝：检查选择是否合法
        if (IsValid(state, choices, choice, selected, i))
        {
            // 尝试：做出选择，更新状态
            MakeChoice(state, choices, choice, selected, i);
            // 进行下一轮选择
            Backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            UndoChoice(state, choices, choice, selected, i);
        }
    }
}

}