如何创建所有作品组合 [英] How create all pieces combinations
问题描述
我正试图通过使用一些修剪和蛮力来解决难题，我达到了48级。但是现在考虑使用一些记忆化来重用计算。
一些表：
拼图：（puzzle_id，级别，翻转）
约束puzzle_id_pk主键（puzzle_id）
Puzzle_rows（puzzle_id，row_id，row_flips）
CONSTRAINT puzzle_row_pk主键（puzzle_id，row_id），
CONSTRAINT puzzle_row_puzzle_id_fk FOREIGN KEY（puzzle_id）
（b
件，piece_id，flips_row1，flips_row2，flips_row3，flips_row4，flips_row5）
CONSTRAINT piece_id_pk主键（puzzle_id，piece_id），
CONSTRAINT piece_puzzle_id_fk FOREIGN KEY（p $$$ c / pre>
此级别为18件：
+- ---------- + ----------- + ------------- + ------------- + ------------- + ------------- + ------------- +
| puzzle_id | piece_id | flips_row1 | flips_row2 | flips_row3 | flips_row4 | flips_row5 |
+ ----------- + ----------- + ------------- + ------- ------ + ------------- + ------------- + ------------- +
| 1 | 1 | 2 | 1 | 2 | 0 | 0 |
| 1 | 2 | 2 | 1 | 0 | 0 | 0 |
| 1 | 3 | 2 | 2 | 2 | 0 | 0 |
| 1 | 4 | 3 | 1 | 3 | 0 | 0 |
| 1 | 5 | 4 | 3 | 3 | 3 | 0 |
| 1 | 6 | 3 | 0 | 0 | 0 | 0 |
| 1 | 7 | 3 | 1 | 3 | 0 | 0 |
| 1 | 8 | 3 | 4 | 1 | 2 | 2 |
| 1 | 9 | 1 | 0 | 0 | 0 | 0 |
| 1 | 10 | 2 | 2 | 2 | 0 | 0 |
| 1 | 11 | 2 | 3 | 4 | 0 | 0 |
| 1 | 12 | 1 | 3 | 1 | 3 | 2 |
| 1 | 13 | 1 | 2 | 2 | 0 | 0 |
| 1 | 14 | 2 | 4 | 1 | 1 | 0 |
| 1 | 15 | 1 | 2 | 1 | 0 | 0 |
| 1 | 16 | 1 | 1 | 3 | 0 | 0 |
| 1 | 17 | 3 | 2 | 3 | 1 | 0 |
| 1 | 18 | 1 | 3 | 2 | 2 | 0 |
+ ----------- + ----------- + ------------- + ------- ------ + ------------- + ------------- + ------------- +
我需要帮助填写表 solution_pieces 所有的组合。在这种情况下， 2 ^ 18 = 262144 的想法是首先检查行奇偶校验以缩减搜索空间。 （SUM（pieces.flips_row1）+ puzzle_row [1] .flips）％3 = 0 。
例如，在下面的图片中，第一行的内容为 {14,15} ：总翻转次数（3）+ row_flips（3）= 6％3 = 0
解决方案：（solution_id，puzzle_id，
flips_row1，flips_row2，flips_row3，flips_row4，flips_row5）
CONSTRAINT solution_pk主键（solution_id），
CONSTRAINT solution_puzzle_id_fk FOREIGN KEY（puzzle_id $ b b solution_pieces：（solution_id，piece_id）
CONSTRAINT solution_pieces_pk主键（solution_id，piece_id），
CONSTRAINT solution_pieces_solution_id_fk FOREIGN KEY（solution_id）
CONSTRAINT solution_puzzle_id_fk $ b FOREIGN KEY code>
所以我需要像这样填写表格 solution_pieces 。
solution_id piece_id
1 1
....-仅含一件的解决方案
18 18
19 1
19 2
20 1
20 3
....-两件式解决方案
262144 {1..18}-所有件式解决方案
然后表 solutions 仅填充 GROUP BY
解决方案使用 Erwin Brandstetter 解决方案，只需添加不必要的内容即可将数组转换为行。
使用cte as（
select row_number（）over（）as rn，*
FROM f_combos（array（SELECT（pieces_id FROM Pieces ORDER BY piece_id））
）
SELECT rn，unnest（f_combos）AS id
FROM cte
ORDER BY 1;
Im trying to solve a puzzle, by using some prunning and brute force I reach level 48. But now thinking use some Memoization to reuse the calculations.
I have some tables:
puzzles: (puzzle_id, level, flips)
CONSTRAINT puzzle_id_pk PRIMARY KEY (puzzle_id)
puzzle_rows (puzzle_id, row_id, row_flips)
CONSTRAINT puzzle_row_pk PRIMARY KEY (puzzle_id, row_id),
CONSTRAINT puzzle_row_puzzle_id_fk FOREIGN KEY (puzzle_id)
pieces: (puzzle_id, piece_id, flips_row1, flips_row2, flips_row3, flips_row4, flips_row5)
CONSTRAINT piece_id_pk PRIMARY KEY (puzzle_id, piece_id),
CONSTRAINT piece_puzzle_id_fk FOREIGN KEY (puzzle_id)
For this level are 18 pieces:
+-----------+-----------+-------------+-------------+-------------+-------------+-------------+
| puzzle_id | piece_id | flips_row1 | flips_row2 | flips_row3 | flips_row4 | flips_row5 |
+-----------+-----------+-------------+-------------+-------------+-------------+-------------+
| 1 | 1 | 2 | 1 | 2 | 0 | 0 |
| 1 | 2 | 2 | 1 | 0 | 0 | 0 |
| 1 | 3 | 2 | 2 | 2 | 0 | 0 |
| 1 | 4 | 3 | 1 | 3 | 0 | 0 |
| 1 | 5 | 4 | 3 | 3 | 3 | 0 |
| 1 | 6 | 3 | 0 | 0 | 0 | 0 |
| 1 | 7 | 3 | 1 | 3 | 0 | 0 |
| 1 | 8 | 3 | 4 | 1 | 2 | 2 |
| 1 | 9 | 1 | 0 | 0 | 0 | 0 |
| 1 | 10 | 2 | 2 | 2 | 0 | 0 |
| 1 | 11 | 2 | 3 | 4 | 0 | 0 |
| 1 | 12 | 1 | 3 | 1 | 3 | 2 |
| 1 | 13 | 1 | 2 | 2 | 0 | 0 |
| 1 | 14 | 2 | 4 | 1 | 1 | 0 |
| 1 | 15 | 1 | 2 | 1 | 0 | 0 |
| 1 | 16 | 1 | 1 | 3 | 0 | 0 |
| 1 | 17 | 3 | 2 | 3 | 1 | 0 |
| 1 | 18 | 1 | 3 | 2 | 2 | 0 |
+-----------+-----------+-------------+-------------+-------------+-------------+-------------+
I need help to fill the table solution_pieces with all the pieces combination. In this case is 2^18 = 262144 The idea is to check row parity first to prunning the search space. (SUM(pieces.flips_row1) + puzzle_row[1].flips) % 3 = 0.
For example in the picture below with pieces {14,15} on first row: pieces total flips (3) + row_flips (3) = 6 % 3 = 0
solutions: (solution_id, puzzle_id,
flips_row1, flips_row2, flips_row3, flips_row4, flips_row5)
CONSTRAINT solution_pk PRIMARY KEY (solution_id),
CONSTRAINT solution_puzzle_id_fk FOREIGN KEY (puzzle_id)
solution_pieces: (solution_id, piece_id)
CONSTRAINT solution_pieces_pk PRIMARY KEY (solution_id, piece_id),
CONSTRAINT solution_pieces_solution_id_fk FOREIGN KEY (solution_id)
CONSTRAINT solution_puzzle_id_fk FOREIGN KEY (puzzle_id)
So I need fill the table solution_pieces like this.
solution_id piece_id
1 1
.... -- solutions with only one piece
18 18
19 1
19 2
20 1
20 3
.... -- solutions with two pieces
262144 {1..18} -- solution with all pieces
Then the table solutions is fill with just a GROUP BY
解决方案 Using Erwin Brandstetter solution, just add unnest to convert array to rows.
WITH cte as (
SELECT row_number() over () as rn, *
FROM f_combos(array(SELECT piece_id FROM pieces ORDER BY piece_id))
)
SELECT rn, unnest( f_combos ) AS id
FROM cte
ORDER BY 1;
这篇关于如何创建所有作品组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
