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

編集履歴

回答編集履歴

25

テキスト修正

2015/06/14 21:35

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -35,7 +35,7 @@
35
35
  // 0以上４以下の整数のすべての順列のリストを作成
36
36
  List<List<Integer>> list = getPermutations(4);
37
37
 
38
- // 結果の表示（逆順にリスト要素を出力
38
+ // 結果の表示（逆順にリスト要素を出力）
39
39
  int counter = 0;
40
40
  for (int i = list.size() - 1; i >= 0; --i) {
41
41
  counter++;

24

テキスト修正

2015/06/14 21:35

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -35,10 +35,9 @@
35
35
  // 0以上４以下の整数のすべての順列のリストを作成
36
36
  List<List<Integer>> list = getPermutations(4);
37
37
 
38
- // 結果の表示（逆順にリスト要素を出力）
38
+ // 結果の表示（逆順にリスト要素を出力
39
- final int size = list.size();
40
39
  int counter = 0;
41
- for (int i = size - 1; i >= 0; --i) {
40
+ for (int i = list.size() - 1; i >= 0; --i) {
42
41
  counter++;
43
42
  System.out.println(counter + ":" + list.get(i));
44
43
  }

23

テキスト修正

2015/06/14 21:31

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -7,9 +7,9 @@
7
7
  > 0 以上 n以下の(n+1)個の整数を要素とする順列 p(n+1) は、
8
8
  > 0 以上 (n-1)以下の n個の整数を要素とするある順列 p(n)に、
9
9
  > 要素 n を追加して作成する。
10
- > その際に、要素 n を追加する場所は、以下のnヶ所ある。
10
+ > その際に、要素 n を追加する場所は、以下の(n+1)ヶ所ある。
11
11
  > 　・p(n)の先頭
12
- > 　・p(n)の要素と要素の間（ (n-1)ヶ所ある。）
12
+ > 　・p(n)の要素と要素の間（これは、(n-1)ヶ所ある。）
13
13
  > 　・p(n)の末尾
14
14
  たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
15
15
  要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の

22

テキスト修正

2015/06/14 19:18

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -4,9 +4,13 @@
4
4
  あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
5
5
 
6
6
  　基本的な考え方は以下です。
7
- > 0 以上 n以下の(n+1)個の整数を要素とする順列は、
7
+ > 0 以上 n以下の(n+1)個の整数を要素とする順列 p(n+1) は、
8
- > 0 以上 (n-1)以下の n個の整数を要素とする順列の
8
+ > 0 以上 (n-1)以下の n個の整数を要素とするある順列 p(n)に、
9
- > 要素と要素の間、および先頭と末尾に n を追加して作成できる。
9
+ > 要素 n を追加して作成する。
10
+ > その際に、要素 n を追加する場所は、以下のnヶ所ある。
11
+ > 　・p(n)の先頭
12
+ > 　・p(n)の要素と要素の間（ (n-1)ヶ所ある。）
13
+ > 　・p(n)の末尾
10
14
  たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
11
15
  要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の
12
16
  ４カ所あり、これらの追加する位置の違いによって４つの順列、

21

テキスト修正

2015/06/14 19:16

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -41,7 +41,7 @@
41
41
  }
42
42
 
43
43
  /*
44
- * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
44
+ * 0以上 n以下の整数を要素とする順列（を表現したリスト）を
45
45
  * 要素として持つリストを作成
46
46
  */
47
47
  private static List<List<Integer>> getPermutations(Integer n) {

20

テキスト修正

2015/06/14 19:04

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -1,22 +1,21 @@
1
1
  こんにちは。
2
2
 
3
- お手本になるようなアルゴリズムや、それを実装したコードがきっと
3
+ 　お手本になるようなアルゴリズムや、それを実装したコードがきっと
4
4
  あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
5
5
 
6
- 基本的な考え方は以下です。
6
+ 　基本的な考え方は以下です。
7
7
  > 0 以上 n以下の(n+1)個の整数を要素とする順列は、
8
8
  > 0 以上 (n-1)以下の n個の整数を要素とする順列の
9
9
  > 要素と要素の間、および先頭と末尾に n を追加して作成できる。
10
10
  たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
11
11
  要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の
12
- ４カ所あり、それぞれの追加する位置によって、
12
+ ４カ所あり、これらの追加する位置の違いによって４つの順列、
13
13
  [3,0,1,2]
14
14
  [0,3,1,2]
15
15
  [0,1,3,2]
16
16
  [0,1,2,3]
17
- が作成されます。
18
- この考え方で再帰のアルゴリズムを作成しました。
17
+ が作成されます。この考え方で再帰のアルゴリズムを作成しました。
19
- 以下のソースで、
18
+ 　以下のソースで、
20
19
  　private static List<List<Integer>> getPermutations(Integer n)
21
20
  が再帰で解のリストを求めるメソッドです。
22
21
 
@@ -78,7 +77,7 @@
78
77
  }
79
78
  }
