一些ruby代码片段5 图论算法和排列组合

这里把图论问题和排列组合放在一起因为两者都经常用到回溯算法。

图论算法

以下主要基于邻接表（图的最简表示方式），简单清晰无封装。

图论算法说明

1. DFS 深度优先搜索 ：一条路走到黑，再回头走其他路（递归实现）
2. BFS 广度优先搜索 ：一层一层往外扩散（队列实现）
3. 连通性 无向图连通性判断：无向图能从起点访问所有节点就是连通的
4. Dijkstra 单源最短路径（带权无负权）：带权图的最短路径（不能有负权重）
5. 拓扑排序（有向无环图 DAG）：有向无环图的依赖顺序（比如任务先后、课程先修）
6. A star 搜索的时候可以用，以距离作为启发函数。
7. 最小生成树（MST）：Prim 算法、Kruskal 算法
8. Bellman-Ford（支持负权边、可判负环）
9. Floyd-Warshall（多源最短路径）
10. 有向图判环
11. 强连通分量（Kosaraju / Tarjan）
12. 欧拉路径/回路
13. 二分图判定

深度优先搜索 (DFS)

require 'set'

# 无向无权图（邻接表：键=节点，值=相邻节点数组）
graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D', 'E'],
  'C' => ['A', 'F'],
  'D' => ['B'],
  'E' => ['B', 'F'],
  'F' => ['C', 'E']
}

# 深度优先搜索 DFS（递归实现，最简）
def dfs(graph, node, visited = Set.new)
  return if visited.include?(node) # 已访问则跳过
  visited.add(node)
  print "#{node} " # 输出访问顺序
  graph[node].each { |neighbor| dfs(graph, neighbor, visited) } # 递归遍历邻居
end

puts "DFS 遍历顺序（起点 'A'）："
dfs(graph, 'A')
puts

运行结果 A B C D E F

广度优先搜索 (BFS)

require 'set'

# 无向无权图（邻接表：键=节点，值=相邻节点数组）
graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D', 'E'],
  'C' => ['A', 'F'],
  'D' => ['B'],
  'E' => ['B', 'F'],
  'F' => ['C', 'E']
}

# 广度优先搜索 BFS（队列实现，最简）
def bfs(graph, start)
  visited = Set.new
  queue = [start] # 数组模拟队列
  visited.add(start)

  while !queue.empty?
    node = queue.shift # 队首出队
    print "#{node} "
    # 遍历未访问的邻居，入队
    graph[node].each do |neighbor|
      unless visited.include?(neighbor)
        visited.add(neighbor)
        queue << neighbor
      end
    end
  end
end

puts "BFS 遍历顺序（起点 'A'）："
bfs(graph, 'A')
puts

运行结果 A B C D E F

无向图连通性判断

require 'set'

# 无向无权图（邻接表：键=节点，值=相邻节点数组）
graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D', 'E'],
  'C' => ['A', 'F'],
  'D' => ['B'],
  'E' => ['B', 'F'],
  'F' => ['C', 'E']
}

# 深度优先搜索 DFS（递归实现，最简）
def dfs(graph, node, visited = Set.new)
  return if visited.include?(node) # 已访问则跳过
  visited.add(node)
  graph[node].each { |neighbor| dfs(graph, neighbor, visited) } # 递归遍历邻居
  visited # 返回访问集合
end

# 判断无向图是否连通（所有节点能被访问到=连通）
def connected?(graph, start)
  visited = dfs(graph, start)
  visited.size == graph.keys.size
end

puts "无向图是否连通（起点 'A'）：#{connected?(graph, 'A')}"

运行结果 true

Dijkstra 单源最短路径（带权无负权）

require 'set'

# 带权无向图（邻接表：节点 => {邻居 => 权重}）
graph = {
  'A' => {'B' => 1, 'C' => 4},
  'B' => {'A' => 1, 'C' => 2, 'D' => 5},
  'C' => {'A' => 4, 'B' => 2, 'D' => 1},
  'D' => {'B' => 5, 'C' => 1}
}

