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


タイトルにもあるとおり、  
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ですので、そちらの言語で教えていただくのがベストですが、難しい場合は、言葉で説明していただけると幸いです。




**以下では「１から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]