80
79
  ```
81
- 上記を実行すると、以下のような出力が得られます。
80
+ 　上記を実行すると、以下のような出力が得られます。
82
81
  行頭の数字は、組み合わせの数を数えるためのものです。
83
82
  ```lang-xxx
84
83
  1:[0, 1, 2, 3, 4]

19

テキスト修正

2015/06/14 18:59

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -3,6 +3,19 @@
3
3
  お手本になるようなアルゴリズムや、それを実装したコードがきっと
4
4
  あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
5
5
 
6
+ 基本的な考え方は以下です。
7
+ > 0 以上 n以下の(n+1)個の整数を要素とする順列は、
8
+ > 0 以上 (n-1)以下の n個の整数を要素とする順列の
9
+ > 要素と要素の間、および先頭と末尾に n を追加して作成できる。
10
+ たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
11
+ 要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の
12
+ ４カ所あり、それぞれの追加する位置によって、
13
+ [3,0,1,2]
14
+ [0,3,1,2]
15
+ [0,1,3,2]
16
+ [0,1,2,3]
17
+ が作成されます。
18
+ この考え方で再帰のアルゴリズムを作成しました。
6
19
  以下のソースで、
7
20
  　private static List<List<Integer>> getPermutations(Integer n)
8
21
  が再帰で解のリストを求めるメソッドです。

18

テキスト修正

2015/06/14 18:57

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -9,6 +9,7 @@
9
9
 
10
10
  ```lang-java
11
11
  import java.util.ArrayList;
12
+ import java.util.Arrays;
12
13
  import java.util.List;
13
14
 
14
15
  public class Q11179 {
@@ -29,7 +30,7 @@
29
30
 
30
31
  /*
31
32
  * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
32
- 　　 * 要素として持つリストを作成
33
+ * 要素として持つリストを作成
33
34
  */
34
35
  private static List<List<Integer>> getPermutations(Integer n) {
35
36
 
@@ -40,11 +41,9 @@
40
41
  // このメソッドの返り値となるリストを作成
41
42
  List<List<Integer>> results = new ArrayList<List<Integer>>();
42
43
 
43
- // n = 0 の場合、[0]だけを要素とするリストを返す。
44
+ // n = 0 の場合、要素の追加が可能なリスト[0]を要素とするリストを返す。
44
- if (n == 0) {
45
+ if (n == 0) {
45
- List<Integer> permutation = new ArrayList<Integer>();
46
+ results.add(new ArrayList<Integer>(Arrays.asList(0)));
46
- permutation.add(0);
47
- results.add(permutation);
48
47
  return results;
49
48
  }
50
49
 

17

テキスト修正

2015/06/14 18:13

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -4,7 +4,7 @@
4
4
  あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
5
5
 
6
6
  以下のソースで、
7
- 　private static List<List<Integer>> getPermutations(int n)
7
+ 　private static List<List<Integer>> getPermutations(Integer n)
8
8
  が再帰で解のリストを求めるメソッドです。
9
9
 
10
10
  ```lang-java

16

テキスト修正

2015/06/14 17:57

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -28,7 +28,8 @@
28
28
  }
29
29
 
30
30
  /*
31
- * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを 要素として持つリストを作成
31
+ * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
32
+ 　　 * 要素として持つリストを作成
32
33
  */
