ねら~ITエンジニア雑記

やきうのお兄ちゃんが綴るOracle Databaseメインのブログ

SQL の再帰WITH句で nPr(n = r)の1桁数値順列を生成してみる。(Oracle Database)

1. やりたい事

表題の通り、再帰WITH句で下記のような数値の順列(重複無し)を生成してみます。

1       ... 1
1, 2    ... 12, 21
1, 2, 3 ... 123, 132, 213, 231, 312, 321
:

nPr の公式で n = r の順列となります。使用するのは Oracle Database で
ちょっとした検証だったので Live SQL のサイトでガチャガチャと検証彡(゚)(゚)

Oracle Live SQL
https://livesql.oracle.com/

2. 順列を生成するSQL

以下のような SQL で対象の順列を生成できました。数値1桁まで対応します。

WITH nums AS (
  SELECT LEVEL AS C0
    FROM DUAL
 CONNECT BY LEVEL <= 3
),
cte(c1, c2) AS (
  SELECT nums.c0, TO_CHAR(nums.c0)
    FROM nums
   UNION ALL
  SELECT c1
       , c2 || nums.c0
    FROM nums, cte
   WHERE LENGTH(c2) < 3
     AND cte.c2 NOT LIKE '%' || TO_CHAR(nums.c0) || '%'
)
SELECT *
  FROM cte
 WHERE LENGTH(c2) = 3
 ORDER BY c2;

結果は以下の通り。n = r の順列の場合は n!(階乗) で要素数を表現できます。3 の場合は 321 で 6個

image.png

1,2,3,4,5 の順列では下記のようになります。要素数は 5!=54321 で 120個ですね。

image.png

3. SQLの解説

以下のような考え方で SQL を組んでいます。

・初めのWITH句(nums仮表)で順列の生成に必要な数値(1, 2, 3, ...)を生成しています。
再帰WITH句の開始条件(開始レコード)はnums仮表の各要素
再帰WITH句の継続条件は 長さが求める順列の長さより小さい場合 かつ nums仮表の要素を順列(c2列)に含まない場合
・そのままだと短い順列も取得されてしまうので、順列の文字列長で絞り込んでいます。

上記の通り再帰WITH句の継続条件の判定がショボいので、1桁の数値までしか対応しません。

4. 参考サイト

下記のサイトを参考にさせて頂きました。ありがとうございます!彡(^)(^)

SQL だけで再帰的に順列/組み合わせを列挙する
https://zenn.dev/indigo13love/articles/b04f8f2973fee3

上記サイトのように配列型を定義してゴニョゴニョすれば、1桁制限も突破できるとは思われる。
彡(゚)(゚)