回答編集履歴

11

fix answer

2022/11/18 07:33

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -28,6 +28,6 @@
28
28
  ```
29
29
  `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列が生成されました.適宜,適用したい条件`cond`を追加して実行することができます.
30
30
 
31
- ちなみに生成する条件で「0,1は3個**以下**」と言っていましたが,3個**未満**でないと結果の個数が一致しません.どちらが望んだ結果なのか不明でしたので,得られる配列の個数に合わせましたが,もし3個**以下**の条件が正しいなら,`if x.count(k) < v - 1:`を`if x.count(k) < v:`に変更してください.
31
+ ちなみに生成する条件で「0,2は3個**以下**」と言っていましたが,3個**未満**でないと結果の個数が一致しません.どちらが望んだ結果なのか不明でしたので,とりあえず得られる配列の個数に合わせましたが,もし3個**以下**の条件が正しいなら,`if x.count(k) < v - 1:`を`if x.count(k) < v:`に変更してください.
32
32
 
33
33
  can110さんの回答との相違点は,「グローバル変数を使いまくっているので行儀が悪い」「ファイル書き込みではなく`result`に答えを格納しまくるのでメモリ圧迫する」という点です.ファイル書き込みによるメモリ節約に関しては弊回答にも適用しやすいものかと思われます.

10

fix answer

2022/11/18 07:23

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -5,7 +5,7 @@
5
5
 
6
6
  cond = {
7
7
  0: 3, # 3個未満
8
- 1: 1e9, # 10^9以下(実質無制限)
8
+ 1: 1e9, # 10^9未満(実質無制限)
9
9
  2: 3, # 3個未満
10
10
  }
11
11
 
@@ -13,7 +13,8 @@
13
13
 
14
14
  def dfs(x):
15
15
  if len(x) == n:
16
- return result.append(x.copy())
16
+ result.append(x.copy())
17
+ return
17
18
 
18
19
  for k, v in cond.items():
19
20
  if x.count(k) < v - 1:

9

update answer

2022/11/18 07:19

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -27,4 +27,6 @@
27
27
  ```
28
28
  `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列が生成されました.適宜,適用したい条件`cond`を追加して実行することができます.
29
29
 
30
+ ちなみに生成する条件で「0,1は3個**以下**」と言っていましたが,3個**未満**でないと結果の個数が一致しません.どちらが望んだ結果なのか不明でしたので,得られる配列の個数に合わせましたが,もし3個**以下**の条件が正しいなら,`if x.count(k) < v - 1:`を`if x.count(k) < v:`に変更してください.
31
+
30
32
  can110さんの回答との相違点は,「グローバル変数を使いまくっているので行儀が悪い」「ファイル書き込みではなく`result`に答えを格納しまくるのでメモリ圧迫する」という点です.ファイル書き込みによるメモリ節約に関しては弊回答にも適用しやすいものかと思われます.

8

fix answer

2022/11/18 07:09

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -27,4 +27,4 @@
27
27
  ```
28
28
  `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列が生成されました.適宜,適用したい条件`cond`を追加して実行することができます.
29
29
 
30
- can110さんの回答の相違点は,「グローバル変数を使いまくっているので行儀が悪い」「`result`に答えを格納しまくるのでメモリ圧迫する」という点です.後者に関しては弊回答にも適用しやすいものかと思われます.
30
+ can110さんの回答の相違点は,「グローバル変数を使いまくっているので行儀が悪い」「ファイル書き込みではなく`result`に答えを格納しまくるのでメモリ圧迫する」という点です.ファイル書き込みよるメモリ節約に関しては弊回答にも適用しやすいものかと思われます.

7

append context

2022/11/18 07:08

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -26,3 +26,5 @@
26
26
  print(len(result))
27
27
  ```
28
28
  `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列が生成されました.適宜,適用したい条件`cond`を追加して実行することができます.
29
+
30
+ can110さんとの回答の相違点は,「グローバル変数を使いまくっているので行儀が悪い」「`result`に答えを格納しまくるのでメモリ圧迫する」という点です.後者に関しては弊回答にも適用しやすいものかと思われます.

6

fix context

2022/11/18 07:04

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -1,4 +1,4 @@
1
- 勝たんしか深さ優先探索な問題ですね.3分木を探索するイメージで,次のように書けば全列挙できます.
1
+ 勝たんしか深さ優先探索な問題ですね.`len(cond)`分木を探索するイメージで,次のように再帰を書けば余計な配列を生成せず全列挙できます.
2
2
 
3
3
  ```Python
4
4
  n = 10

5

fix answer

2022/11/18 07:01

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -1,4 +1,4 @@
1
- 勝たんしか深さ優先探索な問題ですね.次のように書くことで全列挙できます.
1
+ 勝たんしか深さ優先探索な問題ですね.3分木を探索するイメージで,次のように書けば全列挙できます.
2
2
 
3
3
  ```Python
4
4
  n = 10
@@ -25,4 +25,4 @@
25
25
  print(result)
26
26
  print(len(result))
27
27
  ```
28
- `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列が生成されました.
28
+ `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列が生成されました.適宜,適用したい条件`cond`を追加して実行することができます.

4

append answer

2022/11/18 06:58

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -25,4 +25,4 @@
25
25
  print(result)
26
26
  print(len(result))
27
27
  ```
28
- `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は実行時間長くて確認できていせん
28
+ `n = 10`のとき,同様に2181個観測され,`n = 30`で190591個,`n = 50`は1504401個の配列生成されした

3

fix answer

2022/11/18 06:55

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -4,9 +4,9 @@
4
4
  n = 10
5
5
 
6
6
  cond = {
7
- 0: 3, # 3個以下
7
+ 0: 3, # 3個未満
8
8
  1: 1e9, # 10^9以下(実質無制限)
9
- 2: 3, # 3個以下
9
+ 2: 3, # 3個未満
10
10
  }
11
11
 
12
12
  result = list()

2

fix answer

2022/11/18 06:53

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -16,7 +16,7 @@
16
16
  return result.append(x.copy())
17
17
 
18
18
  for k, v in cond.items():
19
- if x.count(k) < v:
19
+ if x.count(k) < v - 1:
20
20
  x.append(k)
21
21
  dfs(x)
22
22
  x.pop()
@@ -25,4 +25,4 @@
25
25
  print(result)
26
26
  print(len(result))
27
27
  ```
28
- `n = 10`でピックアップした`result`は2181個とでしたがこちらの結果では13341個観測されました.`n = 30`で15143571ですね.`n = 50`は実行時間がかかりそうなのやってませんが,おそらく実現不可能でしょう
28
+ `n = 10`のと同様に2181個観測され`n = 30`で190591個`n = 50`は実行時間が長くて確認ません.

1

fix answer

2022/11/18 06:42

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -25,4 +25,4 @@
25
25
  print(result)
26
26
  print(len(result))
27
27
  ```
28
- `n = 10`でピックアップした`result`は2181個とのことでしたが,こちらの結果では13341個観測されました.`n = 50`で15143571個ですね.
28
+ `n = 10`でピックアップした`result`は2181個とのことでしたが,こちらの結果では13341個観測されました.`n = 30`で15143571個ですね.`n = 50`は実行時間がかかりそうなのでやってませんが,おそらく実現不可能でしょう.