回答編集履歴
3
s
test
CHANGED
|
@@ -262,7 +262,7 @@
|
|
|
262
262
|
|
|
263
263
|
|
|
264
264
|
|
|
265
|
-
このとき、最初の並び順 [0, 1, 2] を起点として、与えられたパターンで並び変えを**深さ優先探索**で行っていくことで、以下のようなグラフが作れます。
|
|
265
|
+
このとき、最初の並び順 [0, 1, 2] を起点として、与えられたパターンで並び変えを**深さ優先探索**で行っていくことで、以下のようなグラフが作れます。(数学的には置換群の [ケイリーグラフ](http://dopal.cs.uec.ac.jp/okamotoy/lect/2016/dme/handout05.pdf) というそうです。)
|
|
266
266
|
|
|
267
267
|
|
|
268
268
|
|
2
d
test
CHANGED
|
@@ -219,3 +219,95 @@
|
|
|
219
219
|
[2] [【行列式編】互換の求め方と置換の符号 | 大学1年生もバッチリ分かる線形代数入門](https://oguemon.com/study/linear-algebra/transposition/)
|
|
220
220
|
|
|
221
221
|
[3] [【行列式編】置換と巡回置換 | 大学1年生もバッチリ分かる線形代数入門](https://oguemon.com/study/linear-algebra/permutation/)
|
|
222
|
+
|
|
223
|
+
|
|
224
|
+
|
|
225
|
+
## 追記
|
|
226
|
+
|
|
227
|
+
|
|
228
|
+
|
|
229
|
+
質問内容を勘違いしていたため、追記。
|
|
230
|
+
|
|
231
|
+
|
|
232
|
+
|
|
233
|
+
----
|
|
234
|
+
|
|
235
|
+
|
|
236
|
+
|
|
237
|
+
### 課題
|
|
238
|
+
|
|
239
|
+
|
|
240
|
+
|
|
241
|
+
* 長さ N の最初の並び順と目標の並び順、すべての要素を同時に並び替えるパターンがランダムに1～3個与えられる。
|
|
242
|
+
|
|
243
|
+
* 与えられたパターンの並び替えを繰り返すことで、目標の並び順にする最小の組み合わせを考える。
|
|
244
|
+
|
|
245
|
+
* そのような組み合わせが見つからない場合は False を返す。
|
|
246
|
+
|
|
247
|
+
|
|
248
|
+
|
|
249
|
+
### 考え方
|
|
250
|
+
|
|
251
|
+
|
|
252
|
+
|
|
253
|
+
例として、N=3 の場合を考えます。
|
|
254
|
+
|
|
255
|
+
|
|
256
|
+
|
|
257
|
+
最初の並び順 [0, 1, 2]
|
|
258
|
+
|
|
259
|
+
目標の並び順 [2, 1, 0]
|
|
260
|
+
|
|
261
|
+
並び変えパターン [1, 0, 2], [0, 2, 1]
|
|
262
|
+
|
|
263
|
+
|
|
264
|
+
|
|
265
|
+
このとき、最初の並び順 [0, 1, 2] を起点として、与えられたパターンで並び変えを**深さ優先探索**で行っていくことで、以下のようなグラフが作れます。
|
|
266
|
+
|
|
267
|
+
|
|
268
|
+
|
|
269
|
+
|
|
270
|
+
|
|
271
|
+
|
|
272
|
+
|
|
273
|
+
点は並び順、辺は実行した並び替えのパターンを意味します。
|
|
274
|
+
|
|
275
|
+
例えば、並び順 (0, 2, 1) に対して、並び替え (1, 0, 2) を実行すると、並び順は (2, 0, 1) になりますので、点 (0, 2, 1) から点 (2, 0, 1) に対して、(1, 0, 2) というラベルのついた辺があります。
|
|
276
|
+
|
|
277
|
+
長さ3の並び順は3!=6なので、最大で6個の点ができます。
|
|
278
|
+
|
|
279
|
+
|
|
280
|
+
|
|
281
|
+
この時点で、目標の並び順の点が存在しない場合、どんなに並び替えを繰り返しても目標の順番にはならないということを意味するので、False を返すようにします。
|
|
282
|
+
|
|
283
|
+
|
|
284
|
+
|
|
285
|
+
最小の並び替え実行パターンを考えるには、グラフにおいて点 [0, 1, 2] から点 [2, 1, 0] に至る**長さが最小の道**を見つければよいことになります。
|
|
286
|
+
|
|
287
|
+
|
|
288
|
+
|
|
289
|
+
答えは以下の2つ
|
|
290
|
+
|
|
291
|
+
```
|
|
292
|
+
|
|
293
|
+
(0, 2, 1) (1, 0, 2) (0, 2, 1)
|
|
294
|
+
|
|
295
|
+
(1, 0, 2) (0, 2, 1) (1, 0, 2)
|
|
296
|
+
|
|
297
|
+
```
|
|
298
|
+
|
|
299
|
+
|
|
300
|
+
|
|
301
|
+
ある点からある点へ至る最短ルートの算出は、すべての辺の重みを1にした**ダイクストラ法**で求められます。
|
|
302
|
+
|
|
303
|
+
|
|
304
|
+
|
|
305
|
+
まとめると、
|
|
306
|
+
|
|
307
|
+
|
|
308
|
+
|
|
309
|
+
1. 最初の並び順から与えられた1 ~ 3 個の並び替えを深さ優先探索で実行して、グラフを作成する。
|
|
310
|
+
|
|
311
|
+
2. 目標の並び順を表す点がグラフに存在しない場合は False を返す。
|
|
312
|
+
|
|
313
|
+
3. 最初の並び順から目標の並び順に至る長さ最小の道をダイクストラ法で見つける。
|
1
d
test
CHANGED
|
@@ -172,7 +172,7 @@
|
|
|
172
172
|
|
|
173
173
|
|
|
174
174
|
|
|
175
|
-
sympy に順列を扱うモジュールがあ
|
|
175
|
+
sympy に順列を扱うモジュールがあるので、自前で実装した上記のことは以下のようにかけます。
|
|
176
176
|
|
|
177
177
|
[Permutations — SymPy 1.4 documentation](https://docs.sympy.org/latest/modules/combinatorics/permutations.html)
|
|
178
178
|
|