33
34
  private static List<List<Integer>> getPermutations(Integer n) {
34
35
 

15

テキスト修正

2015/06/14 17:52

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -21,43 +21,47 @@
21
21
  // 結果の表示（逆順にリスト要素を出力）
22
22
  final int size = list.size();
23
23
  int counter = 0;
24
- for ( int i = size - 1; i >= 0; --i ) {
24
+ for (int i = size - 1; i >= 0; --i) {
25
25
  counter++;
26
26
  System.out.println(counter + ":" + list.get(i));
27
27
  }
28
28
  }
29
29
 
30
30
  /*
31
- * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
31
+ * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを 要素として持つリストを作成
32
- * 要素として持つリストを作成
33
32
  */
34
33
  private static List<List<Integer>> getPermutations(Integer n) {
35
-
36
- if (n == null || n < 0) return null;
37
34
 
38
- List<List<Integer>> permutationsList = new ArrayList<List<Integer>>();
35
+ // n が不正な値のとき、何もせず null を返して終了
36
+ if (n == null || n < 0)
37
+ return null;
39
38
 
39
+ // このメソッドの返り値となるリストを作成
40
+ List<List<Integer>> results = new ArrayList<List<Integer>>();
41
+
42
+ // n = 0 の場合、[0]だけを要素とするリストを返す。
40
43
  if (n == 0) {
41
44
  List<Integer> permutation = new ArrayList<Integer>();
42
45
  permutation.add(0);
43
- permutationsList.add(permutation);
46
+ results.add(permutation);
44
- } else {
47
+ return results;
48
+ }
49
+
50
+ // n > 0 の場合、まず、(n-1)に対する解のリストを再帰で取得
45
- final List<List<Integer>> prevPermutationsList = getPermutations(n - 1);
51
+ List<List<Integer>> prevResults = getPermutations(n - 1);
52
+
46
-
53
+ // (n-1)のときのリストをループし、要素の順列に n を加えた順列を作成
47
- for ( List<Integer> permutation : prevPermutationsList ) {
54
+ for (List<Integer> permutation : prevResults) {
48
- final int size = permutation.size();
49
- for ( int i = 0; i <= size; ++i ) {
55
+ for (int i = 0; i <= n; ++i) { // n を加える位置についてのループ
50
- permutation.add(i, n);
56
+ permutation.add(i, n);
51
- permutationsList.add(new ArrayList<Integer>(permutation));
57
+ results.add(new ArrayList<Integer>(permutation));
52
- permutation.remove(n);
58
+ permutation.remove(n);
53
- }
54
- permutation.clear();
55
59
  }
56
-
57
- prevPermutationsList.clear();
60
+ permutation.clear(); // 全要素を削除しておく
58
61
  }
59
-
62
+ prevResults.clear(); // 全要素を削除しておく
63
+
60
- return permutationsList;
64
+ return results;
61
65
  }
62
66
  }
63
67
  ```

14

テキスト修正

2015/06/14 17:51

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -31,9 +31,9 @@
31
31
  * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
32
32
  * 要素として持つリストを作成
33
33
  */
34
- private static List<List<Integer>> getPermutations(int n) {
34
+ private static List<List<Integer>> getPermutations(Integer n) {
35
35
 
36
- if (n < 0) return null;
36
+ if (n == null || n < 0) return null;
37
37
 
38
38
  List<List<Integer>> permutationsList = new ArrayList<List<Integer>>();
39
39
 
@@ -43,14 +43,13 @@
43
43
  permutationsList.add(permutation);
44
44
  } else {
45
45
  final List<List<Integer>> prevPermutationsList = getPermutations(n - 1);
46
- final Integer intN = new Integer(n);
47
46
 
48
47
  for ( List<Integer> permutation : prevPermutationsList ) {
49
48
  final int size = permutation.size();
50
49
  for ( int i = 0; i <= size; ++i ) {
51
50
  permutation.add(i, n);
52
51
  permutationsList.add(new ArrayList<Integer>(permutation));
53
- permutation.remove(intN);
52
+ permutation.remove(n);
54
53
  }
55
54
  permutation.clear();
56
55
  }
@@ -61,7 +60,6 @@
61
60
  return permutationsList;
62
61
  }
63
62
  }
64
-
65
63
  ```
66
64
  上記を実行すると、以下のような出力が得られます。
67
65
  行頭の数字は、組み合わせの数を数えるためのものです。

13

テキスト修正

2015/06/14 17:24

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -63,8 +63,8 @@
63
63
  }
64
64
 
65
65
  ```
66
-
67
66
  上記を実行すると、以下のような出力が得られます。
67
+ 行頭の数字は、組み合わせの数を数えるためのものです。
68
68
  ```lang-xxx
69
69
  1:[0, 1, 2, 3, 4]
70
70
  2:[0, 1, 2, 4, 3]
@@ -77,8 +77,12 @@
77
77
  119:[3, 4, 2, 1, 0]
78
78
  120:[4, 3, 2, 1, 0]
79
79
  ```
80
+ ５個の要素による順列の数は、公式nPr = n!/(n-r)!　に n=r=5 を代入して
80
81
 
82
+ 5P5 = 5!/(5-5)! = (5*4*3*2*1)/0! = 120/1 = 120
83
+
84
+ ですので、出力例の行数は合っています。
81
- ソースコードのmainメソッドの中で
85
+ また、ソースコードのmainメソッドの中で
82
86
  　List<List<Integer>> list = getPermutations(4);
83
87
  としているところを
84
88
  　List<List<Integer>> list = getPermutations(5);

12

テキスト修正

2015/06/14 17:07

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -3,8 +3,9 @@
3
3
  お手本になるようなアルゴリズムや、それを実装したコードがきっと
4
4
  あるのだろうなと思いつつ、自分の頭の体操としてやってみました。
5
5
 
6
+ 以下のソースで、
6
- 以下の getPermutations(int n)　が再帰で解のリストを
7
+ 　private static List<List<Integer>> getPermutations(int n)
7
- 求めるメソッドです。
8
+ が再帰で解のリストを求めるメソッドです。
8
9
 
9
10
  ```lang-java
10
11
  import java.util.ArrayList;
