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

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

ただいまの
回答率

89.10%

最小回数で入れ替え 正しい出力が得られない

解決済

回答 1

投稿

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

0からn-1までの数の並びを最小回数で次の条件下で入れ替える.

並び替えの方法を隣どうし数の入れ替えだけにして,両端の入れ替えを行わないようにする.
このプログラムは幅優先探索でそれまでに出現したパターンと重複しているかどうかを調べていない.そのため,効率が悪いのでパターンの重複を調べるようにする.
関数をf(lst)として,この関数の値は [lst, lst1, lst2,...,lstk] とkステップのそれぞれの入れ替えをリストにしたものとする.すなわち,以下のような値を返すものとする:

f([2,0,1,3]) = [[2,0,1,3],[0,2,1,3],[0,1,2,3]]
f([1,3,4,2,0]) = [[1,3,4,2,0],[1,3,2,4,0],[1,2,3,4,0],[0,2,3,4,1]     [0,2,3,1,4],[0,2,1,3,4],[0,1,2,3,4]]

今できているプログラムでは,f([1,3,4,2,0])では正しい値が出力されますが,f([2,0,1,3]) = [[2,0,1,3],[2,1,0,3],[2,1,3,0],[0,1,3,2],[0,1,2,3]]という出力になってしまい,正しい結果が得られません.
どこを修正すべきなのかアドバイスをいただきたいです.

function f(lst) {
    var ans
    function swap(a, i, n){
        var ax = a.slice(0);
        var tmp = ax[i];
        var ii = (i + 1) % n;
        ax[i] = ax[ii];
        ax[ii] = tmp;
        return ax;
    }
    function is_goal(a){
        var n = a.length;
        for (var i = 0; i < n; i++){
            if (a[i] != i) return false
        }
        return true
    }
    function eq_pat(q1, q2){
        var n = q1.length;
        for (var i = 0; i < n; i++){
            if (q1[i] != q2[i]) return false
        }
        return true;
    }
    var ans=[];
    function print_path(m) {

        if (m !== null) {
            print_path(m[2]);
            ans.push(m[1])    
            return ans
        }
    }
    function bfs(list){
        var queue = [[0, list, null]]
        while (true){

            var m = queue.shift();
            var n=list.length;
            var d = m[0];
            var pat = m[1];
            var parent = m[2];

            if (is_goal(pat)) break;
            for (var i = 1; i < n; i++){
                var patx = swap(pat, i, n);
                if (parent !== null && eq_pat(patx, parent[1])) continue;
                queue.push([d + 1, patx, m]);
            }
        }
        ans = print_path(m)
        //puts(ans)
        return ans
    }
    return bfs(lst)
}
puts(f([2,0,1,3]))
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • yambejp

    2020/06/29 17:46

    まえから順番に右側の値といれかえるなら
    [1,3,4,2,0],
    [1,3,2,0,4],
    [1,2,0,3,4],
    [1,0,2,3,4],
    [0,1,2,3,4]
    じゃない?

    キャンセル

  • Q3fdxrGzWzu0u5n

    2020/06/29 17:51

    確かにそうですね.その動作ができていないため,f([2,0,1,3)の出力結果が間違ったものになっているかもしれないです...

    キャンセル

  • sousuke

    2020/06/29 18:22

    隣同士しか入れ替えいけない条件でf([1,3,4,2,0])したらどうなるべきか1個ずつ示した方がいい気がします

    キャンセル

回答 1

checkベストアンサー

0

とりあえず隣を入れ替えるソート

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2020/06/29 18:44 編集

    const f=(a)=>{
    const ret=[];
    var flg=true;
    while(flg){
    flg=false;
    ret.push(a.slice(0));
    a.forEach((x,y)=>{
    if(y>=a.length-1) return;
    if(x>a[y+1]){
    swap(a,y,y+1);
    flg=true;
    }
    });
    }
    return ret;
    }
    const swap=(x,y,z)=>{
    const tmp=x[y];
    x[y]=x[z];
    x[z]=tmp;
    }
    console.log(f([1,3,4,2,0]));

    キャンセル

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

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

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