如何创建所有作品组合 [英] 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屋!