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

Question

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]))

Comments

[yambejp]

まえから順番に右側の値といれかえるなら
[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]

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

[sousuke]

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

Answer 1

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

Comments

[yambejp]

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]));