制約アルゴリズムを持つ2つの文字の可能な配列のアルゴリズム

私はすべてを見つけるためのアルゴリズムを書きたい2つの文字 "n"と "o"の組み合わせによって形成される次元kの可能な配列ですが、どの組み合わせでも2つの "n"が隣り合うことはありません。 例では、k = 4の場合：

いや

正午

ノノ

尾尾

オノン

大野

おお

私の試みは、配列[n、o、o、o、.... o]から、2レコードごとに「n」を持つ別の配列のリストを作成し、配列[n、o 、n、o、....、o]再帰的に

しかし、 "" n "の間に複数の" "o" "の区切りがある場合、[n、o、o、o、n、o、o、n、... o、o]のようなケースがありません。

ご協力ありがとうございました

回答：

これを試して：

public IEnumerable<IEnumerable<char>> Combinations(int length, char? current = null)
{
var output = Enumerable.Empty<IEnumerable<char>>();
if (length == 1)
{
if (current != "n")
{
output = output.Concat(new[] { new[] { "n" } });
}
output = output.Concat(new[] { new[] { "o" } });
}
else if (length > 1)
{
if (current != "n")
{
output = output.Concat(Combinations(length - 1, "n").Select(xs => new[] { "n" }.Concat(xs)));
}
output = output.Concat(Combinations(length - 1, "o").Select(xs => new[] { "o" }.Concat(xs)));
}
return output;
}

ために Combinations(4) 私は得る：

のの 正午 いや オノン おの 大野 おお おおおお