

タイトルにもあるとおり、  
1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズムを教えていただきたいです。  
例えば  
x = [99,1,4,5,2,66,45...]  
length(x)  
→100  
のようなものを作成したいです。  
条件にもあるとおり、よくないパターンは  
１, 偶数が4回以上続いている(奇数も同様)  
x = [77,2,4,3,66,88,42,72]  
2, 同じ数値がある(下の例では99)  
x = [99,1,4,5,2,66,99...]

同じ数値を使わずに1から100までの数値を使ってランダムな配列を作成することは、組み込み関数(MATLAB)を使ってできますが、良くないパターン1の条件を満たせません。  
自分がわかる言語はpythonとmatlabですので、そちらの言語で教えていただくのがベストですが、難しい場合は、言葉で説明していただけると幸いです。


CC BY-SA 4.0
2022-01-17T00:38:55.603
85746
2022-01-21T03:49:54.233
50762
question
アルゴリズム
1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズム


〇→奇数  
×→偶数  
としたら

【〇〇】「××」【〇】「×××」【〇〇】「××」・・・  
と続きます。

【奇数の組】と「偶数の組」と呼びます  
この組数が常に同値もしくは差を１にする必要があります。  
それ以外ですと４つ連続以上になってしまいます。

同値の場合は奇数もしくは偶数どちらが先でもOK  
【〇〇】「××」【〇】「×××」【〇〇】「××」・・・「××」  
「××」【〇】「×××」【〇〇】「××」【〇〇】・・・【〇〇】

差が１の場合は多いほうが先になる  
奇数が１つ多い場合  
【〇〇】「××」【〇】「×××」【〇〇】「××」・・・【〇〇】  
偶数が１つ多い場合  
「××」【〇】「×××」【〇〇】「××」【〇〇】・・・「××」

なのでまずやらなきゃいけないことはいくつ組を作るのかを決めます。  
1~100の数字を３個以下１個以上の組み合わせなので  
最小組数は50/3 = 16あまり2 17組  
最大組数は50/1 = 50 50組

まず組数A（17~50の数字）をランダムに決めます。  
またその対となる組数Bを『組数Aの-1』 『組数Aと同値』 『組数Aの+1』
からランダムに決めます。ただし組数Bが17~50の範囲内になるように決めてください。  
その後組数Aと組数Bをどちらを偶数かどちらを奇数にするかランダムで決めます。

便宜上決まった状態を以下のようになると思います  
【】【】【】【】【】【】【】【】・・・A組  
「」「」「」「」「」「」「」「」・・・B(AorA+1orA-1)組  
空の箱を用意しているイメージです。

次に組数ABと奇数偶数が決まればその組に数を割り当てますが、必ず一個以上にする必要があるのでまずは全部の箱に奇数偶数の組ごとにでランダムに数字を一つ割り振りましょう。  
その後は４つ以上にならないように余った数字をランダムに割り振ればいいと思います。

次に並べる作業ですが  
組数が同値の場合は奇数偶数はランダムで決めているので、Aから並べてOKでしょう。  
組数に差がある場合は組数の多いほうから並べてください。

値の割り振りは言語によってはなんかサポートできる関数だったり計算式があるかもしれないですが、愚直に行っても別に速度に違いはなさそうな気もしますし、今回は速度やパフォーマンスは気にしなくてよさそうなのであまり考えていないです。


CC BY-SA 4.0
2022-01-17T01:44:50.377
85747
2022-01-17T04:08:05.223
2022-01-17T04:08:05.223
22665
22665
85746
answer


**以下では「１からnまでの順列で偶数または奇数が高々k-1個連続するもの」の話に一般化しています**

ひとまず順列そのものではなく偶奇のパターンを考えることにします。

数を前から順に配置していくことを考えます。ある時点で奇数（あるいは偶数）を配置してよいかどうかは、奇数及び偶数の残り個数と、それぞれ連続で何回取り出しているかのみに依存するので、次のような再帰関数`ok(偶数の残り個数,奇数の残り個数,直前まで連続している並んでいる偶数の個数,直前まで連続して並んでいる奇数の個数,k)`で判定できます。

ただし以下では真偽値ではなく、 **遷移先にある（有効な）偶奇のパターンの合計** を返すようにしています。  
また高速化のため`lru_cache`を使ってメモ化しています。