# Dijkstra 算法：求起点到所有节点的最短路径
def dijkstra(graph, start)
  # 初始化距离：起点=0，其余=无穷大
  distances = Hash.new(Float::INFINITY)
  distances[start] = 0
  visited = Set.new

  while visited.size < graph.keys.size
    # 选「未访问且距离最小」的节点
    current = graph.keys.reject { |k| visited.include?(k) }.min_by { |k| distances[k] }
    break if distances[current] == Float::INFINITY # 无连通节点，直接退出
    visited.add(current)

    # 更新邻居的最短距离
    graph[current].each do |neighbor, weight|
      next if visited.include?(neighbor)
      new_dist = distances[current] + weight
      distances[neighbor] = new_dist if new_dist < distances[neighbor]
    end
  end
  distances
end

puts "Dijkstra 最短路径（起点 'A'）："
p dijkstra(graph, 'A')

运行结果 {“A”=>0, “B”=>1, “C”=>3, “D”=>4}

拓扑排序（有向无环图 DAG）

# 有向无环图
graph = {
  'A' => ['C'],
  'B' => ['C', 'D'],
  'C' => ['E'],
  'D' => ['F'],
  'E' => ['F'],
  'F' => []
}

# 拓扑排序：输出节点的先后依赖顺序
def topological_sort(graph)
  # 计算每个节点的入度
  in_degree = Hash.new(0)
  graph.each_value { |neighbors| neighbors.each { |n| in_degree[n] += 1 } }
  # 入度为0的节点入队列
  queue = graph.keys.select { |k| in_degree[k] == 0 }
  topo_order = []

  while !queue.empty?
    node = queue.shift
    topo_order << node
    # 邻居入度-1，入度为0则入队
    graph[node].each do |neighbor|
      in_degree[neighbor] -= 1
      queue << neighbor if in_degree[neighbor] == 0
    end
  end

  # 校验：排序长度=节点数 → 无环；否则有环
  topo_order.size == graph.keys.size ? topo_order : "图有环，无法排序"
end

puts "拓扑排序结果："
p topological_sort(graph)

运行结果 ["A", "B", "C", "D", "E", "F"]

Prim 算法（最小生成树）

从一个点出发，每次选连接已选集合的最小权边，贪心扩展。

# 带权无向图
graph = {
  'A' => { 'B' => 2, 'C' => 3 },
  'B' => { 'A' => 2, 'C' => 1, 'D' => 1 },
  'C' => { 'A' => 3, 'B' => 1, 'D' => 4 },
  'D' => { 'B' => 1, 'C' => 4 }
}

def prim(graph, start)
  visited = Set.new([start])
  mst = []
  total = 0

  while visited.size < graph.size
    min_edge = nil
    min_weight = Float::INFINITY

    visited.each do |u|
      graph[u].each do |v, w|
        next if visited.include?(v)
        if w < min_weight
          min_weight = w
          min_edge = [u, v, w]
        end
      end
    end

    break unless min_edge
    u, v, w = min_edge
    visited.add(v)
    mst << min_edge
    total += w
  end

  { edges: mst, total_weight: total }
end

puts "=== Prim 最小生成树"
p prim(graph, 'A')

---

Kruskal 算法（最小生成树）

按边权从小到大选，用并查集避免环。

class UnionFind
  def initialize(nodes)
    @parent = nodes.to_h { |x| [x, x] }
  end

  def find(x)
    @parent[x] == x ? x : (@parent[x] = find(@parent[x]))
  end

  def union(x, y)
    rx, ry = find(x), find(y)
    return false if rx == ry
    @parent[ry] = rx
    true
  end
end

# 边列表 [u, v, weight]
edges = [
  ['A','B',2], ['A','C',3],
  ['B','C',1], ['B','D',1],
  ['C','D',4]
]

def kruskal(nodes, edges)
  uf = UnionFind.new(nodes)
  sorted = edges.sort_by { |u,v,w| w }
  mst = []
  total = 0

  sorted.each do |u, v, w|
    if uf.union(u, v)
      mst << [u, v, w]
      total += w
      break if mst.size == nodes.size - 1
    end
  end

  { edges: mst, total_weight: total }