@@ -78,30 +79,20 @@
78
79
  ```
79
80
 
80
81
  ソースコードのmainメソッドの中で
81
-
82
82
  　List<List<Integer>> list = getPermutations(4);
83
-
84
83
  としているところを
85
-
86
84
  　List<List<Integer>> list = getPermutations(5);
87
-
88
85
  にしたり、
89
-
90
86
  　List<List<Integer>> list = getPermutations(0);
91
-
92
87
  にしたりしてみましたが問題なく動くのを確認しました。
93
88
  ただし私の手元のPCでは、
94
-
95
89
  getPermutations(8);
96
-
97
90
  まではいけましたが
98
-
99
91
  getPermutations(9);
100
-
101
92
  でヒープを使い果たして
102
93
 
103
94
  Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
104
95
 
105
96
  となりました。
106
97
 
107
- ご参考まで。
98
+ 以上、ご参考になれば幸いです。

11

テキスト修正

2015/06/14 17:01

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -62,18 +62,42 @@
62
62
  }
63
63
 
64
64
  ```
65
+
66
+ 上記を実行すると、以下のような出力が得られます。
67
+ ```lang-xxx
68
+ 1:[0, 1, 2, 3, 4]
69
+ 2:[0, 1, 2, 4, 3]
70
+ 3:[0, 1, 4, 2, 3]
71
+ 4:[0, 4, 1, 2, 3]
72
+ 5:[4, 0, 1, 2, 3]
73
+ ・・・
74
+ 117:[3, 2, 1, 4, 0]
75
+ 118:[3, 2, 4, 1, 0]
76
+ 119:[3, 4, 2, 1, 0]
77
+ 120:[4, 3, 2, 1, 0]
78
+ ```
79
+
65
- 上記のmainメソッドの中で
80
+ ソースコードのmainメソッドの中で
81
+
66
- List<List<Integer>> list = getPermutations(4);
82
+ 　List<List<Integer>> list = getPermutations(4);
83
+
67
84
  としているところを
85
+
68
- List<List<Integer>> list = getPermutations(5);
86
+ 　List<List<Integer>> list = getPermutations(5);
87
+
69
88
  にしたり、
70
- List<List<Integer>> list = getPermutations(0);
71
89
 
90
+ 　List<List<Integer>> list = getPermutations(0);
91
+
72
92
  にしたりしてみましたが問題なく動くのを確認しました。
73
93
  ただし私の手元のPCでは、
94
+
74
95
  getPermutations(8);
96
+
75
97
  まではいけましたが
98
+
76
99
  getPermutations(9);
100
+
77
101
  でヒープを使い果たして
78
102
 
79
103
  Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

10

サンプルコード修正

2015/06/14 16:59

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -7,112 +7,70 @@
7
7
  求めるメソッドです。
8
8
 
9
9
  ```lang-java
10
- package teratail;
11
-
12
10
  import java.util.ArrayList;
13
11
  import java.util.List;
14
12
 
15
13
  public class Q11179 {
16
14
 
17
- public static void main(String[] args)
15
+ public static void main(String[] args) {
18
- {
16
+
19
- // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
17
+ // 0以上４以下の整数のすべての順列のリストを作成
20
18
  List<List<Integer>> list = getPermutations(4);
21
19
 
22
- // 結果の表示
20
+ // 結果の表示（逆順にリスト要素を出力）
23
21
  final int size = list.size();
24
-
25
22
  int counter = 0;
26
- for ( int i = size-1; i >= 0; -- i ) {
23
+ for ( int i = size - 1; i >= 0; --i ) {
27
- counter ++;
24
+ counter++;
28
- System.out.println(counter + ":" + listString(list.get(i)));
25
+ System.out.println(counter + ":" + list.get(i));
29
26
  }
30
27
  }
31
28
 
32
-
33
29
  /*
34
- * 整数のリストを、[0,1,2]のような形式の文字列にして返す。
30
+ * 0以上 n以下の整数が1回ずつ出現するリストのすべてのパターンを
31
+ * 要素として持つリストを作成
35
32
  */
36
- private static String listString(List<Integer> list)
33
+ private static List<List<Integer>> getPermutations(int n) {
37
- {
34
+
38
- StringBuilder sb = new StringBuilder();
35
+ if (n < 0) return null;
39
36
 
40
- sb.append("[");
37
+ List<List<Integer>> permutationsList = new ArrayList<List<Integer>>();
41
38
 
42
- final int size = list.size();
43
- for ( int i=0; i < size; ++i ) {
44
- sb.append((i > 0 ? ",":"") + list.get(i));
45
- }
46
- sb.append("]");
47
-
48
- return sb.toString();
49
- }
50
-
51
- /*
52
- * 0以上n以下の整数が1回ずつ出現するリストのすべてのパターンを返す。
53
- *
54
- * @param n
55
- * @return
56
- */
57
- private static List<List<Integer>> getPermutations(int n)
58
- {
59
- if ( n < 0 ) return null;
60
-
61
- List<List<Integer>> results = new ArrayList<List<Integer>>();
62
-
63
- if ( n == 0) {
39
+ if (n == 0) {
64
- List<Integer> list = new ArrayList<Integer>();
40
+ List<Integer> permutation = new ArrayList<Integer>();
65
- list.add(0);
41
+ permutation.add(0);
66
- results.add(list);
42
+ permutationsList.add(permutation);
67
43
  } else {
68
- List<List<Integer>> prevResults = getPermutations(n-1);
44
+ final List<List<Integer>> prevPermutationsList = getPermutations(n - 1);
69
-
45
+ final Integer intN = new Integer(n);
46
+
70
- for ( List<Integer> list : prevResults ) {
47
+ for ( List<Integer> permutation : prevPermutationsList ) {
71
- final int size = list.size();
48
+ final int size = permutation.size();
72
- for ( int i=0; i <= size; ++ i ) {
49
+ for ( int i = 0; i <= size; ++i ) {
73
- if ( i < size )
74
- list.add(i, n);
50
+ permutation.add(i, n);
75
- else
76
- list.add(n);
51
+ permutationsList.add(new ArrayList<Integer>(permutation));
77
- results.add(copy(list));
52
+ permutation.remove(intN);
78
- list.remove( new Integer(n) );
79
53
  }
54
+ permutation.clear();
80
55
  }
56
+
57
+ prevPermutationsList.clear();
81
58
  }
82
-
59
+
83
- return results;
60
+ return permutationsList;
84
61
  }
85
-
86
- /*
87
- * 指定された整数リストのコピーを作成
88
- */
89
- private static List<Integer> copy(List<Integer> src)
90
- {
91
- List<Integer> list = new ArrayList<Integer>();
92
-
93
- final int size = src.size();
94
- for ( int i=0; i < size; ++ i ) {
95
- list.add(src.get(i));
96
- }
97
-
98
- return list;
99
- }
100
-
101
62
  }
102
63
 
103
-
104
64
  ```
