0

それぞれある周期で循環する0と1の数列があります。

例:
010101010101...(周期2)
001100110011...(周期4)
000111000111...(周期6)

ここで、縦列が全て1になる最初の列番号やその割合を求めたいです。
上の例では最初に4列目(次に12列目)で1が揃い、無限数列全体の1/6が揃っています。

最初の列番号を求める方法は今のところ、各数列で周期内の何番目の1を選ぶかの組み合わせを全て試し、それぞれの組み合わせに対して連立合同式を解いて最小の列数を求め、全体の最小値を更新していくバックトラック法しか思いつきません。
割合を求める方法は、全周期の最小公倍数の列数までに1が揃う列を1つずつ数える方法しか思いつきません。

・これは名前のついた問題ですか?
・この問題はNP困難ですか?数列の数が増えても速く計算する方法はありますか?
・0、1が続く区間や循環する周期の長さを有理数や無理数に拡張した場合はどう計算しますか?

2
  • 問題がどのように与えられるのかを明確化したほうが良いと思います。例示を見る限りでは周期2N=N個の0とN個の1から構成されるようにも読み取れます。
    – yohjp
    2022年2月14日 16:38
  • 最初の問題では周期Nは自然数で、0がa個続いた後に1がb個続きます。N=a+bです
    – nazratt
    2022年2月14日 23:16

1 件の回答 1

0

・この問題はNP困難ですか?

いいえ。多項式時間で解ける問題と思います。

Pythonによるアルゴリズム実装例です:https://wandbox.org/permlink/8R5tfdstFdRV4NTG

import math
from fractions import Fraction

def solve(q):
  period = math.lcm(*[e[0] + e[1] for e in q])
  acc = (1 << period) - 1
  for e in q:
    dist = sum([1 << m for m in range(0, period, e[0] + e[1])])    
    bits = ((1 << e[1]) - 1) * dist
    acc &= bits
    print('{}+{} {:0{}b}'.format(*e, bits, period))
  print('acc {:0{}b}'.format(acc, period))
  msb = 1 + period - acc.bit_length()
  ratio = Fraction(bin(acc).count('1'), period)  # acc.bit_count() since Python3.10
  return (msb, ratio)

# 問題を(1個の0, 1個の1), ... と定義
q = [(1,1), (2,2), (3,3)]
ans = solve(q)
print(ans)
# 答え=(4, Fraction(1, 6))
1
  • 全周期の最小公倍数の長さのビット列を生成して演算をしていると思われますが、周期が多くなると最小公倍数も指数関数的に増加するため多項式時間とはならないと思います。
    – nazratt
    2022年2月19日 3:12

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。