サブセット反転に基づくソート アルゴリズムを探しています。これはパンケーキの並べ替えのようなものですが、へらの上にすべてのパンケーキを取る代わりに、必要なサブセットを反転させることができます. サブセットの長さは問題ではありません。このように: http://www.yourgenome.org/sites/default/files/illustrations/diagram/dna_mutations_inversion_yourgenome.png したがって、すべてを反転させずに単純に数値を交換することはできません。
これは、ショウジョウバエの 1 つの亜種が他の亜種にどのように変異するかを判断するために行っています。どちらも同じ遺伝子を持っていますが、順序が異なります。2 番目の亜種のゲノムは「ソート」されています。つまり、遺伝子番号は 1 ～ 25 です。最初の亜種ゲノムはソートされていません。したがって、ソートアルゴリズムを探しています。
これは、私たちが見ている「ゲノム」です (ただし、すべての数字のリストでこれを機能させることができるはずです):
[23, 1, 2, 11, 24, 22, 19, 6, 10, 7, 25, 20, 5, 8, 18, 12, 13, 14, 15, 16, 17, 21, 3, 4, 9];
2 つの別々の問題を検討しています。
1) 反転の少ない 25 個の数字のリストを並べ替えるには
2) 25 個の数字のリストを並べ替えるには、移動する数字の数が最も少なくなるようにします。
左から右に移動し、次に低い値を検索し、その間のすべてを反転させることで、このように並べ替える方法を既に見つけましたが、これをより高速に実行できるはずであることは間違いありません。しかし、まだ他の方法が見つからないので、あなたの助けを求めています!
UPDATE: the method we currently use is based on the above method
but instead works both ways. It looks at the next elements needed
for both ends (e.g. 1 and 25 at the beginning) and then calculates
which inversion would be cheapest. All values at the ends can be
ignored for the rest of the algorithm because they get put into the
correct place immediately. Our first method took 18/19 steps and 148
genes, and this one does it in 17 steps and 101 genes. For both
optimalisation tactics (the two mentioned above), this is a better
method. It is however not cheaper in terms of code and processing.
現在、私たちは Python で作業していますが、これは Python での経験が最も多いためですが、より効率的にこれに取り組む方法についての疑似コードのアイデアがあれば喜んで提供します。別の言語の方が適していると思われる場合は、お知らせください。疑似コード、アイデア、考え、実際のコードはすべて大歓迎です!
前もって感謝します！