105
65
  上記のmainメソッドの中で
106
-
107
66
  List<List<Integer>> list = getPermutations(4);
108
-
109
67
  としているところを
110
68
  List<List<Integer>> list = getPermutations(5);
111
69
  にしたり、
112
70
  List<List<Integer>> list = getPermutations(0);
113
71
 
114
72
  にしたりしてみましたが問題なく動くのを確認しました。
115
- ただし私の手元の環境では、
73
+ ただし私の手元のPCでは、
116
74
  getPermutations(8);
117
75
  まではいけましたが
118
76
  getPermutations(9);

9

テキスト修正

2015/06/14 16:53

投稿

jun68ykt
jun68ykt

スコア9058

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

8

テキスト修正

2015/06/13 06:18

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -1,8 +1,7 @@
1
1
  こんにちは。
2
2
 
3
- 再帰を使ってスマートに出来ないか等、いろいろ考えてみましたが、
4
- 並べ替えた数列を作ること自体が目的ではないようですので、
5
- 以下のような、脳味噌に汗をかかない案を考えました。
3
+ 以下の getPermutations(int n)　が
4
+ 再帰で解のリストを求めるメソッドです。
6
5
 
7
6
  ```lang-java
8
7
  package teratail;
@@ -12,100 +11,6 @@
12
11
 
13
12
  public class Q11179 {
14
13
 
15
- public static void main(String[] args) {
16
- List<String> results = makeStringOf0to4Digits();
17
-
18
- int count = 0;
19
- for ( String e : results ) {
20
- count ++;
21
- System.out.println(count + ":" + e);
22
- }
23
- }
24
-
25
-
26
- /**
27
- * 0から4の数字を並べ替えた文字列のリストを返す。
28
- */
29
- private static List<String> makeStringOf0to4Digits()
30
- {
31
- List<String> results = new ArrayList<String>();
32
-
33
- String[] digits = { "0", "1", "2" ,"3", "4"};
34
-
35
- for ( int i0 = 0; i0 < digits.length; ++ i0 ) {
36
- for ( int i1 = 0; i1 < digits.length; ++ i1 ) {
37
- for ( int i2 = 0; i2 < digits.length; ++ i2 ) {
38
- for ( int i3 = 0; i3 < digits.length; ++ i3 ) {
39
- for ( int i4 = 0; i4 < digits.length; ++ i4 ) {
40
- String s = digits[i0] + digits[i1] +
41
- digits[i2] + digits[i3] + digits[i4] ;
42
- if ( ! hasDuplicateChars(s) )
43
- results.add(s);
44
- }
45
- }
46
- }
47
- }
48
- }
49
-
50
- return results;
51
- }
52
-
53
- /**
54
- * 指定された文字列の中に同じ文字があるかどうか判定
55
- *
56
- * @param s
57
- * @return 重複する文字があればtrue、無ければfalase
58
- */
59
- private static boolean hasDuplicateChars(String s)
60
- {
61
- if ( s == null || s.length() == 0 )
62
- return false;
63
-
64
- List<Character> list = new ArrayList<Character>();
65
-
66
- for ( int i=0; i < s.length(); ++ i ) {
67
- char c = s.charAt(i);
68
- if ( list.contains(c) )
69
- return true;
70
- else
71
- list.add(c);
72
- }
73
-
74
- return false;
75
- }
76
- }
77
-
78
- ```
79
-
80
- 順列の記号 nＰr を使うと、ご質問の場合の組み合わせ数は
81
-
82
- 5Ｐ5 = 5 * 4 * 3 * 2 * 1 ＝ 120
83
-
84
- となりますが、上記のプログラムを実行すると、行頭に通し番号を
85
- 表示しながら、0,1,2,3,4 を並べ替えて連結した、120通りの
86
- 文字列を表示します。
87
-
88
- とはいえ、5の5乗で、3125個の String s を生成するのは無駄が
89
- 多すぎで、あまりいいコードとはいえないので、あくまで最終手段の
90
- ご参考に留めていただければと思います。
91
-
92
- ---
93
-
94
- 追記します。
95
-
96
- さきほどの回答で示したコードが、あまりにも考えなさ杉と思ったので、
97
- 再帰でリストを作成する版を作成しました。
98
-
99
- 以下で、getPermutations(int n)　が再帰で解のリストを求めるメソッドです。
100
-
101
- ```lang-java
102
- package teratail;
103
-
104
- import java.util.ArrayList;
105
- import java.util.List;
106
-
107
- public class Q11179_2 {
108
-
109
14
  public static void main(String[] args)
110
15
  {
111
16
  // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
@@ -202,9 +107,9 @@
202
107
  List<List<Integer>> list = getPermutations(5);
203
108
  にしたり、
204
109
  List<List<Integer>> list = getPermutations(0);
205
- にしたりしてみましたが、一応問題なく動きます。
206
110
 
111
+ にしたりしてみましたが問題なく動くのを確認しました。
207
- ※ただし私の手元の環境では、
112
+ ただし私の手元の環境では、
208
113
  getPermutations(8);
209
114
  まではいけましたが
210
115
  getPermutations(9);
@@ -213,78 +118,5 @@
213
118
  Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
214
119
 
215
120
  となりました。
216
- 再帰で書いたものの実用的ではないかもしれません。
217
121
 
218
122
  ご参考まで。
219
- ---
220
-
221
- さらに追記します。
222
-
223
-
224
- 与題では、順列を構成する要素は { 0, 1, 2, 3, 4} の5個ですが、
225
- これが多い場合、たとえば、すべての半角英字（大文字）の順列を
226
- 考えると、構成要素は26個になります。
227
-
228
- これの順列の全リストを得たいとすると、以下のように
229
- テキストファイルを作成していく方法が考えられます。
230
-
231
-
232
- ・ファイル　AtoA.txt　は以下の行のみを含みます。
233
-
234
- A
235
-
236
- ・ファイル AtoB.txtは以下の2行を含みます。
237
-
238
- AB
239
- BA
240
-
241
- ・ファイル AtoC.txtは以下の6行を含みます。
242
-
243
- ABC
244
- ACB
245
- BAC
246
- BCA
247
- CAB
248
- CBA
249
-
250
- このような規則でファイルAto[A-Z].txtを作っていくこと
251
- にすると、欲しいのは
252
-
253
- AtoZ.txt
254
-
255
- です。
256
-
257
- ここで、アルファベットの列で最初からn番目の文字をα(n)と
258
- 書くことにします。つまり　α(1)=A, α(26)=Z　ですが、
259
- このとき、ファイル Atoα(n+1).txtは、ファイル Atoα(n).txt
260
- を元に作成することができます。
261
-
262
- それは以下のアルゴリズムによります。
263
-
264
- ファイル Atoα(n).txt の各行の文字列の、先頭と末尾、および
265
- すべての文字と文字との間に、新しいアルファベット α(n+1)を
266
- 挿入した文字列を作成し、それらをファイル Atoα(n+1).txt
267
- に出力します。
268
-
269
- たとえば、AtoB.txt　の行
270
-
271
- AB
272
-
273
- からは、AtoC.txtに書き込むべき行として
274
-
275
- CAB
276
- ACB
277
- ABC
278
-
279
- の3行が生成されます。
280
-
281
- このようにして、AtoA.txtは手入力で作成することにして
282
- 1回のプログラムの実行では
283
- ファイル Atoα(n-1).txt からAtoα(n).txt
284
- を作るだけのものにすれば、少なくとも再帰を使わないで
285
- （つまりヒープを消尽しないで）
286
- AtoZ.txtが得られるものと思います。
287
-
288
- ただし、要素がさらに多くなると、１つのファイルの行数が多くなりすぎるとか、
289
- 実行時間がかかる、といった問題が出てきますが、実用的な方法として
290
- 思いついたことは以上です。

7

テキスト追加

2015/06/13 06:13

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -281,10 +281,10 @@
281
281
  このようにして、AtoA.txtは手入力で作成することにして
282
282
  1回のプログラムの実行では
283
283
  ファイル Atoα(n-1).txt からAtoα(n).txt
284
- を作るだけのものにすれば、再帰を使わないで
284
+ を作るだけのものにすれば、少なくとも再帰を使わないで
285
285
  （つまりヒープを消尽しないで）
286
286
  AtoZ.txtが得られるものと思います。
287
287
 
288
-
288
+ ただし、要素がさらに多くなると、１つのファイルの行数が多くなりすぎるとか、
289
- それなりに手間がかかりますが、実用的な方法として
289
+ 実行時間がかかる、といった問題が出てきますが、実用的な方法として
290
290
  思いついたことは以上です。

6

テキスト追加

2015/06/12 10:07

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -216,4 +216,75 @@
216
216
  再帰で書いたものの実用的ではないかもしれません。
217
217
 
218
218
  ご参考まで。
219
+ ---
219
220
 
221
+ さらに追記します。
222
+
223
+
224
+ 与題では、順列を構成する要素は { 0, 1, 2, 3, 4} の5個ですが、
225
+ これが多い場合、たとえば、すべての半角英字（大文字）の順列を
226
+ 考えると、構成要素は26個になります。
227
+
228
+ これの順列の全リストを得たいとすると、以下のように
229
+ テキストファイルを作成していく方法が考えられます。
230
+
231
+
232
+ ・ファイル　AtoA.txt　は以下の行のみを含みます。
233
+
234
+ A
235
+
236
+ ・ファイル AtoB.txtは以下の2行を含みます。
237
+
238
+ AB
239
+ BA
240
+
241
+ ・ファイル AtoC.txtは以下の6行を含みます。
242
+
243
+ ABC
244
+ ACB
245
+ BAC
246
+ BCA
247
+ CAB
248
+ CBA
249
+
250
+ このような規則でファイルAto[A-Z].txtを作っていくこと
251
+ にすると、欲しいのは
252
+
253
+ AtoZ.txt
254
+
255
+ です。
256
+
257
+ ここで、アルファベットの列で最初からn番目の文字をα(n)と
258
+ 書くことにします。つまり　α(1)=A, α(26)=Z　ですが、
259
+ このとき、ファイル Atoα(n+1).txtは、ファイル Atoα(n).txt
260
+ を元に作成することができます。
261
+
262
+ それは以下のアルゴリズムによります。
263
+
264
+ ファイル Atoα(n).txt の各行の文字列の、先頭と末尾、および
265
+ すべての文字と文字との間に、新しいアルファベット α(n+1)を
266
+ 挿入した文字列を作成し、それらをファイル Atoα(n+1).txt
267
+ に出力します。
268
+
269
+ たとえば、AtoB.txt　の行
270
+
271
+ AB
272
+
273
+ からは、AtoC.txtに書き込むべき行として
274
+
275
+ CAB
276
+ ACB
277
+ ABC
278
+
279
+ の3行が生成されます。
280
+
281
+ このようにして、AtoA.txtは手入力で作成することにして
282
+ 1回のプログラムの実行では
283
+ ファイル Atoα(n-1).txt からAtoα(n).txt
284
+ を作るだけのものにすれば、再帰を使わないで
285
+ （つまりヒープを消尽しないで）
286
+ AtoZ.txtが得られるものと思います。
287
+
288
+
289
+ それなりに手間がかかりますが、実用的な方法として
290
+ 思いついたことは以上です。

5

テキスト修正

2015/06/12 09:51

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -204,5 +204,16 @@
204
204
  List<List<Integer>> list = getPermutations(0);
205
205
  にしたりしてみましたが、一応問題なく動きます。
206
206
 
207
+ ※ただし私の手元の環境では、
208
+ getPermutations(8);
209
+ まではいけましたが
210
+ getPermutations(9);
211
+ でヒープを使い果たして
212
+
213
+ Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
214
+
215
+ となりました。
216
+ 再帰で書いたものの実用的ではないかもしれません。
217
+
207
218
  ご参考まで。
208
219
 

4

テキスト修正

2015/06/12 08:32

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -92,7 +92,10 @@
92
92
  ---
93
93
 
94
94
  追記します。
95
+
96
+ さきほどの回答で示したコードが、あまりにも考えなさ杉と思ったので、
95
97
  再帰でリストを作成する版を作成しました。
98
+
96
99
  以下で、getPermutations(int n)　が再帰で解のリストを求めるメソッドです。
97
100
 
98
101
  ```lang-java

