与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - Java
置換を互換の積に変換する方法で悩んだのですが、バブルソートを応用すれば できる事に気付きました（考え易くするため逆変換を求めて反転させています）。 バブルソートをアレンジして、隣接する互換が連続で起きないようにしています。 これによって例題では例示よりも１行短い解を出力します。 引数に得たいリストを与えて起動してください。 0 1 2 3 4 5 | |-| | | | |-| |-| |-| | |-| |-| | |-| |-| |-| | |-| |-| | 3 5 2 4 0 1
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 32 33 34 35 36 37 38 39 40 41 | import java.util.*;
public class Sample {
public static void main(String[] args) {
int[] sequence = new int[args.length];
List<String> amida = new ArrayList<String>();
String seed = "";
String nums = "";
for (int i = 0; i < args.length; i++) {
sequence[i] = Integer.parseInt(args[i]);
seed = seed + "| ";
nums = nums + args[i] + " ";
}
amida.add(nums);
boolean change;
do {
StringBuilder am = new StringBuilder(seed);
change = false;
for (int i = 0; i < sequence.length - 1; i++) {
if (sequence[i] > sequence[i + 1]) {
int a = sequence[i];
sequence[i] = sequence[i + 1];
sequence[i + 1] = a;
change = true;
am.setCharAt(2 * i + 1, '-');
i++;
}
}
if (change)
amida.add(am.toString());
} while (change);
nums = "";
for (int i = 0; i < sequence.length; i++)
nums = nums + Integer.toString(sequence[i]) + " ";
amida.add(nums);
Collections.reverse(amida);
for (String s : amida) {
System.out.println(s);
}
}
}
|
逆変換を求めて反転させるのが本質的な操作でないのが気になって、 直接求めるプログラムも作ってみました。 ほとんど同じなのですが、余分な操作がなくなった分だけかえって 直感的になったような気もします。 当然ですが、出力する解は違います。 0 1 2 3 4 5 | |-| | |-| |-| |-| | | | |-| |-| | |-| |-| |-| | |-| |-| | 3 5 2 4 0 1
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 32 33 34 35 36 | import java.util.*;
public class Sample2 {
public static void main(String[] args) {
int[] sequence = new int[args.length];
Map<Integer, Integer> order = new HashMap<Integer, Integer>();
String seed = "";
for (int i = 0; i < args.length; i++) {
order.put(Integer.parseInt(args[i]), i);
sequence[i] = i;
seed = seed + "| ";
System.out.print(Integer.toString(i) + " ");
}
System.out.println();
boolean change;
do {
StringBuilder am = new StringBuilder(seed);
change = false;
for (int i = 0; i < sequence.length - 1; i++) {
if (order.get(sequence[i]) > order.get(sequence[i + 1])) {
int a = sequence[i];
sequence[i] = sequence[i + 1];
sequence[i + 1] = a;
change = true;
am.setCharAt(2 * i + 1, '-');
i++;
}
}
if (change)
System.out.println(am.toString());
} while (change);
for (int i = 0; i < sequence.length; i++)
System.out.print(Integer.toString(sequence[i]) + " ");
System.out.println();
}
}
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]