与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - C#
ごくナイーブにバブルソート。出力は長いです。バブルソートそのまんまの結果がでてきます。 3 5 2 4 0 1 | | | |-| | | | |-| | | | |-| | | | |-| | | | | | | | | |-| | | | |-| | | | |-| | | | |-| | | | | | | |-| | | | |-| | | | | | | |-| 0 1 2 3 4 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | using System;
using System.Collections.Generic;
static class Program {
static void Main() {
List<string> data = new List<String>(new string[]{"3", "5", "2", "4", "0", "1"});
Console.WriteLine(String.Join(" ", data.ToArray()));
Console.WriteLine(String.Join("\n", AmidaSort(data)));
Console.WriteLine(String.Join(" ", data.ToArray()));
}
static string[] AmidaSort<T>(List<T> data) where T: IComparable {
List<string> result = new List<string>();
for(int i = 0; i < data.Count - 1; i++){
for(int j = data.Count - 1; i < j; j--){
if(data[j].CompareTo(data[j - 1]) < 0) {
result.Add(Swap(data, j - 1));
}
}
}
return result.ToArray();
}
static string Swap<T>(List<T> data, int index) where T: IComparable {
T temp = data[index];
data[index] = data[index + 1];
data[index + 1] = temp;
string[] amida = new string[data.Count - 1];
for(int i = 0; i < amida.Length; i++) {
amida[i] = i == index ? "-" : " ";
}
return "|" + String.Join("|", amida) + "|";
}
}
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]