end

puts "\n=== Kruskal 最小生成树"
p kruskal(['A','B','C','D'], edges)

---

Bellman-Ford（单源最短路径，支持负权）

可处理负权边，能检测负权环。

def bellman_ford(edges, nodes, start)
  dist = Hash.new(Float::INFINITY)
  dist[start] = 0

  # 松弛 n-1 次
  (nodes.size - 1).times do
    edges.each do |u, v, w|
      if dist[u] + w < dist[v]
        dist[v] = dist[u] + w
      end
    end
  end

  # 检查负环
  has_negative_cycle = false
  edges.each do |u, v, w|
    if dist[u] + w < dist[v]
      has_negative_cycle = true
      break
    end
  end

  { distances: dist, has_negative_cycle: has_negative_cycle }
end

puts "\n=== Bellman-Ford"
bf = bellman_ford(edges, ['A','B','C','D'], 'A')
p bf[:distances]
puts "负环? #{bf[:has_negative_cycle]}"

---

Floyd-Warshall（多源最短路径）

适合节点少的图，直接 DP 松弛所有点对。

def floyd_warshall(graph)
  nodes = graph.keys
  dist = {}

  # 初始化
  nodes.each do |i|
    dist[i] = {}
    nodes.each { |j| dist[i][j] = i == j ? 0 : Float::INFINITY }
    graph[i].each { |j, w| dist[i][j] = w }
  end

  # 三层循环松弛
  nodes.each do |k|
    nodes.each do |i|
      nodes.each do |j|
        if dist[i][k] + dist[k][j] < dist[i][j]
          dist[i][j] = dist[i][k] + dist[k][j]
        end
      end
    end
  end

  dist
end

puts "\n=== Floyd-Warshall 多源最短路径"
p floyd_warshall(graph)

---

典型输出

=== Prim 最小生成树
{:edges=>[["A", "B", 2], ["B", "C", 1], ["B", "D", 1]], :total_weight=>4}

=== Kruskal 最小生成树
{:edges=>[["B", "C", 1], ["B", "D", 1], ["A", "B", 2]], :total_weight=>4}

=== Bellman-Ford
{"A"=>0, "B"=>2, "C"=>3, "D"=>3}
负环? false

=== Floyd-Warshall 多源最短路径
{"A"=>{"A"=>0, "B"=>2, "C"=>3, "D"=>3}, ...}

排列组合

在 Ruby 中实现排列组合算法分两种场景：

1. 开发实用版：直接使用 Ruby 数组内置的原生方法（简洁高效，推荐生产环境使用）；
2. 原理理解版：手动递归/回溯实现（适合学习算法核心逻辑）。

先明确核心区别：

• 排列 (Permutation)：有序，[1,2] 和 [2,1] 是两个不同结果；
• 组合 (Combination)：无序，[1,2] 是唯一结果。

---

排列组合数的计算

排列组合的数学公式依赖阶乘，先实现工具方法：

