質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.79%

python3にて指定されたパターンを使って、目標の順序までの並び替えにかかる最小回数の算出方法

受付中

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 728

Tetron

score 10

1年ほど前から、独学でPython3をちょこちょこ進めている初学者です。
腕試しがてら、「0~4まで書かれたカードを特定のパターンらでの入れ替えを繰り返し、目標の順番になるプログラム」を効率よく組もうと、
与えられた条件で最も少ない試行回数を出そうと挑んだのですが、どのような考え方でコードを組めばよいか思いつかなくて、調べてもうまく見つけられなかったので質問させていただきました。

<例>
例えば、
[0,1,2,3,4]から[2,3,1,4,0]という形を目指すとします。
その際、与えられた"特定のパターン"として
1.[2,3,0,1,4]
2.[4,2,3,1,0]があり、
(1・2はそれぞれ、移動前の[0,1,2,3,4]の同じ値の要素の移り先を表しています)
1を2回したとすると、
[0,1,2,3,4]→[2,3,0,1,4]→[0,1,2,3,4] となる、といった具合です。

特定のパターンは1~3つまでで、その都度ランダムに生成させます。
幾らやっても成り立たないケースはFalseで返す予定です。

なにか良い案がありましたら、ご教授ください。よろしくお願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+4

幾らやっても成り立たないケースはFalseで返す予定です。

いくらやっても成り立たない場合はありません。

与えられた条件で最も少ない試行回数を出そうと挑んだのですが、どのような考え方でコードを組めばよいか思いつかなくて、調べてもうまく見つけられなかったので質問させていただきました。

ある順列から別の順列への変換は数学でいう「置換」と考えることができます。
置換は必ず互換の積で表すことができる [1] ので、その互換の積を求めることができれば、それで swap パターンを求められたことになります。

【行列式編】互換の求め方と置換の符号 | 大学1年生もバッチリ分かる線形代数入門
【行列式編】置換と巡回置換 | 大学1年生もバッチリ分かる線形代数入門

上記の内容を踏まえた上でアルゴリズムを考えると、以下のようになります。

サンプルコード

順列を置換の積で表す。

def cyclic_form(permutation):
    cycles = []  # 置換の一覧

    unvisited = permutation.copy()
    while unvisited:
        j = i = unvisited.pop()
        cycle = [i]  # 起点を追加する。
        while True:
            j = permutation[j]  # 1つ移動する。
            if j == i:
                break  # 起点に戻ってきたら一巡したことになるので、break
            cycle.append(j)
            unvisited.remove(j)  # 1度調べた点は除く。
        cycles.append(cycle)

    return cycles

イメージ説明

置換を互換の積に分解する。

def transpositions(cycles):
    trans = []
    for c in cycles:
        cycle_len = len(c)
        if cycle_len == 2:
            # 置換の長さが2ならすなわち互換
            trans.append(tuple(c))
        elif cycle_len > 2:
            # 長さ3以上の場合は、末尾から順に互換に分解する。
            first = c[0]
            for x in c[cycle_len - 1:0:-1]:
                trans.append((first, x))
    return trans

結果を出力する。

def print_show(N, transpositions):
    lst = list(range(N))
    # 結果を表示する。
    for i, j in transpositions:
        lst[i], lst[j] = lst[j], lst[i]  # 交換する。
        print('swap({}, {}): {}'.format(i, j, lst))  # 交換後の順列を表示する。
    print('number of swaps:', len(transpositions))  

dst = [2, 3, 1, 4, 0]  # スワップ後

cycles = cyclic_form(dst)
print(cycles)  # [[0, 2, 1, 3, 4]]

trans = transpositions(cycles)
print(trans)  # [(0, 4), (0, 3), (0, 1), (0, 2)]

print_show(len(dst), trans)
# swap(0, 4): [4, 1, 2, 3, 0]
# swap(0, 3): [3, 1, 2, 4, 0]
# swap(0, 1): [1, 3, 2, 4, 0]
# swap(0, 2): [2, 3, 1, 4, 0]
# number of swaps: 4

sympy を使う場合

sympy に順列を扱うモジュールがあるので、自前で実装した上記のことは以下のようにかけます。
Permutations — SymPy 1.4 documentation

from sympy.combinatorics import Permutation

dst = [2, 3, 1, 4, 0]

p = Permutation(dst)  # 置換
cycles = p.transpositions()  # 置換を互換の積に分解する。

print_show(len(dst), trans)
# swap(0, 4): [4, 1, 2, 3, 0]
# swap(0, 3): [3, 1, 2, 4, 0]
# swap(0, 1): [1, 3, 2, 4, 0]
# swap(0, 2): [2, 3, 1, 4, 0]
# number of swaps: 4

