如何用BigQuery递归CTE实现任意长度数组的排列生成

我在SQL里构建递归逻辑时遇到了问题，只能用BigQuery环境，尽量避免用JavaScript，想纯用递归CTE实现功能。用Python能轻松搞定：给定任意长度的数组，生成对应的排列集合，比如输入[2,1,2]时输出[[0,0,0],[1,0,0],[0,0,1],[1,0,1]]这类结果。我的思路是从全零数组开始，逐个索引递增元素到输入值减一，保存每个排列，但写的递归CTE代码只完成了第一步，求指导。

以下是我目前的代码：

WITH RECURSIVE
  OrigSeq AS (SELECT [2, 1, 2] as some_numbers), -- input sequence
  BaseSeq AS (SELECT ARRAY(SELECT 0 as a FROM UNNEST(OrigSeq.some_numbers)) AS base FROM OrigSeq), -- get array of 0s of same size as input sequence
  Sequences AS (
    (SELECT 0 AS perm_id, 0 as idx, BaseSeq.base[0] as iter, OrigSeq.some_numbers[0]-1 AS orig, BaseSeq.base as base, OrigSeq.some_numbers as num FROM OrigSeq, BaseSeq)
    UNION ALL
    -- increment index
    SELECT perm_id, idx+1 as idx, base[idx+1] as iter, num[idx+1]-1 as orig, base, num FROM Sequences WHERE idx < ARRAY_LENGTH(num)-1
  ),
  Seq2 AS (
    SELECT * FROM Sequences
    UNION ALL
    -- parse iters - not doing this quite right and my brain stops functioning around here
    SELECT perm_id+1, idx, base[idx]+1 as iter, orig, base, num FROM Sequences where iter <= orig
  ),
  Seq3 AS (
    Select * From Seq2
    UNION ALL
    SELECT perm_id, idx, iter, orig, base, num from Sequences
  )
SELECT perm_id, idx, orig, iter
FROM Seq3
ORDER BY perm_id, idx

解决方案 #

要生成所有可能的排列，递归的核心应该是逐位构建数组，每一步针对当前数组的下一位生成所有可能的取值，直到数组长度和输入一致。以下是正确的递归CTE实现：

WITH RECURSIVE
  OrigSeq AS (SELECT [2, 1, 2] AS some_numbers), -- 输入数组
  -- 初始化：生成第一位的所有可能取值，构成长度为1的数组
  Permutations AS (
    SELECT
      1 AS pos, -- 当前构建到第几位（从1开始）
      ARRAY[val] AS perm
    FROM OrigSeq, UNNEST(GENERATE_ARRAY(0, some_numbers[OFFSET(0)] - 1)) val
    UNION ALL
    -- 递归步骤：为每个已有排列追加下一位的所有可能取值
    SELECT
      p.pos + 1,
      ARRAY_CONCAT(p.perm, ARRAY[val])
    FROM Permutations p
    JOIN OrigSeq o ON p.pos < ARRAY_LENGTH(o.some_numbers)
    UNNEST(GENERATE_ARRAY(0, o.some_numbers[OFFSET(p.pos)] - 1)) val
  )
-- 筛选出长度与输入数组一致的完整排列
SELECT perm
FROM Permutations
WHERE ARRAY_LENGTH(perm) = (SELECT ARRAY_LENGTH(some_numbers) FROM OrigSeq)
ORDER BY perm;

代码逻辑说明 #

1. OrigSeq：定义输入数组，这里示例为[2,1,2]，可直接替换为其他数组。
2. Permutations递归CTE：
   • 初始部分：生成第一位的所有合法取值（0到输入数组第一个元素减1），每个值单独构成长度为1的数组。
   • 递归部分：对每个已生成的排列，若未达到输入数组长度，则取下一位的合法取值范围，将每个值追加到现有排列后，生成新的更长排列。
3. 最终筛选：只保留长度和输入数组一致的结果，即为所有完整排列。

测试输入[2,1,2]时，输出结果为：

[0,0,0]
[0,0,1]
[1,0,0]
[1,0,1]

该方案无需维护额外的索引或ID，通过数组长度自动控制递归终止，逻辑简洁且适配任意长度的输入数组。

内容的提问来源于stack exchange，提问作者dgBP