トップアルゴリズムに関する質問 1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズム

編集履歴

回答編集履歴

Step2

2022/01/28 08:43

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -2,8 +2,9 @@
 **Step1:** 1以上100以下の奇数を Fisher-Yates shuffle しておきます．
 MATLABなら fy = randperm(100); のあと fyodd=fy(mod(fy,2)==1); など．
-python なら import random から fyodd=list(range(1,101,2)) をして
+また，python なら import random から
+fyodd=list(range(1,101,2)) をして random.shuffle(fyodd) など．
-random.shuffle(fyodd) など．random.shuffle() はfyoddの中身を直接書きかえてしまうのですね．
+random.shuffle() はfyoddの中身を直接書きかえてしまうのですね．
 **Step2:** 同様に，1以上100以下の偶数を Fisher-Yates shuffle しておきます．

Step2 度重なる修正

2022/01/28 08:42

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -2,8 +2,8 @@
 **Step1:** 1以上100以下の奇数を Fisher-Yates shuffle しておきます．
 MATLABなら fy = randperm(100); のあと fyodd=fy(mod(fy,2)==1); など．
-python なら import random から fyodd=list(range(1,101,2)) をして random.shuffle(fyodd) など．
+python なら import random から fyodd=list(range(1,101,2)) をして
-random.shuffle() はfyoddの中身を直接書きかえてしまうのですね．
+random.shuffle(fyodd) など．random.shuffle() はfyoddの中身を直接書きかえてしまうのですね．
 **Step2:** 同様に，1以上100以下の偶数を Fisher-Yates shuffle しておきます．

Step2

2022/01/28 08:41

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -1,8 +1,11 @@
 ### 題意をみたす列を全パターン出せそうな方法（途中，考察をダラダラと記述）
 **Step1:** 1以上100以下の奇数を Fisher-Yates shuffle しておきます．
-**Step2:** 1以上100以下の奇数を Fisher-Yates shuffle しておきます．
+MATLABなら fy = randperm(100); のあと fyodd=fy(mod(fy,2)==1); など．
-MATLABなら randperm()，python なら import random からの random.shuffle() を使うでしょうか．
+python なら import random から fyodd=list(range(1,101,2)) をして random.shuffle(fyodd) など．
+random.shuffle() はfyoddの中身を直接書きかえてしまうのですね．
+**Step2:** 同様に，1以上100以下の偶数を Fisher-Yates shuffle しておきます．
 次に，偶奇の切り替わり回数は最多で99回，最少で33回です．
 (切り替わりが最少となる例) 奇奇奇,偶偶偶, ... ,奇奇奇,偶偶偶,奇奇,偶偶（カンマが33個）

Step2の後を修正

2022/01/28 08:19

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -2,8 +2,7 @@
 **Step1:** 1以上100以下の奇数を Fisher-Yates shuffle しておきます．
 **Step2:** 1以上100以下の奇数を Fisher-Yates shuffle しておきます．
-MATLABなら randperm(100)，
-python なら import random からの random.shuffle(range(100)) でしょうか．
+MATLABなら randperm()，python なら import random からの random.shuffle() を使うでしょうか．
 次に，偶奇の切り替わり回数は最多で99回，最少で33回です．
 (切り替わりが最少となる例) 奇奇奇,偶偶偶, ... ,奇奇奇,偶偶偶,奇奇,偶偶（カンマが33個）

Step7,10の修正

2022/01/28 07:41

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -26,13 +26,13 @@
 **Step5:** 1以上49以下の数をmo個並べてできる列 {ro_1, ro_2, ... , ro_mo}を考えます．また，もしmoの値が0ならばStep8に移ります．
 **Step6:** 次に「奇,奇, ... ,奇」という（かたまりサイズ1の奇数50個をカンマで区切った）並びを考えます．
-**Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く（これにより，左から ro_i番目のかたまりのサイズが（旧ro_i番目のかたまりのサイズ）+（旧(ro_i+1)番目のかたまりのサイズ）となる）」
+**Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，Step6の時点で左から ro_i番目の位置にあったカンマを取り除いても，奇数が4つ以上連続しないならば，そのカンマを取り除く（これにより，取り除くカンマの左にあったかたまりのサイズが「取り除くカンマの両脇にあった2つのかたまりのサイズの和」となる）」
 同様に，偶数のかたまりの個数を減らしていきます．
 **Step8:** 1以上49以下の数をme個並べてできる列 {re_1, re_2, ... , re_me}を考えます．また，もしmeの値が0ならばStep11に移ります．
 **Step9:** 次に「偶,偶, ... ,偶」という（かたまりサイズ1の偶数50個をカンマで区切った）並びを考えます．
