java scriptのバックトラック法を使った問題について

Question

java scriptについて質問です。nビットの01のパターンの文字列をすべて発生させることができる（文字列は辞書式順序で発生する）このプログラムは，発生させたものを配列に蓄えて返り値として返している．このプログラムを書き換えて，ここで発生させられる文字列のうち，1がm回以上連続するもののみを辞書式順序で配列にして返す関数a(n, m)を作りたいのですが、わからないので教えていただきたいです。
###発生している問題・エラーメッセージ
例えば2回以上連続する場合など10011などを区別する条件がわからない。
###使用言語　java script
###ソースコード
function binary(n)
{
var ans = []
function bin(k, s)
{
if (k >= n) ans.push(s);
else
{
bin(k + 1, s + "0")
bin(k + 1, s + "1")
}

        }     
    bin(0, " ") 
    
} 
var res = binary(2)

　puts(res)
試したこと
ここに問題に対して試したことを記載してください。
forなどを使い、特定の配列を取り出すなど様々なことを試したが、上手くいかなかった。

Answer 1

バックトラック法を使うのが条件ですか。

例えばnのうちk文字目まで生成した文字列Skがあるとしましょう。
Skにおいて右側から数えて連続して"1"が登場している数をpkとします。

1. pk >= m の場合、これ以降どのような文字列を生成しても条件を満たす。
2. n - k + pk >= m の場合、これ以降に生成する文字列に1が m 回連続して出現する可能性がある。
3. それ以外の場合、これ以降どのような文字列を生成しても条件を満たさない。

3.の条件に当てはまる場合は、このSkから生成された文字列は1つも前提条件を満たさないことが明らかなので、Skを元にした文字列をこれ以上生成する必要はありません。これがバックトラックです。

文字列を生成するたびに（つまり再帰のbinが発生するたびに）1が連続する数を数えるのは処理時間が嵩むので、bin関数の引数に変数 pk を加え、

1. "0"を連結する場合は pk = 0
2. "1"を連結する場合は pk + 1
3. 既に条件を満たしている場合は、どちらを連結する場合も pk = m

を次の再帰するbin関数に渡してあげれば良いでしょう。

n=100, m=85くらいでも1秒以内に収まります。

Comments

[zoran]

回答していただきありがとうございます。pkを生み出した後の条件式は分かったのですが、肝心のpkの生成方法がわかりません。お手数ですがよろしくお願いします。

[hope_mucci]

pkの生成方法も回答に書いてあります。
初期値（binを一番最初に実行する際の引数pkの値）は0です。

[zoran]

いえ、すいません自分が言いたいのは、どのように右側から1を数えるのかということです。言い方が悪かったです。

[hope_mucci]

右側から1の数を数えるだけだったら、素直に右側から文字列を走査していけばいいという回答にしかなりません。そういうことではないでしょう。言い方がもっと悪くなっています。
binは右側に文字列を連結していくわけなので、右に"1"を連結したらpkは1増え、"0"を連結したらpkは0になる、pkに関する操作はそれだけのことです。
最初から上記のような方法で数えていけば、途中でわざわざ連続する1を数える必要はないということです。
このような考え方はアルゴリズムを考える上では非常に重要です（数学で言う漸化式に近い）。

[zoran]

なるほどありがとございます！