与えられた並べ替えを実現するあみだくじの生成 in Smalltalk DouKaku?

与えられた並べ替えを実現するあみだくじの生成

お題#4476を見て思いつきました。

0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。

与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：

 0 1 2 3 4 5
 | | |-| |-|
 | |-| |-| |
 |-| |-| | |
 | |-| |-| |
 | | |-| |-|
 | | | |-| |
 3 5 2 4 0 1

一応、制約条件を示しておきます。

あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります。
同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。

一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。

post comment

Posted feedbacks - Smalltalk

Squeak Smalltalk で。

| goal amida isNeighbor |
goal := #(3 5 2 4 0 1).
amida := OrderedCollection with: ((goal asString allButFirst: 2) allButLast).
isNeighbor := false.
[goal isSorted] whileFalse: [
    amida addFirst: (String streamContents: [:ss |
        1 to: goal size - 1 do: [:idx |
            ss nextPutAll: (
                (isNeighbor not and: [(goal at: idx) > (goal at: idx + 1)])
                    ifTrue:[
                        goal swap: idx with: idx + 1.
                        isNeighbor := true.
                        '|-']
                    ifFalse: [
                        isNeighbor := false.
                        '| '])].
        ss nextPut: $|])].
amida addFirst: ((goal asString allButFirst: 2) allButLast).
World findATranscript: nil.
amida do: [:line | Transcript cr; show: line]

"=>
0 1 2 3 4 5
| |-| | | |
|-| |-| |-|
| |-| |-| |
|-| |-| |-|
| |-| |-| |
3 5 2 4 0 1 "

DouKaku?

与えられた並べ替えを実現するあみだくじの生成

Posted feedbacks - Smalltalk

Index

Feed

Other

Link

Pathtraq