-**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが（旧re_i番目のかたまりのサイズ）+（旧(re_i+1)番目のかたまりのサイズ）となる）」
+**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，Step6の時点で左から re_i番目の位置にあったカンマを取り除いても，偶数が4つ以上連続しないならば，そのカンマを取り除く（これにより，取り除くカンマの左にあったかたまりのサイズが「取り除くカンマの両脇にあった2つのかたまりのサイズの和」となる）」
 以上の操作によって生成された最大サイズ3の偶奇のかたまりを並べていきます．

Step5,8を修正．先の修正が誤り．

2022/01/28 05:36

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -24,13 +24,13 @@
 奇数のかたまりの個数を減らしていきます．
 かたまりの個数を1つ減らすごとに，いずれか1つのかたまりのサイズが大きくなります（増えるサイズは後述）．
-**Step5:** 1以上33以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．また，もしmoの値が0ならばStep8に移ります．
+**Step5:** 1以上49以下の数をmo個並べてできる列 {ro_1, ro_2, ... , ro_mo}を考えます．また，もしmoの値が0ならばStep8に移ります．
 **Step6:** 次に「奇,奇, ... ,奇」という（かたまりサイズ1の奇数50個をカンマで区切った）並びを考えます．
 **Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く（これにより，左から ro_i番目のかたまりのサイズが（旧ro_i番目のかたまりのサイズ）+（旧(ro_i+1)番目のかたまりのサイズ）となる）」
 同様に，偶数のかたまりの個数を減らしていきます．
-**Step8:** 1以上33以下の偶数me個からなる列 {re_1, re_2, ... , re_me}を考えます．また，もしmeの値が0ならばStep11に移ります．
+**Step8:** 1以上49以下の数をme個並べてできる列 {re_1, re_2, ... , re_me}を考えます．また，もしmeの値が0ならばStep11に移ります．
 **Step9:** 次に「偶,偶, ... ,偶」という（かたまりサイズ1の偶数50個をカンマで区切った）並びを考えます．
 **Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが（旧re_i番目のかたまりのサイズ）+（旧(re_i+1)番目のかたまりのサイズ）となる）」

Step5,8の加筆，Step11の修正．

2022/01/28 05:30

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -24,19 +24,22 @@
 奇数のかたまりの個数を減らしていきます．
 かたまりの個数を1つ減らすごとに，いずれか1つのかたまりのサイズが大きくなります（増えるサイズは後述）．
-**Step5:** 1以上33以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．
+**Step5:** 1以上33以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．また，もしmoの値が0ならばStep8に移ります．
 **Step6:** 次に「奇,奇, ... ,奇」という（かたまりサイズ1の奇数50個をカンマで区切った）並びを考えます．
 **Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く（これにより，左から ro_i番目のかたまりのサイズが（旧ro_i番目のかたまりのサイズ）+（旧(ro_i+1)番目のかたまりのサイズ）となる）」
 同様に，偶数のかたまりの個数を減らしていきます．
-**Step8:** 1以上33以下の偶数me個からなる列 {re_1, re_2, ... , re_me}を考えます．
+**Step8:** 1以上33以下の偶数me個からなる列 {re_1, re_2, ... , re_me}を考えます．また，もしmeの値が0ならばStep11に移ります．
 **Step9:** 次に「偶,偶, ... ,偶」という（かたまりサイズ1の偶数50個をカンマで区切った）並びを考えます．
-**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが（旧ro_i番目のかたまりのサイズ）+（旧(ro_i+1)番目のかたまりのサイズ）となる）」
+**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが（旧re_i番目のかたまりのサイズ）+（旧(re_i+1)番目のかたまりのサイズ）となる）」
 以上の操作によって生成された最大サイズ3の偶奇のかたまりを並べていきます．