引用

[1] Cyclic permutation - Wikipedia
[2] 【行列式編】互換の求め方と置換の符号 | 大学1年生もバッチリ分かる線形代数入門
[3] 【行列式編】置換と巡回置換 | 大学1年生もバッチリ分かる線形代数入門

追記

質問内容を勘違いしていたため、追記。


課題

  • 長さ N の最初の並び順と目標の並び順、すべての要素を同時に並び替えるパターンがランダムに1~3個与えられる。
  • 与えられたパターンの並び替えを繰り返すことで、目標の並び順にする最小の組み合わせを考える。
  • そのような組み合わせが見つからない場合は False を返す。

考え方

例として、N=3 の場合を考えます。

最初の並び順 [0, 1, 2]
目標の並び順 [2, 1, 0]
並び変えパターン [1, 0, 2], [0, 2, 1]

このとき、最初の並び順 [0, 1, 2] を起点として、与えられたパターンで並び変えを深さ優先探索で行っていくことで、以下のようなグラフが作れます。(数学的には置換群の ケイリーグラフ というそうです。)

イメージ説明

点は並び順、辺は実行した並び替えのパターンを意味します。
例えば、並び順 (0, 2, 1) に対して、並び替え (1, 0, 2) を実行すると、並び順は (2, 0, 1) になりますので、点 (0, 2, 1) から点 (2, 0, 1) に対して、(1, 0, 2) というラベルのついた辺があります。
長さ3の並び順は3!=6なので、最大で6個の点ができます。

この時点で、目標の並び順の点が存在しない場合、どんなに並び替えを繰り返しても目標の順番にはならないということを意味するので、False を返すようにします。

最小の並び替え実行パターンを考えるには、グラフにおいて点 [0, 1, 2] から点 [2, 1, 0] に至る長さが最小の道を見つければよいことになります。

答えは以下の2つ

(0, 2, 1) (1, 0, 2) (0, 2, 1) 
(1, 0, 2) (0, 2, 1) (1, 0, 2)

ある点からある点へ至る最短ルートの算出は、すべての辺の重みを1にしたダイクストラ法で求められます。

まとめると、

  1. 最初の並び順から与えられた1 ~ 3 個の並び替えを深さ優先探索で実行して、グラフを作成する。
  2. 目標の並び順を表す点がグラフに存在しない場合は False を返す。
  3. 最初の並び順から目標の並び順に至る長さ最小の道をダイクストラ法で見つける。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/13 00:11

    ご回答有難うございます。
    数学がニガテなので調べつつ解読させていただいたのですが、上記のサンプルコードは"[0,1,2,3,4]の状態から指定した順序までの置き換えにかかる二項間での入れ替え回数"を出力する認識で宜しいでしょうか。

    <例>内の1.2.にも記した通り、私が想定しているものは指定した順序まで「指定した入れ替え方」で行うので、ただ闇雲に「互換」を行った場合の最小回数ではないです。
    互換の積の分解で、
    [0,1,2,3,4]から1.の[2,3,0,1,4]の状態になってから目標の[2,3,1,4,0]になるわけでもなく、
    その与えられた順序[2,3,0,1,4]の並びに、5つまとめて動く必要があります。
    この5つ同時に動く一つの処理で、何回かかるかという処理についての質問です。

    求めていた回答とは異なりましたが、参考にさせていただきます。ありがとうございます。
    加え、拙い質問文で誤解を招いてしまいました、すみません。
    宜しければまたの回答、お待ちしております。

    キャンセル

  • 2019/04/14 02:18 編集

    申し訳ありません。質問の課題内容を勘違いしておりました。
    回答の内容は目標の順序にするための2要素間のスワップ方法及び回数の一例を出力する方法になります。

    そうではなく、5個同時に並び替える与えられた複数のパターンを使って、目的の並び順にするにはそれらをどのように組み合わせるのがよいかという問題ですね。
    やり方を考えてみましたが、入れ替えを実行する最大試行回数を決めて、全探索で組み合わせを探すぐらいしか思いつかないですね。(試行回数内で見つからなかったら False)

    キャンセル

  • 2019/04/14 04:05

    おそらく、本質的なやり方を思いついたので、追記しました。

    キャンセル

0

編集距離、動的計画法などで検索すると良いかもしれません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/13 00:14

    回答ありがとうございます。
    どのように検索すればよいかわからなかったので、とても助かります。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.79%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • トップ
  • Pythonに関する質問
  • python3にて指定されたパターンを使って、目標の順序までの並び替えにかかる最小回数の算出方法