質問編集履歴

1

該当ソースコードを追加しました

2020/06/24 03:08

投稿

plzcarryme
plzcarryme

スコア3

test CHANGED
File without changes
test CHANGED
@@ -22,6 +22,16 @@
22
22
 
23
23
 
24
24
 
25
+ //追記//
26
+
27
+
28
+
29
+ 配列を受け取り幅優先探索で上記の結果のように並び替え、結果を一本の配列として出力したいです。
30
+
31
+
32
+
33
+
34
+
25
35
 
26
36
 
27
37
  ### 該当のソースコード
@@ -30,9 +40,119 @@
30
40
 
31
41
  ```ここに言語名を入力
32
42
 
33
- var ans=[]
34
43
 
44
+
45
+ /配列aのi番目とi+1番目の要素を入れ替えた配列を返す関数/
46
+
47
+ function swap(a, i, n){
48
+
49
+ var ax = a.slice(0);
50
+
51
+ var tmp = ax[i];
52
+
53
+ var ii = (i + 1) % n;
54
+
55
+ ax[i] = ax[ii];
56
+
57
+ ax[ii] = tmp;
58
+
59
+ return ax;
60
+
61
+ }
62
+
63
+ /配列の並びが最終系になっているかの確認/
64
+
65
+ function is_goal(a){
66
+
67
+ var n = a.length;
68
+
69
+ for (var i = 0; i < n; i++){
70
+
71
+ if (a[i] != i) return false
72
+
73
+ }
74
+
75
+ return true
76
+
77
+ }
78
+
79
+ /二つの配列を引数とし要素が同じであるかを調べる/
80
+
81
+ function eq_pat(q1, q2){
82
+
83
+ var n = q1.length;
84
+
85
+ for (var i = 0; i < n; i++){
86
+
87
+ if (q1[i] != q2[i]) return false
88
+
89
+ }
90
+
91
+ return true;
92
+
93
+ }
94
+
95
+ /根からノードに向けてのパターンの出力/
96
+
97
+ function print_path(m) {
98
+
99
+ var ans=[];
100
+
101
+ if (m != null) {
102
+
103
+ print_path(m[2]);
104
+
35
- ans.push(m[1])
105
+ ans.push(m[1])
106
+
107
+ console.log(ans)
108
+
109
+ }
110
+
111
+ }
112
+
113
+ /queueの要素:[木の深さ、パターン、親のノード]/
114
+
115
+ function bfs(list){
116
+
117
+ var queue = [[0, list, null]]
118
+
119
+ while (true){
120
+
121
+
122
+
123
+ var m = queue.shift();
124
+
125
+ var n=list.length;
126
+
127
+ var d = m[0];
128
+
129
+ var pat = m[1];
130
+
131
+ var parent = m[2];
132
+
133
+
134
+
135
+ if (is_goal(pat)) break;
136
+
137
+ for (var i = 1; i < n; i++){
138
+
139
+ var patx = swap(pat, i, n);
140
+
141
+ if (parent != null && eq_pat(patx, parent[1])) continue;
142
+
143
+ queue.push([d + 1, patx, m]);
144
+
145
+ }
146
+
147
+ }
148
+
149
+ print_path(m);
150
+
151
+ }
152
+
153
+
154
+
155
+ bfs([0,4,2,3,5,1])
36
156
 
37
157
  ```
38
158