以下では「1からnまでの順列で偶数または奇数が高々k-1個連続するもの」の話に一般化しています
ひとまず順列そのものではなく偶奇のパターンを考えることにします。
数を前から順に配置していくことを考えます。ある時点で奇数(あるいは偶数)を配置してよいかどうかは、奇数及び偶数の残り個数と、それぞれ連続で何回取り出しているかのみに依存するので、次のような再帰関数ok(偶数の残り個数,奇数の残り個数,直前まで連続している並んでいる偶数の個数,直前まで連続して並んでいる奇数の個数,k)
で判定できます。
ただし以下では真偽値ではなく、遷移先にある(有効な)偶奇のパターンの合計を返すようにしています。
また高速化のためlru_cache
を使ってメモ化しています。
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)
この時、m=ok(元の順列に現れる偶数の個数,元の順列に現れる奇数の個数,0,0,k)
が偶奇のパターンのうち偶数および奇数が高々k-1個連続しているものの総数です。
よって
- 整数i∈[1,m]を一様に選ぶ
- 「i 番目」の偶奇のパターンを計算する
- 奇数のリストと偶数のリストをそれぞれシャッフルし、2 で計算したパターンに従って数を並べる
ということを行えば条件を満たす順列を等しい確率で得ることができます。
ここで 2.はok
で遷移先にあるパターンの数が得られることを利用して、次のget_nth
で実現できます。
# 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
gen(n,k)
で条件を満たす順列を1つ得られます。
実際に使ってみるとこんな感じです。
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]