# 计算 n 的阶乘 n!
def factorial(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

# 计算排列数 P(n,k) = n!/(n-k)! （从n个元素选k个的排列总数）
def permutation_count(n, k)
  return 0 if k < 0 || k > n
  factorial(n) / factorial(n - k)
end

# 计算组合数 C(n,k) = n!/(k!*(n-k)!) （从n个元素选k个的组合总数）
def combination_count(n, k)
  return 0 if k < 0 || k > n
  factorial(n) / (factorial(k) * factorial(n - k))
end

# 测试
puts "5! = #{factorial(5)}"
puts "P(5,2) = #{permutation_count(5, 2)}"
puts "C(5,2) = #{combination_count(5, 2)}"

---

Ruby 内置的排列组合方法

Ruby 数组原生提供了完备的排列组合方法。

arr = [1, 2, 3]

# ========== 1. 排列 (有序) ==========
# 全排列
p arr.permutation.to_a  # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
# 选 2 个元素的排列
p arr.permutation(2).to_a # [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]

# ========== 2. 组合 (无序) ==========
# 选 2 个元素的组合
p arr.combination(2).to_a # [[1,2],[1,3],[2,3]]

# ========== 3. 可重复的排列/组合 ==========
# 可重复排列（元素可重复选择）
p arr.repeated_permutation(2).to_a # [[1,1],[1,2],...,[3,3]]
# 可重复组合
p arr.repeated_combination(2).to_a # [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]

# ========== 4. 带重复元素的去重排列 ==========
dup_arr = [1, 1, 2]
p dup_arr.permutation.to_a.uniq # 去重后：[[1,1,2],[1,2,1],[2,1,1]]

Python 也内置了。

也可以用回溯算法手动实现（理解核心逻辑，面试/学习必备）：

递归实现排列组合

组合（无重复元素）

组合不重复、不回头，递归时从下一个索引开始遍历：

# 从数组 arr 中选 k 个元素的所有组合
def combinations(arr, k)
  result = []
  # 回溯函数：start=起始索引，current=当前组合
  backtrack = lambda do |start, current|
    # 终止条件：组合长度达标，存入结果
    result << current.dup if current.size == k

    (start...arr.size).each do |i|
      current << arr[i]       # 选择元素
      backtrack.call(i + 1, current) # 递归（不回头，i+1）
      current.pop             # 回溯（撤销选择）
    end
  end

  backtrack.call(0, [])
  result
end

# 测试
p combinations([1,2,3], 2) # [[1,2],[1,3],[2,3]]

排列（无重复元素）

排列有序，需标记已使用的元素：

# 数组的全排列
def permutations(arr)
  result = []
  used = Array.new(arr.size, false) # 标记元素是否被使用

  backtrack = lambda do |current|
    result << current.dup if current.size == arr.size

    arr.each_with_index do |num, i|
      next if used[i] # 跳过已使用的元素
      used[i] = true
      current << num
      backtrack.call(current)
      current.pop
      used[i] = false # 回溯
    end
  end

  backtrack.call([])
  result
end

# 从数组中选 k 个元素的排列
def permutations_k(arr, k)
  result = []
  used = Array.new(arr.size, false)

  backtrack = lambda do |current|
    result << current.dup if current.size == k

    arr.each_with_index do |num, i|
      next if used[i]
      used[i] = true
      current << num
      backtrack.call(current)
      current.pop
      used[i] = false
    end
  end

  backtrack.call([])
  result
end

# 测试
p permutations([1,2,3])        # 全排列
p permutations_k([1,2,3], 2)   # 选2个的排列

---

带重复元素的去重算法

针对 [1,1,2] 这类含重复元素的数组，避免生成重复结果：

# 去重组合（手动优化版）
def unique_combinations(arr, k)
  arr.sort! # 排序让重复元素相邻
  result = []
  backtrack = lambda do |start, current|
    result << current.dup if current.size == k
    (start...arr.size).each do |i|
      next if i > start && arr[i] == arr[i-1] # 跳过重复元素
      current << arr[i]
      backtrack.call(i + 1, current)
      current.pop
    end
  end
  backtrack.call(0, [])
  result
end

# 测试
p unique_combinations([1,1,2], 2) # [[1,1],[1,2]]

总结

1. 生产环境：直接用 Ruby 内置的 permutation/combination，高效简洁；
2. 学习/面试：掌握回溯算法手动实现，理解排列组合的核心逻辑；
3. 关键区别：排列有序、组合无序；重复元素需排序+去重优化。

当然可以！完全不用递归，改用迭代 + 栈模拟回溯、或者字典序法来实现排列组合，逻辑更贴近底层，也避免了递归栈溢出问题。

下面直接给你纯迭代版的 Ruby 实现：

• 组合（无重复）
• 全排列（无重复）
• 字典序法生成排列（经典非递归排列算法）

---

非递归实现排列组合

全排列 Permutation （非递归）

同样用栈模拟，栈里存 [当前排列, 已使用下标集合]。

# 非递归：全排列
def permutations_iter(arr)
  return [[]] if arr.empty?

  res = []
  # 栈元素：[当前排列, 已使用的索引集合]
  stack = [[[], Set.new]]

  until stack.empty?
    curr, used = stack.pop

    if curr.size == arr.size
      res << curr.dup
      next
    end

    # 倒序入栈，保证结果顺序和递归版一致
    (arr.size - 1).downto(0) do |i|
      next if used.include?(i)
      stack << [curr + [arr[i]], used + [i]]
    end
  end

  res
end

# 测试
p permutations_iter([1,2,3])

---

选 k 个的排列（非递归）

# 非递归：从 arr 选 k 个的排列
def permutations_k_iter(arr, k)
  return [] if k < 0 || k > arr.size
  return [[]] if k == 0

  res = []
  stack = [[[], Set.new]]

  until stack.empty?
    curr, used = stack.pop

    if curr.size == k
      res << curr.dup
      next
    end

    (arr.size - 1).downto(0) do |i|
      next if used.include?(i)
      stack << [curr + [arr[i]], used + [i]]
    end
  end

  res
end

# 测试
p permutations_k_iter([1,2,3], 2)

---

全部测试汇总

arr = [1,2,3]

puts "=== 组合 C(3,2) ==="
p combinations_iter(arr, 2)

puts "\n=== 全排列 ==="
p permutations_iter(arr)

puts "\n=== 字典序全排列 ==="
p permutations_dict(arr)

puts "\n=== 选2个排列 P(3,2) ==="
p permutations_k_iter(arr, 2)

---

特点

• 全程无递归、无 lambda 递归、无自身调用
• 用栈 + 循环模拟回溯，逻辑等价递归
• 字典序法是效率最高的非递归排列方式，适合大数据量
• 结果顺序和 Ruby 内置 permutation/combination 基本一致

如果你需要可重复组合/可重复排列的非递归版，我也可以继续补上。

下面给你补上纯迭代、无递归的：

• 可重复排列（允许同一个元素选多次，有序）
• 可重复组合（允许同一个元素选多次，无序）

依然全程只用循环 + 栈/数组，不碰递归。

---

组合 Combination （非递归）

思路：用栈模拟递归的“选择/回溯”，栈里存 [起始索引, 当前组合]，循环处理栈即可。

# 非递归：从 arr 中选 k 个元素的组合
def combinations_iter(arr, k)
  return [] if k < 0 || k > arr.size
  return [[]] if k == 0

  res = []
  # 栈元素：[起始索引, 当前已选组合]
  stack = [[0, []]]

  until stack.empty?
    start, curr = stack.pop

    if curr.size == k
      res << curr.dup
      next
    end

    # 从后往前压栈，保证顺序和递归版一致
    (arr.size - 1).downto(start) do |i|
      stack << [i + 1, curr + [arr[i]]]
    end
  end

  res
end

# 测试
p combinations_iter([1,2,3], 2) # [[1,2], [1,3], [2,3]]
p combinations_iter([1,2,3,4], 3)

---

可重复排列（非递归）

从 n 个元素里可重复地选 k 个，有序。

# 非递归：可重复排列
def repeated_permutation_iter(arr, k)
  return [] if k <= 0
  res = []
  # 栈中存放当前构造的序列
  stack = [[]]

  until stack.empty?
    curr = stack.pop

    if curr.size == k
      res << curr
      next
    end

    # 每个位置都可以选所有元素（可重复）
    arr.each do |num|
      stack << curr + [num]
    end
  end

  res.reverse # 让顺序自然一点
end

# 示例
p repeated_permutation_iter([1,2], 2)
# => [[1,1], [1,2], [2,1], [2,2]]

---

可重复组合（非递归）

从 n 个元素里可重复地选 k 个，无序不重复。
思路：只允许从当前位置及之后选，保证不出现 [2,1] 这种逆序。

# 非递归：可重复组合
def repeated_combination_iter(arr, k)
  return [] if k <= 0
  res = []
  # [当前组合, 起始下标]
  stack = [[[], 0]]

  until stack.empty?
    curr, start = stack.pop

    if curr.size == k
      res << curr
      next
    end

    (start...arr.size).each do |i|
      stack << [curr + [arr[i]], i] # 下次仍从 i 开始，实现可重复
    end
  end

  res.reverse
end

# 示例
p repeated_combination_iter([1,2,3], 2)
# => [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]

---

非递归实现排列组合

把之前的 + 现在的放在一起，方便你直接用：

1. 组合 C(n,k) 不重复、无序
2. 排列 P(n,k) 不重复、有序
3. 可重复排列
4. 可重复组合

# 1. 组合 C(n,k) 不重复、无序
def combinations_iter(arr, k)
  res = []
  stack = [[[], 0]]
  until stack.empty?
    curr, start = stack.pop
    res << curr and next if curr.size == k
    (start...arr.size).each { |i| stack << [curr + [arr[i]], i+1] }
  end
  res.reverse
end

# 2. 排列 P(n,k) 不重复、有序
def permutations_k_iter(arr, k)
  res = []
  stack = [[[], []]] # [curr, used_indexes]
  until stack.empty?
    curr, used = stack.pop
    res << curr and next if curr.size == k
    arr.each_with_index do |num, i|
      stack << [curr + [num], used + [i]] unless used.include?(i)
    end
  end
  res.reverse
end

# 3. 可重复排列
def repeated_permutation_iter(arr, k)
  res = []
  stack = [[]]
  until stack.empty?
    curr = stack.pop
    res << curr and next if curr.size == k
    arr.each { |num| stack << curr + [num] }
  end
  res.reverse
end

# 4. 可重复组合
def repeated_combination_iter(arr, k)
  res = []
  stack = [[[], 0]]
  until stack.empty?
    curr, start = stack.pop
    res << curr and next if curr.size == k
    (start...arr.size).each { |i| stack << [curr + [arr[i]], i] }
  end
  res.reverse
end

# 测试一下
arr = [1,2,3]
k = 2

p combinations_iter(arr, k)              # 普通组合
p permutations_k_iter(arr, k)             # 普通排列
p repeated_combination_iter(arr, k)        # 可重复组合
p repeated_permutation_iter(arr, k)       # 可重复排列

用字典序法实现排列组合

如果你想，我还可以再给你写一版完全不用栈、纯下标迭代的极简版本，更像 C/Java 风格。

下面给你一套完全不用递归、不用栈、不用回溯，纯靠下标循环/数位模拟实现的极简版本，风格更接近传统算法书，代码极短、好理解。

特点：

• 全程只有循环 + 下标操作
• 无递归、无栈、无 lambda、无闭包
• 效率高、适合大数、不会栈溢出
• 结果顺序标准、和数学定义一致

字典序法生成全排列（更高效的非递归）

这是经典教科书级非递归排列算法，不依赖栈/回溯，直接通过交换+逆序生成下一个排列。

步骤：

1. 从后向前找第一个 a[i] < a[i+1] 的位置 i
2. 从后向前找第一个比 a[i] 大的数 a[j]
3. 交换 a[i] 和 a[j]
4. 逆序 i+1 到末尾
5. 重复直到没有下一个排列

# 字典序法：下一个排列
def next_permutation(arr)
  a = arr.dup
  i = a.size - 2

  # 步骤1：找 i
  i -= 1 while i >= 0 && a[i] >= a[i+1]
  return nil if i < 0 # 已到最后一个排列

  # 步骤2：找 j
  j = a.size - 1
  j -= 1 while a[j] <= a[i]

  # 步骤3：交换
  a[i], a[j] = a[j], a[i]

  # 步骤4：逆序
  a[i+1..-1] = a[i+1..-1].reverse

  a
end

# 非递归全排列（字典序）
def permutations_dict(arr)
  return [] if arr.empty?
  res = []
  curr = arr.sort

  until curr.nil?
    res << curr
    curr = next_permutation(curr)
  end

  res
end

# 测试
p permutations_dict([1,2,3])

---

普通排列 P(n,k)（不重复、有序）

def permutations(arr, k)
  n = arr.size
  return [] if k < 1 || k > n

  res = []
  indexes = (0 ... n).to_a

  loop do
    res << indexes[0 ... k].map { |i| arr[i] }

    # 下一个排列（字典序）
    i = n - 2
    i -= 1 while i >= 0 && indexes[i] >= indexes[i+1]
    break if i < 0

    j = n - 1
    j -= 1 while indexes[j] <= indexes[i]

    indexes[i], indexes[j] = indexes[j], indexes[i]
    indexes[i+1 .. -1] = indexes[i+1 .. -1].reverse
  end

  res.uniq
end

---

统一测试

arr = [1,2,3]
k = 2

puts "组合 C(3,2):"
p combinations(arr, k)

puts "\n可重复组合:"
p repeated_combinations(arr, k)

puts "\n可重复排列:"
p repeated_permutations(arr, k)

puts "\n排列 P(3,2):"
p permutations(arr, k)

组合 C(n,k)（不重复、无序）

纯迭代、无递归、无栈 · 完整版（Ruby 可直接运行）

普通组合 C(n,k)（不重复、无序）

def combinations(arr, k)
  n = arr.size
  return [] if k < 1 || k > n

  res = []
  idx = Array.new(k) { |i| i }

  loop do
    res << idx.map { |i| arr[i] }

    i = k - 1
    i -= 1 while i >= 0 && idx[i] == n - k + i
    break if i < 0

    idx[i] += 1
    (i+1 ... k).each { |j| idx[j] = idx[j-1] + 1 }
  end

  res
end

可重复排列（有序、可重复选）

def repeated_permutations(arr, k)
  n = arr.size
  return [] if k < 1

  total = n ** k
  res = []

  (0 ... total).each do |num|
    perm = []
    tmp = num
    k.times do
      perm << arr[tmp % n]
      tmp /= n
    end
    res << perm.reverse
  end

  res
end

可重复组合（无序、可重复选）

def repeated_combinations(arr, k)
  n = arr.size
  return [] if k < 1

  res = []
  idx = Array.new(k, 0)

  loop do
    res << idx.map { |i| arr[i] }

    i = k - 1
    i -= 1 while i >= 0 && idx[i] == n - 1
    break if i < 0

    idx[i] += 1
    (i+1 ... k).each { |j| idx[j] = idx[i] }
  end

  res
end

Python 相关

图论工具箱

以下是 NetworkX 的基础用法演示代码：
涉及算法：最短路径。

import networkx as nx
import matplotlib.pyplot as plt

# ========== 1. 创建图 ==========
print("=== 创建图 ===")

# 无向图
G = nx.Graph()
# 有向图
DG = nx.DiGraph()

# ========== 2. 添加节点和边 ==========
print("\n=== 添加节点和边 ===")

# 添加节点
G.add_node("A")
G.add_nodes_from(["B", "C", "D", "E"])

# 添加边（带权重）
G.add_edge("A", "B", weight=4.0)
G.add_edges_from([
    ("A", "C", {"weight": 2.0}),
    ("B", "C", {"weight": 1.0}),
    ("B", "D", {"weight": 5.0}),
    ("C", "D", {"weight": 3.0}),
    ("C", "E", {"weight": 6.0}),
    ("D", "E", {"weight": 7.0})
])

print(f"节点数: {G.number_of_nodes()}")
print(f"边数: {G.number_of_edges()}")
print(f"所有节点: {list(G.nodes())}")
print(f"所有边: {list(G.edges())}")

# ========== 3. 基本属性 ==========
print("\n=== 基本属性 ===")

# 邻居
print(f"A 的邻居: {list(G.neighbors('A'))}")

# 度数
print(f"A 的度数: {G.degree('A')}")
print(f"所有节点的度数: {dict(G.degree())}")

# 边权重
print(f"A-B 边的权重: {G['A']['B']['weight']}")

# ========== 4. 路径和连通性 ==========
print("\n=== 路径和连通性 ===")

# 最短路径
print(f"A 到 E 的最短路径: {nx.shortest_path(G, 'A', 'E')}")
print(f"A 到 E 的最短路径长度: {nx.shortest_path_length(G, 'A', 'E')}")

# 加权最短路径
print(f"A 到 E 的加权最短路径: {nx.dijkstra_path(G, 'A', 'E')}")
print(f"A 到 E 的加权最短路径长度: {nx.dijkstra_path_length(G, 'A', 'E')}")

# 连通性
print(f"图是否连通: {nx.is_connected(G)}")

# ========== 5. 中心性分析 ==========
print("\n=== 中心性分析 ===")

# 度中心性
print(f"度中心性: {nx.degree_centrality(G)}")

# 介数中心性
print(f"介数中心性: {nx.betweenness_centrality(G)}")

# 接近中心性
print(f"接近中心性: {nx.closeness_centrality(G)}")

# ========== 6. 生成随机图 ==========
print("\n=== 生成随机图 ===")

# Erdős–Rényi 随机图
ER = nx.erdos_renyi_graph(10, 0.3, seed=42)
print(f"ER 随机图 - 节点数: {ER.number_of_nodes()}, 边数: {ER.number_of_edges()}")

# Barabási–Albert 无标度网络
BA = nx.barabasi_albert_graph(20, 2, seed=42)
print(f"BA 无标度网络 - 节点数: {BA.number_of_nodes()}, 边数: {BA.number_of_edges()}")

# Watts–Strogatz 小世界网络
WS = nx.watts_strogatz_graph(20, 4, 0.3, seed=42)
print(f"WS 小世界网络 - 节点数: {WS.number_of_nodes()}, 边数: {WS.number_of_edges()}")

# ========== 7. 图的可视化 ==========
print("\n=== 可视化 ===")

# 创建布局
pos = nx.spring_layout(G, seed=42)

# 绘制图
plt.figure(figsize=(10, 8))
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=12, font_weight='bold')