-**Step11:** もし mo-me=1 ならば，奇数のかたまりから開始して奇数のかたまりで終わる．また，もし me-mo=1 ならば，偶数のかたまりから開始して偶数のかたまりで終わる．いずれにも該当しなければ，me=moなので，{奇数/偶数}のかたまりから開始すると{偶数/奇数}のかたまりで終わる．
+**Step11:** もし mo-me=1 ならば，奇数のかたまりから開始して，以下{奇数/偶数}のかたまりを交互に置いていく．また，もし me-mo=1 ならば，偶数のかたまりから開始して{奇数/偶数}のかたまりを交互に置いていく．いずれにも該当しなければ，me=moなので，{奇数/偶数}どちらのかたまりから開始しても良いが，以下{奇数/偶数}のかたまりを交互に置いていく．
+その結果，mo-me=1 の場合が奇数のかたまりで終わり，me-mo=1 の場合は偶数のかたまりで終わります．
+また，me=mo で奇数のかたまりから開始した場合は偶数で，偶数のかたまりから開始した場合は奇数で，それぞれ終わります．
 題意をみたす列は，必ずこの手法で表現し得るのではないかと思っています．
 ただし，出方が一様かどうかの検証はしていません．

直しきれていなかった誤植を直します

2022/01/28 04:25

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -22,7 +22,7 @@
 **Step4:** mが偶数の場合，mo=me=m/2とします．また，mが奇数の場合，moとmeのうち片方を(m+1)/2，もう片方を(m-1)/2とします．
 奇数のかたまりの個数を減らしていきます．
-かたまりの個数を1つ減らすごとに，いずれか1つのかたまりのサイズが1大きくなります．
+かたまりの個数を1つ減らすごとに，いずれか1つのかたまりのサイズが大きくなります（増えるサイズは後述）．
 **Step5:** 1以上33以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．
 **Step6:** 次に「奇,奇, ... ,奇」という（かたまりサイズ1の奇数50個をカンマで区切った）並びを考えます．

加筆した箇所に誤りがあり，さらに訂正します

2022/01/28 04:21

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -26,13 +26,13 @@
 **Step5:** 1以上33以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．
 **Step6:** 次に「奇,奇, ... ,奇」という（かたまりサイズ1の奇数50個をカンマで区切った）並びを考えます．
-**Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く（これにより，左から ro_i番目のかたまりのサイズが1大きくなる）」
+**Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く（これにより，左から ro_i番目のかたまりのサイズが（旧ro_i番目のかたまりのサイズ）+（旧(ro_i+1)番目のかたまりのサイズ）となる）」
 同様に，偶数のかたまりの個数を減らしていきます．
 **Step8:** 1以上33以下の偶数me個からなる列 {re_1, re_2, ... , re_me}を考えます．
 **Step9:** 次に「偶,偶, ... ,偶」という（かたまりサイズ1の偶数50個をカンマで区切った）並びを考えます．
-**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが1大きくなる）」
+**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが（旧ro_i番目のかたまりのサイズ）+（旧(ro_i+1)番目のかたまりのサイズ）となる）」
 以上の操作によって生成された最大サイズ3の偶奇のかたまりを並べていきます．

誤植があり修正しました．

2022/01/28 04:18

投稿

obeSolitary

スコア106

test CHANGED Viewed

@@ -24,15 +24,15 @@
 奇数のかたまりの個数を減らしていきます．
 かたまりの個数を1つ減らすごとに，いずれか1つのかたまりのサイズが1大きくなります．
-**Step5:** 1以上49以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．
+**Step5:** 1以上33以下の奇数mo個からなる列 {ro_1, ro_2, ... , ro_mo}を考えます．
 **Step6:** 次に「奇,奇, ... ,奇」という（かたまりサイズ1の奇数50個をカンマで区切った）並びを考えます．
-**Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く」
+**Step7:** i = 1, 2, ... ,mo に対して以下を行います：「もし，左から ro_i番目のカンマを取り除いても奇数が4つ以上連続しないならば左から ro_i番目のカンマを取り除く（これにより，左から ro_i番目のかたまりのサイズが1大きくなる）」
 同様に，偶数のかたまりの個数を減らしていきます．
-**Step8:** 1以上49以下の偶数me個からなる列 {re_1, re_2, ... , re_me}を考えます．
+**Step8:** 1以上33以下の偶数me個からなる列 {re_1, re_2, ... , re_me}を考えます．
 **Step9:** 次に「偶,偶, ... ,偶」という（かたまりサイズ1の偶数50個をカンマで区切った）並びを考えます．
-**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く」
+**Step10:** i = 1, 2, ... ,me に対して以下を行います：「もし，左から re_i番目のカンマを取り除いても偶数が4つ以上連続しないならば左から re_i番目のカンマを取り除く（これにより，左から re_i番目のかたまりのサイズが1大きくなる）」
 以上の操作によって生成された最大サイズ3の偶奇のかたまりを並べていきます．