teratail
回答率
85.48%
質問するログイン新規登録
トップJavaに関する質問javaで0,1,2,3,4の５つの数の並べ方をすべて導出したい

編集履歴

回答編集履歴

25

テキスト修正

2015/06/14 21:35

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -72,7 +72,7 @@
72
72
 
73
73
 
74
74
 
75
- // 結果の表示（逆順にリスト要素を出力
75
+ // 結果の表示（逆順にリスト要素を出力）
76
76
 
77
77
  int counter = 0;
78
78
 

24

テキスト修正

2015/06/14 21:35

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -72,13 +72,11 @@
72
72
 
73
73
 
74
74
 
75
- // 結果の表示（逆順にリスト要素を出力）
75
+ // 結果の表示（逆順にリスト要素を出力
76
-
77
- final int size = list.size();
78
76
 
79
77
  int counter = 0;
80
78
 
81
- for (int i = size - 1; i >= 0; --i) {
79
+ for (int i = list.size() - 1; i >= 0; --i) {
82
80
 
83
81
  counter++;
84
82
 

23

テキスト修正

2015/06/14 21:31

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -16,11 +16,11 @@
16
16
 
17
17
  > 要素 n を追加して作成する。
18
18
 
19
- > その際に、要素 n を追加する場所は、以下のnヶ所ある。
19
+ > その際に、要素 n を追加する場所は、以下の(n+1)ヶ所ある。
20
20
 
21
21
  > 　・p(n)の先頭
22
22
 
23
- > 　・p(n)の要素と要素の間（ (n-1)ヶ所ある。）
23
+ > 　・p(n)の要素と要素の間（これは、(n-1)ヶ所ある。）
24
24
 
25
25
  > 　・p(n)の末尾
26
26
 

22

テキスト修正

2015/06/14 19:18

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -10,11 +10,19 @@
10
10
 
11
11
  　基本的な考え方は以下です。
12
12
 
13
- > 0 以上 n以下の(n+1)個の整数を要素とする順列は、
13
+ > 0 以上 n以下の(n+1)個の整数を要素とする順列 p(n+1) は、
14
-
14
+
15
- > 0 以上 (n-1)以下の n個の整数を要素とする順列の
15
+ > 0 以上 (n-1)以下の n個の整数を要素とするある順列 p(n)に、
16
-
16
+
17
- > 要素と要素の間、および先頭と末尾に n を追加して作成できる。
17
+ > 要素 n を追加して作成する。
18
+
19
+ > その際に、要素 n を追加する場所は、以下のnヶ所ある。
20
+
21
+ > 　・p(n)の先頭
22
+
23
+ > 　・p(n)の要素と要素の間（ (n-1)ヶ所ある。）
24
+
25
+ > 　・p(n)の末尾
18
26
 
19
27
  たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
20
28
 

21

テキスト修正

2015/06/14 19:16

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -84,7 +84,7 @@
84
84
 
85
85
  /*
86
86
 
87
- * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
87
+ * 0以上 n以下の整数を要素とする順列（を表現したリスト）を
88
88
 
89
89
  * 要素として持つリストを作成
90
90
 

20

テキスト修正

2015/06/14 19:04

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -2,13 +2,13 @@
2
2
 
3
3
 
4
4
 
5
- お手本になるようなアルゴリズムや、それを実装したコードがきっと
5
+ 　お手本になるようなアルゴリズムや、それを実装したコードがきっと
6
6
 
7
7
  あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
8
8
 
9
9
 
10
10
 
11
- 基本的な考え方は以下です。
11
+ 　基本的な考え方は以下です。
12
12
 
13
13
  > 0 以上 n以下の(n+1)個の整数を要素とする順列は、
14
14
 
@@ -20,7 +20,7 @@
20
20
 
21
21
  要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の
22
22
 
23
- ４カ所あり、それぞれの追加する位置によって、
23
+ ４カ所あり、これらの追加する位置の違いによって４つの順列、
24
24
 
25
25
  [3,0,1,2]
26
26
 
@@ -30,11 +30,9 @@
30
30
 
31
31
  [0,1,2,3]
32
32
 
33
- が作成されます。
34
-
35
- この考え方で再帰のアルゴリズムを作成しました。
33
+ が作成されます。この考え方で再帰のアルゴリズムを作成しました。
36
-
34
+
37
- 以下のソースで、
35
+ 　以下のソースで、
38
36
 
39
37
  　private static List<List<Integer>> getPermutations(Integer n)
40
38
 
@@ -158,7 +156,7 @@
158
156
 
159
157
  ```
160
158
 
161
- 上記を実行すると、以下のような出力が得られます。
159
+ 　上記を実行すると、以下のような出力が得られます。
162
160
 
163
161
  行頭の数字は、組み合わせの数を数えるためのものです。
164
162
 

19

テキスト修正

2015/06/14 18:59

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -8,6 +8,32 @@
8
8
 
9
9
 
10
10
 
11
+ 基本的な考え方は以下です。
12
+
13
+ > 0 以上 n以下の(n+1)個の整数を要素とする順列は、
14
+
15
+ > 0 以上 (n-1)以下の n個の整数を要素とする順列の
16
+
17
+ > 要素と要素の間、および先頭と末尾に n を追加して作成できる。
18
+
19
+ たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
20
+
21
+ 要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の
22
+
23
+ ４カ所あり、それぞれの追加する位置によって、
24
+
25
+ [3,0,1,2]
26
+
27
+ [0,3,1,2]
28
+
29
+ [0,1,3,2]
30
+
31
+ [0,1,2,3]
32
+
33
+ が作成されます。
34
+
35
+ この考え方で再帰のアルゴリズムを作成しました。
36
+
11
37
  以下のソースで、
12
38
 
13
39
  　private static List<List<Integer>> getPermutations(Integer n)

18

テキスト修正

2015/06/14 18:57

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -20,6 +20,8 @@
20
20
 
21
21
  import java.util.ArrayList;
22
22
 
23
+ import java.util.Arrays;
24
+
23
25
  import java.util.List;
24
26
 
25
27
 
@@ -60,7 +62,7 @@
60
62
 
61
63
  * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
62
64
 
63
- 　　 * 要素として持つリストを作成
65
+ * 要素として持つリストを作成
64
66
 
65
67
  */
66
68
 
@@ -82,15 +84,11 @@
82
84
 
83
85
 
84
86
 
85
- // n = 0 の場合、[0]だけを要素とするリストを返す。
87
+ // n = 0 の場合、要素の追加が可能なリスト[0]を要素とするリストを返す。
86
-
88
+
87
- if (n == 0) {
89
+ if (n == 0) {
88
-
90
+
89
- List<Integer> permutation = new ArrayList<Integer>();
91
+ results.add(new ArrayList<Integer>(Arrays.asList(0)));
90
-
91
- permutation.add(0);
92
-
93
- results.add(permutation);
94
92
 
95
93
  return results;
96
94
 

17

テキスト修正

2015/06/14 18:13

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -10,7 +10,7 @@
10
10
 
11
11
  以下のソースで、
12
12
 
13
- 　private static List<List<Integer>> getPermutations(int n)
13
+ 　private static List<List<Integer>> getPermutations(Integer n)
14
14
 
15
15
  が再帰で解のリストを求めるメソッドです。
16
16
 

16

テキスト修正

2015/06/14 17:57

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -58,7 +58,9 @@
58
58
 
59
59
  /*
60
60
 
61
- * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを 要素として持つリストを作成
61
+ * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
62
+
63
+ 　　 * 要素として持つリストを作成
62
64
 
63
65
  */
64
66
 

15

テキスト修正

2015/06/14 17:52

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -44,7 +44,7 @@
44
44
 
45
45
  int counter = 0;
46
46
 
47
- for ( int i = size - 1; i >= 0; --i ) {
47
+ for (int i = size - 1; i >= 0; --i) {
48
48
 
49
49
  counter++;
50
50
 
@@ -58,23 +58,29 @@
58
58
 
59
59
  /*
60
60
 
61
- * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
61
+ * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを 要素として持つリストを作成
62
-
63
- * 要素として持つリストを作成
64
62
 
65
63
  */
66
64
 
67
65
  private static List<List<Integer>> getPermutations(Integer n) {
68
66
 
67
+
68
+
69
-
69
+ // n が不正な値のとき、何もせず null を返して終了
70
-
70
+
71
- if (n == null || n < 0) return null;
71
+ if (n == null || n < 0)
72
+
72
-
73
+ return null;
74
+
75
+
76
+
73
-
77
+ // このメソッドの返り値となるリストを作成
74
-
78
+
75
- List<List<Integer>> permutationsList = new ArrayList<List<Integer>>();
79
+ List<List<Integer>> results = new ArrayList<List<Integer>>();
80
+
81
+
82
+
76
-
83
+ // n = 0 の場合、[0]だけを要素とするリストを返す。
77
-
78
84
 
79
85
  if (n == 0) {
80
86
 
@@ -82,41 +88,43 @@
82
88
 
83
89
  permutation.add(0);
84
90
 
85
- permutationsList.add(permutation);
91
+ results.add(permutation);
86
-
92
+
87
- } else {
93
+ return results;
94
+
88
-
95
+ }
96
+
97
+
98
+
99
+ // n > 0 の場合、まず、(n-1)に対する解のリストを再帰で取得
100
+
89
- final List<List<Integer>> prevPermutationsList = getPermutations(n - 1);
101
+ List<List<Integer>> prevResults = getPermutations(n - 1);
102
+
103
+
104
+
90
-
105
+ // (n-1)のときのリストをループし、要素の順列に n を加えた順列を作成
91
-
92
-
106
+
93
- for ( List<Integer> permutation : prevPermutationsList ) {
107
+ for (List<Integer> permutation : prevResults) {
94
-
95
- final int size = permutation.size();
108
+
96
-
97
- for ( int i = 0; i <= size; ++i ) {
109
+ for (int i = 0; i <= n; ++i) { // n を加える位置についてのループ
98
-
110
+
99
- permutation.add(i, n);
111
+ permutation.add(i, n);
100
-
112
+
101
- permutationsList.add(new ArrayList<Integer>(permutation));
113
+ results.add(new ArrayList<Integer>(permutation));
102
-
114
+
103
- permutation.remove(n);
115
+ permutation.remove(n);
104
-
105
- }
106
-
107
- permutation.clear();
108
116
 
109
117
  }
110
118
 
111
-
112
-
113
- prevPermutationsList.clear();
119
+ permutation.clear(); // 全要素を削除しておく
114
120
 
115
121
  }
116
122
 
117
-
123
+ prevResults.clear(); // 全要素を削除しておく
118
-
124
+
125
+
126
+
119
- return permutationsList;
127
+ return results;
120
128
 
121
129
  }
122
130
 

14

テキスト修正

2015/06/14 17:51

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -64,11 +64,11 @@
64
64
 
65
65
  */
66
66
 
67
- private static List<List<Integer>> getPermutations(int n) {
67
+ private static List<List<Integer>> getPermutations(Integer n) {
68
68
 
69
69
 
70
70
 
71
- if (n < 0) return null;
71
+ if (n == null || n < 0) return null;
72
72
 
73
73
 
74
74
 
@@ -88,8 +88,6 @@
88
88
 
89
89
  final List<List<Integer>> prevPermutationsList = getPermutations(n - 1);
90
90
 
91
- final Integer intN = new Integer(n);
92
-
93
91
 
94
92
 
95
93
  for ( List<Integer> permutation : prevPermutationsList ) {
@@ -102,7 +100,7 @@
102
100
 
103
101
  permutationsList.add(new ArrayList<Integer>(permutation));
104
102
 
105
- permutation.remove(intN);
103
+ permutation.remove(n);
106
104
 
107
105
  }
108
106
 
@@ -124,8 +122,6 @@
124
122
 
125
123
  }
126
124
 
127
-
128
-
129
125
  ```
130
126
 
131
127
  上記を実行すると、以下のような出力が得られます。

13

テキスト修正

2015/06/14 17:24

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -128,10 +128,10 @@
128
128
 
129
129
  ```
130
130
 
131
-
132
-
133
131
  上記を実行すると、以下のような出力が得られます。
134
132
 
133
+ 行頭の数字は、組み合わせの数を数えるためのものです。
134
+
135
135
  ```lang-xxx
136
136
 
137
137
  1:[0, 1, 2, 3, 4]
@@ -156,9 +156,17 @@
156
156
 
157
157
  ```
158
158
 
159
-
159
+ ５個の要素による順列の数は、公式nPr = n!/(n-r)!　に n=r=5 を代入して
160
+
161
+
162
+
160
-
163
+ 5P5 = 5!/(5-5)! = (5*4*3*2*1)/0! = 120/1 = 120
164
+
165
+
166
+
167
+ ですので、出力例の行数は合っています。
168
+
161
- ソースコードのmainメソッドの中で
169
+ また、ソースコードのmainメソッドの中で
162
170
 
163
171
  　List<List<Integer>> list = getPermutations(4);
164
172
 

12

テキスト修正

2015/06/14 17:07

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -8,9 +8,11 @@
8
8
 
9
9
 
10
10
 
11
- 以下の getPermutations(int n)　が再帰で解のリストを
11
+ 以下のソースで、
12
12
 
13
+ 　private static List<List<Integer>> getPermutations(int n)
14
+
13
- 求めるメソッドです。
15
+ が再帰で解のリストを求めるメソッドです。
14
16
 
15
17
 
16
18
 
@@ -158,45 +160,25 @@
158
160
 
159
161
  ソースコードのmainメソッドの中で
160
162
 
161
-
162
-
163
163
  　List<List<Integer>> list = getPermutations(4);
164
-
165
-
166
164
 
167
165
  としているところを
168
166
 
169
-
170
-
171
167
  　List<List<Integer>> list = getPermutations(5);
172
-
173
-
174
168
 
175
169
  にしたり、
176
170
 
177
-
178
-
179
171
  　List<List<Integer>> list = getPermutations(0);
180
-
181
-
182
172
 
183
173
  にしたりしてみましたが問題なく動くのを確認しました。
184
174
 
185
175
  ただし私の手元のPCでは、
186
176
 
187
-
188
-
189
177
  getPermutations(8);
190
-
191
-
192
178
 
193
179
  まではいけましたが
194
180
 
195
-
196
-
197
181
  getPermutations(9);
198
-
199
-
200
182
 
201
183
  でヒープを使い果たして
202
184
 
@@ -210,6 +192,6 @@
210
192
 
211
193
 
212
194
 
213
- ご参考まで。
195
+ 以上、ご参考になれば幸いです。
214
196
 
215
197
 

11

テキスト修正

2015/06/14 17:01

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -126,17 +126,57 @@
126
126
 
127
127
  ```
128
128
 
129
+
130
+
131
+ 上記を実行すると、以下のような出力が得られます。
132
+
133
+ ```lang-xxx
134
+
135
+ 1:[0, 1, 2, 3, 4]
136
+
137
+ 2:[0, 1, 2, 4, 3]
138
+
139
+ 3:[0, 1, 4, 2, 3]
140
+
141
+ 4:[0, 4, 1, 2, 3]
142
+
143
+ 5:[4, 0, 1, 2, 3]
144
+
145
+ ・・・
146
+
147
+ 117:[3, 2, 1, 4, 0]
148
+
149
+ 118:[3, 2, 4, 1, 0]
150
+
151
+ 119:[3, 4, 2, 1, 0]
152
+
153
+ 120:[4, 3, 2, 1, 0]
154
+
155
+ ```
156
+
157
+
158
+
129
- 上記のmainメソッドの中で
159
+ ソースコードのmainメソッドの中で
130
-
160
+
161
+
162
+
131
- List<List<Integer>> list = getPermutations(4);
163
+ 　List<List<Integer>> list = getPermutations(4);
164
+
165
+
132
166
 
133
167
  としているところを
134
168
 
169
+
170
+
135
- List<List<Integer>> list = getPermutations(5);
171
+ 　List<List<Integer>> list = getPermutations(5);
172
+
173
+
136
174
 
137
175
  にしたり、
138
176
 
177
+
178
+
139
- List<List<Integer>> list = getPermutations(0);
179
+ 　List<List<Integer>> list = getPermutations(0);
140
180
 
141
181
 
142
182
 
@@ -144,12 +184,20 @@
144
184
 
145
185
  ただし私の手元のPCでは、
146
186
 
187
+
188
+
147
189
  getPermutations(8);
148
190
 
191
+
192
+
149
193
  まではいけましたが
150
194
 
195
+
196
+
151
197
  getPermutations(9);
152
198
 
199
+
200
+
153
201
  でヒープを使い果たして
154
202
 
155
203
 

10

サンプルコード修正

2015/06/14 16:59

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -16,10 +16,6 @@
16
16
 
17
17
  ```lang-java
18
18
 
19
- package teratail;
20
-
21
-
22
-
23
19
  import java.util.ArrayList;
24
20
 
25
21
  import java.util.List;
@@ -30,29 +26,27 @@
30
26
 
31
27
 
32
28
 
33
- public static void main(String[] args)
29
+ public static void main(String[] args) {
34
30
 
35
- {
36
31
 
32
+
37
- // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
33
+ // 0以上４以下の整数のすべての順列のリストを作成
38
34
 
39
35
  List<List<Integer>> list = getPermutations(4);
40
36
 
41
37
 
42
38
 
43
- // 結果の表示
39
+ // 結果の表示（逆順にリスト要素を出力）
44
40
 
45
41
  final int size = list.size();
46
42
 
47
-
48
-
49
43
  int counter = 0;
50
44
 
51
- for ( int i = size-1; i >= 0; -- i ) {
45
+ for ( int i = size - 1; i >= 0; --i ) {
52
46
 
53
- counter ++;
47
+ counter++;
54
48
 
55
- System.out.println(counter + ":" + listString(list.get(i)));
49
+ System.out.println(counter + ":" + list.get(i));
56
50
 
57
51
  }
58
52
 
@@ -60,147 +54,73 @@
60
54
 
61
55
 
62
56
 
63
-
64
-
65
57
  /*
66
58
 
67
- * 整数のリストを、[0,1,2]のような形式の文字列にして返す。
59
+ * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
60
+
61
+ * 要素として持つリストを作成
68
62
 
69
63
  */
70
64
 
71
- private static String listString(List<Integer> list)
65
+ private static List<List<Integer>> getPermutations(int n) {
72
66
 
73
- {
67
+
74
68
 
75
- StringBuilder sb = new StringBuilder();
69
+ if (n < 0) return null;
76
70
 
77
71
 
78
72
 
79
- sb.append("[");
73
+ List<List<Integer>> permutationsList = new ArrayList<List<Integer>>();
80
74
 
81
75
 
82
76
 
83
- final int size = list.size();
77
+ if (n == 0) {
84
78
 
85
- for ( int i=0; i < size; ++i ) {
79
+ List<Integer> permutation = new ArrayList<Integer>();
86
80
 
81
+ permutation.add(0);
82
+
83
+ permutationsList.add(permutation);
84
+
85
+ } else {
86
+
87
+ final List<List<Integer>> prevPermutationsList = getPermutations(n - 1);
88
+
89
+ final Integer intN = new Integer(n);
90
+
91
+
92
+
93
+ for ( List<Integer> permutation : prevPermutationsList ) {
94
+
95
+ final int size = permutation.size();
96
+
97
+ for ( int i = 0; i <= size; ++i ) {
98
+
99
+ permutation.add(i, n);
100
+
87
- sb.append((i > 0 ? ",":"") + list.get(i));
101
+ permutationsList.add(new ArrayList<Integer>(permutation));
102
+
103
+ permutation.remove(intN);
104
+
105
+ }
106
+
107
+ permutation.clear();
108
+
109
+ }
110
+
111
+
112
+
113
+ prevPermutationsList.clear();
88
114
 
89
115
  }
90
116
 
91
- sb.append("]");
117
+
92
118
 
93
-
94
-
95
- return sb.toString();
119
+ return permutationsList;
96
120
 
97
121
  }
98
122
 
99
-
100
-
101
- /*
102
-
103
- * 0以上n以下の整数が1回ずつ出現するリストのすべてのパターンを返す。
104
-
105
- *
106
-
107
- * @param n
108
-
109
- * @return
110
-
111
- */
112
-
113
- private static List<List<Integer>> getPermutations(int n)
114
-
115
- {
116
-
117
- if ( n < 0 ) return null;
118
-
119
-
120
-
121
- List<List<Integer>> results = new ArrayList<List<Integer>>();
122
-
123
-
124
-
125
- if ( n == 0) {
126
-
127
- List<Integer> list = new ArrayList<Integer>();
128
-
129
- list.add(0);
130
-
131
- results.add(list);
132
-
133
- } else {
134
-
135
- List<List<Integer>> prevResults = getPermutations(n-1);
136
-
137
-
138
-
139
- for ( List<Integer> list : prevResults ) {
140
-
141
- final int size = list.size();
142
-
143
- for ( int i=0; i <= size; ++ i ) {
144
-
145
- if ( i < size )
146
-
147
- list.add(i, n);
148
-
149
- else
150
-
151
- list.add(n);
152
-
153
- results.add(copy(list));
154
-
155
- list.remove( new Integer(n) );
156
-
157
- }
158
-
159
- }
160
-
161
- }
162
-
163
-
164
-
165
- return results;
166
-
167
- }
168
-
169
-
170
-
171
- /*
172
-
173
- * 指定された整数リストのコピーを作成
174
-
175
- */
176
-
177
- private static List<Integer> copy(List<Integer> src)
178
-
179
- {
180
-
181
- List<Integer> list = new ArrayList<Integer>();
182
-
183
-
184
-
185
- final int size = src.size();
186
-
187
- for ( int i=0; i < size; ++ i ) {
188
-
189
- list.add(src.get(i));
190
-
191
- }
192
-
193
-
194
-
195
- return list;
196
-
197
- }
198
-
199
-
200
-
201
123
  }
202
-
203
-
204
124
 
205
125
 
206
126
 
@@ -208,11 +128,7 @@
208
128
 
209
129
  上記のmainメソッドの中で
210
130
 
211
-
212
-
213
131
  List<List<Integer>> list = getPermutations(4);
214
-
215
-
216
132
 
217
133
  としているところを
218
134
 
@@ -226,7 +142,7 @@
226
142
 
227
143
  にしたりしてみましたが問題なく動くのを確認しました。
228
144
 
229
- ただし私の手元の環境では、
145
+ ただし私の手元のPCでは、
230
146
 
231
147
  getPermutations(8);
232
148
 

9

テキスト修正

2015/06/14 16:53

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -2,9 +2,15 @@
2
2
 
3
3
 
4
4
 
5
+ お手本になるようなアルゴリズムや、それを実装したコードがきっと
6
+
7
+ あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
8
+
9
+
10
+
5
- 以下の getPermutations(int n)　が
11
+ 以下の getPermutations(int n)　が再帰で解のリストを
6
-
12
+
7
- 再帰で解のリストを求めるメソッドです。
13
+ 求めるメソッドです。
8
14
 
9
15
 
10
16
 

8

テキスト修正

2015/06/13 06:18

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -2,11 +2,9 @@
2
2
 
3
3
 
4
4
 
5
- 再帰を使ってスマートに出来ないか等、いろいろ考えてみましたが、
6
-
7
- 並べ替えた数列を作ること自体が目的ではないようですので、
8
-
9
- 以下のような、脳味噌に汗をかかない案を考えました。
5
+ 以下の getPermutations(int n)　が
6
+
7
+ 再帰で解のリストを求めるメソッドです。
10
8
 
11
9
 
12
10
 
@@ -26,67 +24,129 @@
26
24
 
27
25
 
28
26
 
29
- public static void main(String[] args) {
27
+ public static void main(String[] args)
28
+
30
-
29
+ {
30
+
31
+ // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
32
+
31
- List<String> results = makeStringOf0to4Digits();
33
+ List<List<Integer>> list = getPermutations(4);
34
+
35
+
36
+
32
-
37
+ // 結果の表示
38
+
33
-
39
+ final int size = list.size();
34
-
40
+
41
+
42
+
35
- int count = 0;
43
+ int counter = 0;
36
-
44
+
37
- for ( String e : results ) {
45
+ for ( int i = size-1; i >= 0; -- i ) {
38
-
46
+
39
- count ++;
47
+ counter ++;
40
-
48
+
41
- System.out.println(count + ":" + e);
49
+ System.out.println(counter + ":" + listString(list.get(i)));
42
-
50
+
43
- }
51
+ }
44
-
52
+
45
- }
53
+ }
46
-
47
-
48
-
49
-
50
-
54
+
55
+
56
+
57
+
58
+
51
- /**
59
+ /*
52
-
60
+
53
- * 0から4の数字を並べ替えた文字列のリストを返す。
61
+ * 整数のリストを、[0,1,2]のような形式の文字列にして返す。
54
62
 
55
63
  */
56
64
 
57
- private static List<String> makeStringOf0to4Digits()
58
-
59
- {
60
-
61
- List<String> results = new ArrayList<String>();
62
-
63
-
64
-
65
- String[] digits = { "0", "1", "2" ,"3", "4"};
66
-
67
-
68
-
69
- for ( int i0 = 0; i0 < digits.length; ++ i0 ) {
70
-
71
- for ( int i1 = 0; i1 < digits.length; ++ i1 ) {
72
-
73
- for ( int i2 = 0; i2 < digits.length; ++ i2 ) {
74
-
75
- for ( int i3 = 0; i3 < digits.length; ++ i3 ) {
76
-
77
- for ( int i4 = 0; i4 < digits.length; ++ i4 ) {
78
-
79
- String s = digits[i0] + digits[i1] +
80
-
81
- digits[i2] + digits[i3] + digits[i4] ;
82
-
83
- if ( ! hasDuplicateChars(s) )
84
-
85
- results.add(s);
86
-
87
- }
88
-
89
- }
65
+ private static String listString(List<Integer> list)
66
+
67
+ {
68
+
69
+ StringBuilder sb = new StringBuilder();
70
+
71
+
72
+
73
+ sb.append("[");
74
+
75
+
76
+
77
+ final int size = list.size();
78
+
79
+ for ( int i=0; i < size; ++i ) {
80
+
81
+ sb.append((i > 0 ? ",":"") + list.get(i));
82
+
83
+ }
84
+
85
+ sb.append("]");
86
+
87
+
88
+
89
+ return sb.toString();
90
+
91
+ }
92
+
93
+
94
+
95
+ /*
96
+
97
+ * 0以上n以下の整数が1回ずつ出現するリストのすべてのパターンを返す。
98
+
99
+ *
100
+
101
+ * @param n
102
+
103
+ * @return
104
+
105
+ */
106
+
107
+ private static List<List<Integer>> getPermutations(int n)
108
+
109
+ {
110
+
111
+ if ( n < 0 ) return null;
112
+
113
+
114
+
115
+ List<List<Integer>> results = new ArrayList<List<Integer>>();
116
+
117
+
118
+
119
+ if ( n == 0) {
120
+
121
+ List<Integer> list = new ArrayList<Integer>();
122
+
123
+ list.add(0);
124
+
125
+ results.add(list);
126
+
127
+ } else {
128
+
129
+ List<List<Integer>> prevResults = getPermutations(n-1);
130
+
131
+
132
+
133
+ for ( List<Integer> list : prevResults ) {
134
+
135
+ final int size = list.size();
136
+
137
+ for ( int i=0; i <= size; ++ i ) {
138
+
139
+ if ( i < size )
140
+
141
+ list.add(i, n);
142
+
143
+ else
144
+
145
+ list.add(n);
146
+
147
+ results.add(copy(list));
148
+
149
+ list.remove( new Integer(n) );
90
150
 
91
151
  }
92
152
 
@@ -102,294 +162,44 @@
102
162
 
103
163
 
104
164
 
105
- /**
165
+ /*
106
-
166
+
107
- * 指定された文字列の中に同じ文字があるかどうか判定
167
+ * 指定された整数リストのコピーを作成
108
-
109
- *
110
-
111
- * @param s
112
-
113
- * @return 重複する文字があればtrue、無ければfalase
114
168
 
115
169
  */
116
170
 
117
- private static boolean hasDuplicateChars(String s)
171
+ private static List<Integer> copy(List<Integer> src)
118
-
172
+
119
- {
173
+ {
120
-
121
- if ( s == null || s.length() == 0 )
174
+
122
-
123
- return false;
124
-
125
-
126
-
127
- List<Character> list = new ArrayList<Character>();
175
+ List<Integer> list = new ArrayList<Integer>();
176
+
177
+
178
+
128
-
179
+ final int size = src.size();
129
-
130
-
180
+
131
- for ( int i=0; i < s.length(); ++ i ) {
181
+ for ( int i=0; i < size; ++ i ) {
132
-
133
- char c = s.charAt(i);
182
+
134
-
135
- if ( list.contains(c) )
136
-
137
- return true;
138
-
139
- else
140
-
141
- list.add(c);
183
+ list.add(src.get(i));
142
-
184
+
143
- }
185
+ }
144
-
145
-
146
-
186
+
187
+
188
+
147
- return false;
189
+ return list;
148
-
190
+
149
- }
191
+ }
192
+
193
+
150
194
 
151
195
  }
152
196
 
153
197
 
154
198
 
199
+
200
+
155
201
  ```
156
202
 
157
-
158
-
159
- 順列の記号 nＰr を使うと、ご質問の場合の組み合わせ数は
160
-
161
-
162
-
163
- 5Ｐ5 = 5 * 4 * 3 * 2 * 1 ＝ 120
164
-
165
-
166
-
167
- となりますが、上記のプログラムを実行すると、行頭に通し番号を
168
-
169
- 表示しながら、0,1,2,3,4 を並べ替えて連結した、120通りの
170
-
171
- 文字列を表示します。
172
-
173
-
174
-
175
- とはいえ、5の5乗で、3125個の String s を生成するのは無駄が
176
-
177
- 多すぎで、あまりいいコードとはいえないので、あくまで最終手段の
178
-
179
- ご参考に留めていただければと思います。
180
-
181
-
182
-
183
- ---
184
-
185
-
186
-
187
- 追記します。
188
-
189
-
190
-
191
- さきほどの回答で示したコードが、あまりにも考えなさ杉と思ったので、
192
-
193
- 再帰でリストを作成する版を作成しました。
194
-
195
-
196
-
197
- 以下で、getPermutations(int n)　が再帰で解のリストを求めるメソッドです。
198
-
199
-
200
-
201
- ```lang-java
202
-
203
- package teratail;
204
-
205
-
206
-
207
- import java.util.ArrayList;
208
-
209
- import java.util.List;
210
-
211
-
212
-
213
- public class Q11179_2 {
214
-
215
-
216
-
217
- public static void main(String[] args)
218
-
219
- {
220
-
221
- // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
222
-
223
- List<List<Integer>> list = getPermutations(4);
224
-
225
-
226
-
227
- // 結果の表示
228
-
229
- final int size = list.size();
230
-
231
-
232
-
233
- int counter = 0;
234
-
235
- for ( int i = size-1; i >= 0; -- i ) {
236
-
237
- counter ++;
238
-
239
- System.out.println(counter + ":" + listString(list.get(i)));
240
-
241
- }
242
-
243
- }
244
-
245
-
246
-
247
-
248
-
249
- /*
250
-
251
- * 整数のリストを、[0,1,2]のような形式の文字列にして返す。
252
-
253
- */
254
-
255
- private static String listString(List<Integer> list)
256
-
257
- {
258
-
259
- StringBuilder sb = new StringBuilder();
260
-
261
-
262
-
263
- sb.append("[");
264
-
265
-
266
-
267
- final int size = list.size();
268
-
269
- for ( int i=0; i < size; ++i ) {
270
-
271
- sb.append((i > 0 ? ",":"") + list.get(i));
272
-
273
- }
274
-
275
- sb.append("]");
276
-
277
-
278
-
279
- return sb.toString();
280
-
281
- }
282
-
283
-
284
-
285
- /*
286
-
287
- * 0以上n以下の整数が1回ずつ出現するリストのすべてのパターンを返す。
288
-
289
- *
290
-
291
- * @param n
292
-
293
- * @return
294
-
295
- */
296
-
297
- private static List<List<Integer>> getPermutations(int n)
298
-
299
- {
300
-
301
- if ( n < 0 ) return null;
302
-
303
-
304
-
305
- List<List<Integer>> results = new ArrayList<List<Integer>>();
306
-
307
-
308
-
309
- if ( n == 0) {
310
-
311
- List<Integer> list = new ArrayList<Integer>();
312
-
313
- list.add(0);
314
-
315
- results.add(list);
316
-
317
- } else {
318
-
319
- List<List<Integer>> prevResults = getPermutations(n-1);
320
-
321
-
322
-
323
- for ( List<Integer> list : prevResults ) {
324
-
325
- final int size = list.size();
326
-
327
- for ( int i=0; i <= size; ++ i ) {
328
-
329
- if ( i < size )
330
-
331
- list.add(i, n);
332
-
333
- else
334
-
335
- list.add(n);
336
-
337
- results.add(copy(list));
338
-
339
- list.remove( new Integer(n) );
340
-
341
- }
342
-
343
- }
344
-
345
- }
346
-
347
-
348
-
349
- return results;
350
-
351
- }
352
-
353
-
354
-
355
- /*
356
-
357
- * 指定された整数リストのコピーを作成
358
-
359
- */
360
-
361
- private static List<Integer> copy(List<Integer> src)
362
-
363
- {
364
-
365
- List<Integer> list = new ArrayList<Integer>();
366
-
367
-
368
-
369
- final int size = src.size();
370
-
371
- for ( int i=0; i < size; ++ i ) {
372
-
373
- list.add(src.get(i));
374
-
375
- }
376
-
377
-
378
-
379
- return list;
380
-
381
- }
382
-
383
-
384
-
385
- }
386
-
387
-
388
-
389
-
390
-
391
- ```
392
-
393
203
  上記のmainメソッドの中で
394
204
 
395
205
 
@@ -406,11 +216,11 @@
406
216
 
407
217
  List<List<Integer>> list = getPermutations(0);
408
218
 
219
+
220
+
409
- にしたりしてみましたが、一応問題なく動きます。
221
+ にしたりしてみましたが問題なく動くのを確認しました。
410
-
411
-
412
-
222
+
413
- ※ただし私の手元の環境では、
223
+ ただし私の手元の環境では、
414
224
 
415
225
  getPermutations(8);
416
226
 
@@ -428,152 +238,8 @@
428
238
 
429
239
  となりました。
430
240
 
431
- 再帰で書いたものの実用的ではないかもしれません。
432
-
433
241
 
434
242
 
435
243
  ご参考まで。
436
244
 
437
- ---
245
+
438
-
439
-
440
-
441
- さらに追記します。
442
-
443
-
444
-
445
-
446
-
447
- 与題では、順列を構成する要素は { 0, 1, 2, 3, 4} の5個ですが、
448
-
449
- これが多い場合、たとえば、すべての半角英字（大文字）の順列を
450
-
451
- 考えると、構成要素は26個になります。
452
-
453
-
454
-
455
- これの順列の全リストを得たいとすると、以下のように
456
-
457
- テキストファイルを作成していく方法が考えられます。
458
-
459
-
460
-
461
-
462
-
463
- ・ファイル　AtoA.txt　は以下の行のみを含みます。
464
-
465
-
466
-
467
- A
468
-
469
-
470
-
471
- ・ファイル AtoB.txtは以下の2行を含みます。
472
-
473
-
474
-
475
- AB
476
-
477
- BA
478
-
479
-
480
-
481
- ・ファイル AtoC.txtは以下の6行を含みます。
482
-
483
-
484
-
485
- ABC
486
-
487
- ACB
488
-
489
- BAC
490
-
491
- BCA
492
-
493
- CAB
494
-
495
- CBA
496
-
497
-
498
-
499
- このような規則でファイルAto[A-Z].txtを作っていくこと
500
-
501
- にすると、欲しいのは
502
-
503
-
504
-
505
- AtoZ.txt
506
-
507
-
508
-
509
- です。
510
-
511
-
512
-
513
- ここで、アルファベットの列で最初からn番目の文字をα(n)と
514
-
515
- 書くことにします。つまり　α(1)=A, α(26)=Z　ですが、
516
-
517
- このとき、ファイル Atoα(n+1).txtは、ファイル Atoα(n).txt
518
-
519
- を元に作成することができます。
520
-
521
-
522
-
523
- それは以下のアルゴリズムによります。
524
-
525
-
526
-
527
- ファイル Atoα(n).txt の各行の文字列の、先頭と末尾、および
528
-
529
- すべての文字と文字との間に、新しいアルファベット α(n+1)を
530
-
531
- 挿入した文字列を作成し、それらをファイル Atoα(n+1).txt
532
-
533
- に出力します。
534
-
535
-
536
-
537
- たとえば、AtoB.txt　の行
538
-
539
-
540
-
541
- AB
542
-
543
-
544
-
545
- からは、AtoC.txtに書き込むべき行として
546
-
547
-
548
-
549
- CAB
550
-
551
- ACB
552
-
553
- ABC
554
-
555
-
556
-
557
- の3行が生成されます。
558
-
559
-
560
-
561
- このようにして、AtoA.txtは手入力で作成することにして
562
-
563
- 1回のプログラムの実行では
564
-
565
- ファイル Atoα(n-1).txt からAtoα(n).txt
566
-
567
- を作るだけのものにすれば、少なくとも再帰を使わないで
568
-
569
- （つまりヒープを消尽しないで）
570
-
571
- AtoZ.txtが得られるものと思います。
572
-
573
-
574
-
575
- ただし、要素がさらに多くなると、１つのファイルの行数が多くなりすぎるとか、
576
-
577
- 実行時間がかかる、といった問題が出てきますが、実用的な方法として
578
-
579
- 思いついたことは以上です。

7

テキスト追加

2015/06/13 06:13

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -564,7 +564,7 @@
564
564
 
565
565
  ファイル Atoα(n-1).txt からAtoα(n).txt
566
566
 
567
- を作るだけのものにすれば、再帰を使わないで
567
+ を作るだけのものにすれば、少なくとも再帰を使わないで
568
568
 
569
569
  （つまりヒープを消尽しないで）
570
570
 
@@ -572,8 +572,8 @@
572
572
 
573
573
 
574
574
 
575
-
575
+ ただし、要素がさらに多くなると、１つのファイルの行数が多くなりすぎるとか、
576
-
576
+
577
- それなりに手間がかかりますが、実用的な方法として
577
+ 実行時間がかかる、といった問題が出てきますが、実用的な方法として
578
578
 
579
579
  思いついたことは以上です。

6

テキスト追加

2015/06/12 10:07

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -434,6 +434,146 @@
434
434
 
435
435
  ご参考まで。
436
436
 
437
-
437
+ ---
438
+
439
+
440
+
438
-
441
+ さらに追記します。
442
+
443
+
444
+
445
+
446
+
439
-
447
+ 与題では、順列を構成する要素は { 0, 1, 2, 3, 4} の5個ですが、
448
+
449
+ これが多い場合、たとえば、すべての半角英字（大文字）の順列を
450
+
451
+ 考えると、構成要素は26個になります。
452
+
453
+
454
+
455
+ これの順列の全リストを得たいとすると、以下のように
456
+
457
+ テキストファイルを作成していく方法が考えられます。
458
+
459
+
460
+
461
+
462
+
463
+ ・ファイル　AtoA.txt　は以下の行のみを含みます。
464
+
465
+
466
+
467
+ A
468
+
469
+
470
+
471
+ ・ファイル AtoB.txtは以下の2行を含みます。
472
+
473
+
474
+
475
+ AB
476
+
477
+ BA
478
+
479
+
480
+
481
+ ・ファイル AtoC.txtは以下の6行を含みます。
482
+
483
+
484
+
485
+ ABC
486
+
487
+ ACB
488
+
489
+ BAC
490
+
491
+ BCA
492
+
493
+ CAB
494
+
495
+ CBA
496
+
497
+
498
+
499
+ このような規則でファイルAto[A-Z].txtを作っていくこと
500
+
501
+ にすると、欲しいのは
502
+
503
+
504
+
505
+ AtoZ.txt
506
+
507
+
508
+
509
+ です。
510
+
511
+
512
+
513
+ ここで、アルファベットの列で最初からn番目の文字をα(n)と
514
+
515
+ 書くことにします。つまり　α(1)=A, α(26)=Z　ですが、
516
+
517
+ このとき、ファイル Atoα(n+1).txtは、ファイル Atoα(n).txt
518
+
519
+ を元に作成することができます。
520
+
521
+
522
+
523
+ それは以下のアルゴリズムによります。
524
+
525
+
526
+
527
+ ファイル Atoα(n).txt の各行の文字列の、先頭と末尾、および
528
+
529
+ すべての文字と文字との間に、新しいアルファベット α(n+1)を
530
+
531
+ 挿入した文字列を作成し、それらをファイル Atoα(n+1).txt
532
+
533
+ に出力します。
534
+
535
+
536
+
537
+ たとえば、AtoB.txt　の行
538
+
539
+
540
+
541
+ AB
542
+
543
+
544
+
545
+ からは、AtoC.txtに書き込むべき行として
546
+
547
+
548
+
549
+ CAB
550
+
551
+ ACB
552
+
553
+ ABC
554
+
555
+
556
+
557
+ の3行が生成されます。
558
+
559
+
560
+
561
+ このようにして、AtoA.txtは手入力で作成することにして
562
+
563
+ 1回のプログラムの実行では
564
+
565
+ ファイル Atoα(n-1).txt からAtoα(n).txt
566
+
567
+ を作るだけのものにすれば、再帰を使わないで
568
+
569
+ （つまりヒープを消尽しないで）
570
+
571
+ AtoZ.txtが得られるものと思います。
572
+
573
+
574
+
575
+
576
+
577
+ それなりに手間がかかりますが、実用的な方法として
578
+
579
+ 思いついたことは以上です。

5

テキスト修正

2015/06/12 09:51

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -410,6 +410,28 @@
410
410
 
411
411
 
412
412
 
413
+ ※ただし私の手元の環境では、
414
+
415
+ getPermutations(8);
416
+
417
+ まではいけましたが
418
+
419
+ getPermutations(9);
420
+
421
+ でヒープを使い果たして
422
+
423
+
424
+
425
+ Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
426
+
427
+
428
+
429
+ となりました。
430
+
431
+ 再帰で書いたものの実用的ではないかもしれません。
432
+
433
+
434
+
413
435
  ご参考まで。
414
436
 
415
437
 

4

テキスト修正

2015/06/12 08:32

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -186,8 +186,14 @@
186
186
 
187
187
  追記します。
188
188
 
189
+
190
+
191
+ さきほどの回答で示したコードが、あまりにも考えなさ杉と思ったので、
192
+
189
193
  再帰でリストを作成する版を作成しました。
190
194
 
195
+
196
+
191
197
  以下で、getPermutations(int n)　が再帰で解のリストを求めるメソッドです。
192
198
 
193
199
 

3

ソース修正

2015/06/12 08:05

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -310,11 +310,11 @@
310
310
 
311
311
  } else {
312
312
 
313
- List<List<Integer>> prevList = getPermutations(n-1);
313
+ List<List<Integer>> prevResults = getPermutations(n-1);
314
-
315
-
316
-
314
+
315
+
316
+
317
- for ( List<Integer> list : prevList) {
317
+ for ( List<Integer> list : prevResults ) {
318
318
 
319
319
  final int size = list.size();
320
320
 

2

テキスト追加

2015/06/12 07:46

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -177,3 +177,235 @@
177
177
  多すぎで、あまりいいコードとはいえないので、あくまで最終手段の
178
178
 
179
179
  ご参考に留めていただければと思います。
180
+
181
+
182
+
183
+ ---
184
+
185
+
186
+
187
+ 追記します。
188
+
189
+ 再帰でリストを作成する版を作成しました。
190
+
191
+ 以下で、getPermutations(int n)　が再帰で解のリストを求めるメソッドです。
192
+
193
+
194
+
195
+ ```lang-java
196
+
197
+ package teratail;
198
+
199
+
200
+
201
+ import java.util.ArrayList;
202
+
203
+ import java.util.List;
204
+
205
+
206
+
207
+ public class Q11179_2 {
208
+
209
+
210
+
211
+ public static void main(String[] args)
212
+
213
+ {
214
+
215
+ // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
216
+
217
+ List<List<Integer>> list = getPermutations(4);
218
+
219
+
220
+
221
+ // 結果の表示
222
+
223
+ final int size = list.size();
224
+
225
+
226
+
227
+ int counter = 0;
228
+
229
+ for ( int i = size-1; i >= 0; -- i ) {
230
+
231
+ counter ++;
232
+
233
+ System.out.println(counter + ":" + listString(list.get(i)));
234
+
235
+ }
236
+
237
+ }
238
+
239
+
240
+
241
+
242
+
243
+ /*
244
+
245
+ * 整数のリストを、[0,1,2]のような形式の文字列にして返す。
246
+
247
+ */
248
+
249
+ private static String listString(List<Integer> list)
250
+
251
+ {
252
+
253
+ StringBuilder sb = new StringBuilder();
254
+
255
+
256
+
257
+ sb.append("[");
258
+
259
+
260
+
261
+ final int size = list.size();
262
+
263
+ for ( int i=0; i < size; ++i ) {
264
+
265
+ sb.append((i > 0 ? ",":"") + list.get(i));
266
+
267
+ }
268
+
269
+ sb.append("]");
270
+
271
+
272
+
273
+ return sb.toString();
274
+
275
+ }
276
+
277
+
278
+
279
+ /*
280
+
281
+ * 0以上n以下の整数が1回ずつ出現するリストのすべてのパターンを返す。
282
+
283
+ *
284
+
285
+ * @param n
286
+
287
+ * @return
288
+
289
+ */
290
+
291
+ private static List<List<Integer>> getPermutations(int n)
292
+
293
+ {
294
+
295
+ if ( n < 0 ) return null;
296
+
297
+
298
+
299
+ List<List<Integer>> results = new ArrayList<List<Integer>>();
300
+
301
+
302
+
303
+ if ( n == 0) {
304
+
305
+ List<Integer> list = new ArrayList<Integer>();
306
+
307
+ list.add(0);
308
+
309
+ results.add(list);
310
+
311
+ } else {
312
+
313
+ List<List<Integer>> prevList = getPermutations(n-1);
314
+
315
+
316
+
317
+ for ( List<Integer> list : prevList) {
318
+
319
+ final int size = list.size();
320
+
321
+ for ( int i=0; i <= size; ++ i ) {
322
+
323
+ if ( i < size )
324
+
325
+ list.add(i, n);
326
+
327
+ else
328
+
329
+ list.add(n);
330
+
331
+ results.add(copy(list));
332
+
333
+ list.remove( new Integer(n) );
334
+
335
+ }
336
+
337
+ }
338
+
339
+ }
340
+
341
+
342
+
343
+ return results;
344
+
345
+ }
346
+
347
+
348
+
349
+ /*
350
+
351
+ * 指定された整数リストのコピーを作成
352
+
353
+ */
354
+
355
+ private static List<Integer> copy(List<Integer> src)
356
+
357
+ {
358
+
359
+ List<Integer> list = new ArrayList<Integer>();
360
+
361
+
362
+
363
+ final int size = src.size();
364
+
365
+ for ( int i=0; i < size; ++ i ) {
366
+
367
+ list.add(src.get(i));
368
+
369
+ }
370
+
371
+
372
+
373
+ return list;
374
+
375
+ }
376
+
377
+
378
+
379
+ }
380
+
381
+
382
+
383
+
384
+
385
+ ```
386
+
387
+ 上記のmainメソッドの中で
388
+
389
+
390
+
391
+ List<List<Integer>> list = getPermutations(4);
392
+
393
+
394
+
395
+ としているところを
396
+
397
+ List<List<Integer>> list = getPermutations(5);
398
+
399
+ にしたり、
400
+
401
+ List<List<Integer>> list = getPermutations(0);
402
+
403
+ にしたりしてみましたが、一応問題なく動きます。
404
+
405
+
406
+
407
+ ご参考まで。
408
+
409
+
410
+
411
+

1

テキスト修正

2015/06/12 07:45

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -172,6 +172,8 @@
172
172
 
173
173
 
174
174
 
175
- とはいえ、やはりあまりいいコードとはいえないので、
175
+ とはいえ、5の5乗で、3125個の String s を生成するのは無駄が
176
176
 
177
+ 多すぎで、あまりいいコードとはいえないので、あくまで最終手段の
178
+
177
- あくまで、最終手段のご参考になればと思います。
179
+ ご参考に留めていただければと思います。