# 绘制边权重
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

plt.title("NetworkX 图示例")
plt.axis('off')
plt.show()

# ========== 8. 图的统计信息 ==========
print("\n=== 图的统计信息 ===")

print(f"平均度: {sum(dict(G.degree()).values()) / G.number_of_nodes():.2f}")
print(f"密度: {nx.density(G):.3f}")
print(f"聚类系数: {nx.average_clustering(G):.3f}")
print(f"直径: {nx.diameter(G)}")
print(f"半径: {nx.radius(G)}")

排列组合

Python 内置的排列组合功能主要通过 itertools 模块提供，包括 permutations（排列）、combinations（组合）和 combinations_with_replacement（可重复组合）。下面是代码演示：

from itertools import permutations, combinations, combinations_with_replacement

# 示例数据
items = ['A', 'B', 'C']

# 1. 排列（顺序重要，不重复）
print("排列 (permutations):")
print(list(permutations(items, 2)))
# 输出: [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

print("\n" + "="*30)

# 2. 组合（顺序不重要，不重复）
print("组合 (combinations):")
print(list(combinations(items, 2)))
# 输出: [('A', 'B'), ('A', 'C'), ('B', 'C')]

print("\n" + "="*30)

# 3. 可重复组合（顺序不重要，允许重复）
print("可重复组合 (combinations_with_replacement):")
print(list(combinations_with_replacement(items, 2)))
# 输出: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

print("\n" + "="*30)

# 4. 不指定长度时，排列默认使用全部元素
print("全排列 (permutations with all items):")
print(list(permutations(items)))
# 输出: [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

关键区别总结：

函数	顺序重要？	元素可重复？	示例 (从 [A,B,C] 选 2 个)
permutations	✅ 是	❌ 否	6 种
combinations	❌ 否	❌ 否	3 种
combinations_with_replacement	❌ 否	✅ 是	6 种

实用技巧：

• 所有函数返回的都是迭代器，可以用 list() 转换为列表
• 如果数据量很大，建议直接迭代使用，避免一次性生成所有结果占用内存
• 对于数字列表同样适用，例如 permutations([1, 2, 3], 2)

补充

leetcode上有一些题目涉及。