[code]

    from functools import lru_cache
    from itertools import permutations, islice, cycle
    import random
    
    @lru_cache(maxsize=None)
    def ok(x, y, xz, yz, k):
        # 残数が負,あるいは連続でk個以上並べるのはダメ
        if x < 0 or y < 0 or xz >= k or yz >= k:
            return 0
        # 全部使い切ったらok
        elif x == 0 and y == 0:
            return 1
        # それ以外は奇数偶数のいずれかを選んで有効な状態へ遷移できるかチェック
        else:
            return ok(x - 1, y, xz + 1, 0, k) + ok(x, y - 1, 0, yz + 1, k)
    
[/code]

この時、`m=ok(元の順列に現れる偶数の個数,元の順列に現れる奇数の個数,0,0,k)`
が偶奇のパターンのうち偶数および奇数が高々k-1個連続しているものの総数です。

よって

  1. 整数i∈[1,m]を一様に選ぶ
  2. 「i 番目」の偶奇のパターンを計算する
  3. 奇数のリストと偶数のリストをそれぞれシャッフルし、2 で計算したパターンに従って数を並べる

ということを行えば条件を満たす順列を等しい確率で得ることができます。

ここで 2.は`ok`で遷移先にあるパターンの数が得られることを利用して、次の`get_nth`で実現できます。

[code]

    # i番目のパターンを選ぶ関数
    # curに偶奇のパターンが格納される
    def get_nth(x, y, xz, yz, k, i, cur):
        if x == 0 and y == 0:
            assert(i == 1)
            return cur
        c = ok(x-1, y, xz+1, 0, k)
    
        # 現在位置が偶数であるようなパターンはc個
        # なのでi <= cならここは偶数を選んで先に進む
        if i <= c:
            cur.append(0)
            return get_nth(x-1, y, xz+1, 0, k, i, cur)
    
        # そうでなければ奇数を選んで先に進む（ただし偶数にしたときのパターン数cを引く必要がある)
        else:
            cur.append(1)
            return get_nth(x, y-1, 0, yz+1, k, i-c, cur)
    
    def gen(n, k):
        m = ok(n//2, (n+1)//2, 0, 0, k)
    
        # i ∈ [1,m]を一様に選ぶ
        i = random.randint(1, m)
    
        # i番目のパターンを計算する
        pat = get_nth(n//2, (n+1)//2, 0, 0, k, i, [])
    
        # 偶数列、奇数列をそれぞれシャッフル
        numbers = [[2*i+2 for i in range(n//2)], [2*i+1 for i in range((n+1)//2)]]
        for i in range(2):
            random.shuffle(numbers[i])
    
        # パターンに従って数を並べる
        l = []
        for b in pat:
            l.append(numbers[b].pop())
        return l
    
    
    
[/code]

`gen(n,k)`で条件を満たす順列を1つ得られます。  
実際に使ってみるとこんな感じです。

[code]

    In [10]: print(gen(15,3))
    [15, 1, 2, 12, 11, 8, 13, 3, 6, 7, 4, 10, 9, 14, 5]
    
    In [11]: print(gen(15,3))
    [9, 10, 13, 6, 7, 14, 5, 8, 4, 15, 1, 2, 11, 12, 3]
    
    In [12]: print(gen(100,4))
    [22, 68, 71, 28, 12, 19, 14, 53, 85, 6, 7, 88, 62, 75, 65, 32, 64, 59, 77, 100, 17, 1, 95, 48, 73, 60, 2, 91, 81, 10, 86, 83, 42, 90, 76, 99, 13, 4, 92, 34, 11, 35, 25, 52, 94, 63, 39, 31, 72, 23, 3, 93, 26, 40, 79, 47, 51, 8, 27, 89, 37, 98, 50, 70, 87, 38, 66, 5, 15, 30, 74, 57, 67, 16, 46, 29, 9, 96, 56, 84, 69, 20, 36, 49, 82, 44, 41, 43, 80, 58, 18, 55, 24, 33, 61, 78, 97, 54, 45, 21]
    
[/code]


CC BY-SA 4.0
2022-01-20T14:10:25.983
85821
2022-01-21T03:49:54.233
2022-01-21T03:49:54.233
13199
13199
85746
answer