3

ソース修正

2015/06/12 08:05

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -154,9 +154,9 @@
154
154
  list.add(0);
155
155
  results.add(list);
156
156
  } else {
157
- List<List<Integer>> prevList = getPermutations(n-1);
157
+ List<List<Integer>> prevResults = getPermutations(n-1);
158
158
 
159
- for ( List<Integer> list : prevList) {
159
+ for ( List<Integer> list : prevResults ) {
160
160
  final int size = list.size();
161
161
  for ( int i=0; i <= size; ++ i ) {
162
162
  if ( i < size )

2

テキスト追加

2015/06/12 07:46

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -87,4 +87,119 @@
87
87
 
88
88
  とはいえ、5の5乗で、3125個の String s を生成するのは無駄が
89
89
  多すぎで、あまりいいコードとはいえないので、あくまで最終手段の
90
- ご参考に留めていただければと思います。
90
+ ご参考に留めていただければと思います。
91
+
92
+ ---
93
+
94
+ 追記します。
95
+ 再帰でリストを作成する版を作成しました。
96
+ 以下で、getPermutations(int n)　が再帰で解のリストを求めるメソッドです。
97
+
98
+ ```lang-java
99
+ package teratail;
100
+
101
+ import java.util.ArrayList;
102
+ import java.util.List;
103
+
104
+ public class Q11179_2 {
105
+
106
+ public static void main(String[] args)
107
+ {
108
+ // 0以上4以下の数字を並べ替えたリストのすべてのパターンを取得
109
+ List<List<Integer>> list = getPermutations(4);
110
+
111
+ // 結果の表示
112
+ final int size = list.size();
113
+
114
+ int counter = 0;
115
+ for ( int i = size-1; i >= 0; -- i ) {
116
+ counter ++;
117
+ System.out.println(counter + ":" + listString(list.get(i)));
118
+ }
119
+ }
120
+
121
+
122
+ /*
123
+ * 整数のリストを、[0,1,2]のような形式の文字列にして返す。
124
+ */
125
+ private static String listString(List<Integer> list)
126
+ {
127
+ StringBuilder sb = new StringBuilder();
128
+
129
+ sb.append("[");
130
+
131
+ final int size = list.size();
132
+ for ( int i=0; i < size; ++i ) {
133
+ sb.append((i > 0 ? ",":"") + list.get(i));
134
+ }
135
+ sb.append("]");
136
+
137
+ return sb.toString();
138
+ }
139
+
140
+ /*
141
+ * 0以上n以下の整数が1回ずつ出現するリストのすべてのパターンを返す。
142
+ *
143
+ * @param n
144
+ * @return
145
+ */
146
+ private static List<List<Integer>> getPermutations(int n)
147
+ {
148
+ if ( n < 0 ) return null;
149
+
150
+ List<List<Integer>> results = new ArrayList<List<Integer>>();
151
+
152
+ if ( n == 0) {
153
+ List<Integer> list = new ArrayList<Integer>();
154
+ list.add(0);
155
+ results.add(list);
156
+ } else {
157
+ List<List<Integer>> prevList = getPermutations(n-1);
158
+
159
+ for ( List<Integer> list : prevList) {
160
+ final int size = list.size();
161
+ for ( int i=0; i <= size; ++ i ) {
162
+ if ( i < size )
163
+ list.add(i, n);
164
+ else
165
+ list.add(n);
166
+ results.add(copy(list));
167
+ list.remove( new Integer(n) );
168
+ }
169
+ }
170
+ }
171
+
172
+ return results;
173
+ }
174
+
175
+ /*
176
+ * 指定された整数リストのコピーを作成
177
+ */
178
+ private static List<Integer> copy(List<Integer> src)
179
+ {
180
+ List<Integer> list = new ArrayList<Integer>();
181
+
182
+ final int size = src.size();
183
+ for ( int i=0; i < size; ++ i ) {
184
+ list.add(src.get(i));
185
+ }
186
+
187
+ return list;
188
+ }
189
+
190
+ }
191
+
192
+
193
+ ```
194
+ 上記のmainメソッドの中で
195
+
196
+ List<List<Integer>> list = getPermutations(4);
197
+
198
+ としているところを
199
+ List<List<Integer>> list = getPermutations(5);
200
+ にしたり、
201
+ List<List<Integer>> list = getPermutations(0);
202
+ にしたりしてみましたが、一応問題なく動きます。
203
+
204
+ ご参考まで。
205
+

1

テキスト修正

2015/06/12 07:45

投稿

jun68ykt
jun68ykt

スコア9058

answer CHANGED
@@ -85,5 +85,6 @@
85
85
  表示しながら、0,1,2,3,4 を並べ替えて連結した、120通りの
86
86
  文字列を表示します。
87
87
 
88
+ とはいえ、5の5乗で、3125個の String s を生成するのは無駄が
88
- とはいえ、やはりあまりいいコードとはいえないので、
89
+ 多すぎで、あまりいいコードとはいえないので、あくまで最終手段の
89
- あくまで、最終手段のご参考になればと思います。
90
+ ご参考に留めていただければと思います。