中括弧ですべての可能性をどのように生成できますか？
N値は私たちに与えられており、私たちはすべての可能性を生み出さなければなりません。
例：
1）N == 1の場合、1つの可能性（）のみ。
2）N == 2の場合、可能性は（（））、（）（）です。
3）N == 3の場合、可能性は（（（）））、（（））（）、（）（）（）、（）（（））..。
注：左中括弧と右中括弧は一致している必要があります。つまり）（N==1の場合は無効です
再発アプローチを使用してこの問題を解決できますか？
2416 次
5 に答える
4
与えられた a に対して、N常に開き中括弧から始める必要があります。ここで、対応する右中括弧がどこにあるかを考えてみましょう。のように途中でも、のように最後()()でもかまいません。(())N=2
今考えてみましょうN=3：
それは最後にあることができます:(()())と((())).
または、中間:()(())および()()()位置 2 にある場所。次に、位置 4: にある場合もあります(())()。
これで、閉じ括弧が最後にある場合と真ん中にある場合は同じであることに気付くことで、2 つのケースを基本的に組み合わせることができますが、N=0 のすべての可能性が最後に追加されます。
nこれを解決するために、開始ブレースと終了ブレースの間のすべての可能性を解決することができます。同様mに、終了ブレースの後についてもすべての可能性を解決できます。(注m+n+1 = N) 次に、考えられるすべての組み合わせを組み合わせて、可能性のリストに追加し、エンド ブレースの次の可能な場所に進むことができます。
これらのタイプの問題で犯しやすい間違いは、すべての可能性を見つけてiそれらをN-i組み合わせることです.N=3()()()
この問題を解決する Python 2.x コードを次に示します。
memoise = {}
memoise[0] = [""]
memoise[1] = ["()"]
def solve(N, doprint=True):
if N in memoise:
return memoise[N]
memoise[N] = []
for i in xrange(1,N+1):
between = solve(i-1, False)
after = solve(N-i, False)
for b in between:
for a in after:
memoise[N].append("("+b+")"+a)
if doprint:
for res in memoise[N]:
print res
return memoise[N]
于 2010-11-30T13:34:31.483 に答える
4
ウィキペディアから -
Dyck ワードは、n 個の X と n 個の Y から構成される文字列であり、文字列の最初のセグメントに X よりも多くの Y が含まれることはありません (Dyck 言語も参照)。たとえば、長さ 6 の Dyck 語は次のとおりです。
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
シンボル X を開き括弧として再解釈し、Y を閉じ括弧として再解釈して、Cn は、正しく一致する n ペアの括弧を含む式の数をカウントします。
((())) ()(()) ()()() (())() (()())
http://www.acta.sapientia.ro/acta-info/C1-1/info1-9.pdfも参照してください。
概要。すべての Dyck 単語を生成する新しいアルゴリズムが提示され、Dyck 単語のランク付けとランク解除に使用されます。カタロニア語の数字に関連するオブジェクトをエンコードする際に Dyck 語を使用することの重要性を強調します。ランキング アルゴリズムで使用される数式の結果として、n 番目のカタロニア語数の再帰的な数式を取得できます。
于 2010-11-30T13:34:46.887 に答える
2
以下は、本質的に JPvdMerwe のコードのコンパクト バージョンであるコードです。ただし、ソリューションを出力するのではなく、ソリューションのリストを返します。このコードは、Python 2 と Python 3 の両方で機能します。
from itertools import product
def solve(num, cache={0: ['']}):
if num not in cache:
cache[num] = ['(%s)%s' % t for i in range(1, num + 1)
for t in product(solve(i - 1), solve(num - i))]
return cache[num]
# Test
for num in range(1, 5):
print(num)
for s in solve(num):
print(s)
出力
1
()
2
()()
(())
3
()()()
()(())
(())()
(()())
((()))
4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
((()))()
(()()())
(()(()))
((())())
((()()))
(((())))
Ed Guiness によってリンクされた記事で提供されている疑似コードから派生した、さらにいくつかの関数があります: Dyck words の生成とランキング。この記事では 1 から始まるインデックスを使用していますが、Python の 0 から始まるインデックスに準拠するように変換しました。
これらの関数は、solve上記の関数よりも低速ですが、それでも役立つ可能性があります。pos_dyck_words純粋に反復的であるという利点があります。unrank反復的ですが、再帰ヘルパー関数を呼び出しますf。OTOHfはキャッシュを使用するため、可能な限り遅くはなく、整数のキャッシュのみであり、RAM の使用量は の文字列キャッシュよりも少なくなりますsolve。の主な利点はunrank、特定のサイズのすべてのソリューションを生成する必要がなく、インデックス番号から個々のソリューションを返すことができることです。
このコードは Python 3 専用です。Python 2 で使用できるように変換するのは簡単ですlru_cache。キャッシングが必要です。そうしないfと、Dyck の語長が最小の場合を除いて、耐えられないほど遅くなります。
from itertools import product
from functools import lru_cache
# Generate all Dyck words of length 2*num, recursively
# fastest, but not lexicographically ordered
def solve(num, cache = {0: ['']}):
if num not in cache:
cache[num] = ['0%s1%s' % t for i in range(1, num + 1)
for t in product(solve(i - 1), solve(num - i))]
return cache[num]
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# A helper function for `unrank`
# f(i, j) gives the number of paths between (0,0) and (i, j) not crossing
# the diagonal x == y of the grid. Paths consist of horizontal and vertical
# segments only, no diagonals are permitted
@lru_cache(None)
def f(i, j):
if j == 0:
return 1
if j == 1:
return i
#if i < j:
#return 0
if i == j:
return f(i, i - 1)
# 1 < j < i <= n
return f(i - 1, j) + f(i, j - 1)
# Determine the position array of a Dyck word from its rank number,
# The position array gives the indices of the 1s in the word;
# the rank number is the word's index in the lexicographic sequence
# of all Dyck words of length 2n
# Very slow
def unrank(nr, n):
b = [-1]
for i in range(n):
b.append(1 + max(b[-1], 2 * i))
ni = n - i - 1
for j in range(n + i - b[-1], 0, -1):
delta = f(ni, j)
if nr < delta or b[-1] >= n + i:
break
nr -= delta
b[-1] += 1
return b[1:]
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# Generate all Dyck word position arrays for words of length 2*n, iteratively
def pos_dyck_words(n):
b = list(range(1, 2 * n, 2))
while True:
yield b
for i in range(n - 2, -1, -1):
if b[i] < n + i:
b[i] += 1
for j in range(i + 1, n - 1):
b[j] = 1 + max(b[j - 1], 2 * j)
break
else:
break
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# Convert a position array to a Dyck word
def pos_to_word(b, n, chars='01'):
c0, c1 = chars
word = [c0] * (2 * n)
for i in b:
word[i] = c1
return ''.join(word)
# Some tests
num = 4
print('num: {}, Catalan number: {}'.format(num, f(num, num)))
words = list(solve(num))
words.sort(reverse=True)
print(len(words))
for i, u in enumerate(pos_dyck_words(num)):
v = unrank(i, num)
w = words[i]
ok = u == v and pos_to_word(u, num) == w
print('{:2} {} {} {} {}'.format(i, u, v, w, ok))
print()
num = 10
print('num: {}, Catalan number: {}'.format(num, f(num, num)))
for i, u in enumerate(pos_dyck_words(num)):
v = unrank(i, num)
assert u == v, (i, u, v)
print('ok')
出力
num: 4, Catalan number: 14
14
0 [1, 3, 5, 7] [1, 3, 5, 7] 01010101 True
1 [1, 3, 6, 7] [1, 3, 6, 7] 01010011 True
2 [1, 4, 5, 7] [1, 4, 5, 7] 01001101 True
3 [1, 4, 6, 7] [1, 4, 6, 7] 01001011 True
4 [1, 5, 6, 7] [1, 5, 6, 7] 01000111 True
5 [2, 3, 5, 7] [2, 3, 5, 7] 00110101 True
6 [2, 3, 6, 7] [2, 3, 6, 7] 00110011 True
7 [2, 4, 5, 7] [2, 4, 5, 7] 00101101 True
8 [2, 4, 6, 7] [2, 4, 6, 7] 00101011 True
9 [2, 5, 6, 7] [2, 5, 6, 7] 00100111 True
10 [3, 4, 5, 7] [3, 4, 5, 7] 00011101 True
11 [3, 4, 6, 7] [3, 4, 6, 7] 00011011 True
12 [3, 5, 6, 7] [3, 5, 6, 7] 00010111 True
13 [4, 5, 6, 7] [4, 5, 6, 7] 00001111 True
num: 10, Catalan number: 16796
ok
于 2016-12-24T06:37:06.153 に答える
1
再帰的な解決策:
import java.util.Scanner;
public class Parentheses
{
static void ParCheck(int left,int right,String str)
{
if (left == 0 && right == 0)
{
System.out.println(str);
}
if (left > 0)
{
ParCheck(left-1, right+1 , str + "(");
}
if (right > 0)
{
ParCheck(left, right-1, str + ")");
}
}
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
System.out.println("Enter the number");
int num=input.nextInt();
String str="";
ParCheck(num,0,str);
}
}
于 2013-08-06T04:43:03.660 に答える