F#:

ОБНОВЛЕНИЕ: этот ответ является неправильным. Мой N=4 промахи, например", (()) (())". (Вы видите почему?) Я отправлю корректное (и более эффективный) алгоритм вскоре.

(Позор всему Вы-избиратели, для того, чтобы не поймать меня!:))

Неэффективный, но короткий и простой. (Обратите внимание, что это только печатает 'энную' строку; звоните в цикл от 1.. n, чтобы попросить у вывода вопросом.)

#light
let rec brackets n =
    if n = 1 then
        ["()"]
    else
        [for s in brackets (n-1) do
            yield "()" ^ s
            yield "(" ^ s ^ ")"
            yield s ^ "()"]

Пример:

Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

def @memo brackets ( n )
    => [] if n == 0 else around( n ) ++ pre( n ) ++ post( n ) ++ [ "()" * n) ]

def @memo pre ( n )
    => map ( ( s ) => "()" ++ s, pre ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []

def @memo post ( n )
    => map ( ( s ) => s ++ "()", post ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []

def @memo around ( n )
    => map ( ( s ) => "(" ++ s ++ ")", brackets( n - 1 ) )

( kin , что-то вроде линейного питона на основе актерской модели с чертами. не обошлось без реализации @memo, но вышеописанное работает без этой оптимизации)

Common Lisp:

Это не печатает их, но создает список списков из всех возможных структур. Мой метод немного отличается от других. Он реструктурирует решения для скобок (n - 1) так, что они становятся скобками (n) . Мое решение не является хвостовым рекурсивным, но оно может быть сделано с небольшой работой.

Код

(defun brackets (n)
  (if (= 1 n)
      '((()))
      (loop for el in (brackets (1- n))
            when (cdr el)
            collect (cons (list (car el)) (cdr el))
            collect (list el)
            collect (cons '() el))))

Вот решение в C++. Основная идея, что я использую, состоит в том, что я беру вывод от предыдущего я (где я - количество пар скобки), и подайте это, как введено к следующему я. Затем для каждой строки во входе мы помещаем пару скобки в каждое местоположение в строке. Новые строки добавляются к набору для устранения дубликатов.

#include <iostream>
#include <set>
using namespace std;
void brackets( int n );
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set );

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    brackets(n);
    return 0;
}

void brackets( int n ) {
    set<string>* set1 = new set<string>;
    set<string>* set2;

    for( int i = 1; i <= n; i++ ) {
        set2 = new set<string>;
        brackets_aux( i, *set1, *set2 );
        delete set1;
        set1 = set2;
    }
}

void brackets_aux( int x, const set<string>& input_set, set<string>& output_set ) {
    // Build set of bracket strings to print
    if( x == 1 ) {
        output_set.insert( "()" );
    }
    else {
        // For each input string, generate the output strings when inserting a bracket pair
        for( set<string>::iterator s = input_set.begin(); s != input_set.end(); s++ ) {
            // For each location in the string, insert bracket pair before location if valid
            for( unsigned int i = 0; i < s->size(); i++ ) {
                string s2 = *s;
                s2.insert( i, "()" );
                output_set.insert( s2 );
            }
            output_set.insert( *s + "()" );
        }
    }

    // Print them
    for( set<string>::iterator i = output_set.begin(); i != output_set.end(); i++ ) {
        cout << *i << "  ";
    }
    cout << endl;
}

Выберите проект установки, «Просмотр»> «Редакторы»> «Интерфейс пользователя», выберите диалоговые окна «Адрес установки» и удалите их. .

РЕДАКТИРОВАТЬ:

Как указывает Шей, пользователи могут переопределить расположение установки по умолчанию из командной строки. Чтобы переопределить это, вы должны установить свойство TARGETDIR в вашей InstallExecuteSequence. К сожалению, вы не можете изменить эту последовательность в Visual Studio, вам нужно использовать Orca:

1. Создайте свой проект установки.
2. Откройте файл MSI из Orca.
3. Создайте новое пользовательское действие типа 51 (установить свойство). с источником "TARGETDIR" (без кавычек), целью вашей целевой папки и уникальным именем для действия (соглашение заключается в использовании GUID с начальным подчеркиванием).
4. Создайте новую строку в InstallExecuteSequence с вашим уникальным именем для Действие "

    let total_bracket n =
    let rec aux acc = function
   | 0, 0 -> print_string (acc ^ "\ n")
   | 0, n -> aux (acc ^ ")") (0, n-1)
   | n, 0 -> aux (acc ^ "(") (n-1, 1)
   | n, c ->
    aux (acc ^ "(") (n-1, c + 1);
    aux (acc ^ ")") (n, c-1)
    в
    aux "" (n, 0)
   

Чертовски - все избили меня к нему, но у меня есть хороший рабочий пример :)

http://www.fiveminuteargument.com/so-727707

Ключ определяет правила, которые на самом деле довольно просты:

• Создайте строковый символ символом
• В данной точке в строке
  • если скобки в строке до сих пор балансируются (включает пустую ул.), добавьте открытую скобку и рекурсивно вызовите
  • если все открытые скобки использовались, добавьте закрывающую квадратную скобку и рекурсивно вызовите
  • иначе рекурсивно вызовите дважды, однажды для каждого типа скобки
• Остановитесь, когда Вы доберетесь в конец :-)

F#:

Вот решение, которому, в отличие от моего предыдущего решения, я верю, может быть корректным. Кроме того, это более эффективно.

#light

let brackets2 n =
    let result = new System.Collections.Generic.List<_>()
    let a = Array.create (n*2) '_'
    let rec helper l r diff i =
        if l=0 && r=0 then
            result.Add(new string(a))
        else
            if l > 0 then
                a.[i] <- '('
                helper (l-1) r (diff+1) (i+1)
            if diff > 0 then
                a.[i] <- ')'
                helper l (r-1) (diff-1) (i+1)
    helper n n 0 0
    result

Пример:

(brackets2 4) |> Seq.iter (printfn "%s")

(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

Вот другое решение F#, способствуя элегантности по эффективности, хотя memoization, вероятно, привел бы к относительно хорошо работающему варианту.

let rec parens = function
| 0 -> [""]
| n -> [for k in 0 .. n-1 do
        for p1 in parens k do
        for p2 in parens (n-k-1) ->
          sprintf "(%s)%s" p1 p2]

Снова, это только приводит к списку тех строк с точно n пары parens (а не в большей части n), но легко перенести его.

Количество возможных комбинаций является каталонским количеством пар N C (n).

Эта проблема была обсуждена на форумах joelonsoftware.com симпатичный exentsively включая повторяющиеся, рекурсивные и iterative/bitshifting решения. Некоторый довольно интересный материал там.

Вот быстрое рекурсивное решение, предложенное на форумах в C#:

C#

public void Brackets(int pairs) {
    if (pairs > 1) Brackets(pairs - 1);
    char[] output = new char[2 * pairs];

    output[0] = '(';
    output[1] = ')';

    foo(output, 1, pairs - 1, pairs, pairs);
    Console.writeLine();
}

public void foo(char[] output, int index, int open, int close,
        int pairs) {
    int i;

    if (index == 2 * pairs) {
        for (i = 0; i < 2 * pairs; i++)
            Console.write(output[i]);
        Console.write('\n');
        return;
    }

    if (open != 0) {
        output[index] = '(';
        foo(output, index + 1, open - 1, close, pairs);
    }

    if ((close != 0) && (pairs - close + 1 <= pairs - open)) {
        output[index] = ')';
        foo(output, index + 1, open, close - 1, pairs);
    }

    return;
}

Скобки (3);

Вывод:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()

Не самое элегантное решение, но вот как я сделал это в C++ (Visual Studio 2008). Используя набор STL для устранения дубликатов, я просто наивно вставил новые пары () в каждый индекс строки в каждой строке из предыдущего поколения, а затем выполнил перебор.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>

using namespace System;
using namespace std;

typedef set<string> StrSet;

void ExpandSet( StrSet &Results, int Curr, int Max )
{
    if (Curr < Max)
    {
        StrSet NewResults;

        for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
        {
            for (unsigned int stri=0; stri < (*it).length(); stri++)
            {
                string NewStr( *it );
                NewResults.insert( NewStr.insert( stri, string("()") ) );
            }
        }
        ExpandSet( NewResults, Curr+1, Max );

        Results = NewResults;
    }
}    

int main(array<System::String ^> ^args)
{
    int ParenCount = 0;

    cout << "Enter the parens to balance:" << endl;
    cin  >> ParenCount;

    StrSet Results;
    Results.insert( string("()") );

    ExpandSet(Results, 1, ParenCount);

    cout << Results.size() << ": Total # of results for " << ParenCount << " parens:" << endl;

    for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
    {
        cout << *it << endl;
    }


    return 0;
}

Простое решение на C ++:

#include <iostream>
#include <string>

void brackets(string output, int open, int close, int pairs)
{
    if(open == pairs && close == pairs)
            cout << output << endl;
    else
    {
            if(open<pairs)
                    brackets(output+"(",open+1,close,pairs);
            if(close<open)
                    brackets(output+")",open,close+1,pairs);
    }
}

int main()
{
    for(int i=1;i<=3;i++)
    {
            cout << "Combination for i = " << i << endl;
            brackets("",0,0,i);
    }
}

Вывод:

Combination for i = 1
()
Combination for i = 2
(())
()()
Combination for i = 3
((()))
(()())
(())()
()(())
()()()

Haskell:

Я попытался придумать элегантный монадный способ списка:

import Control.Applicative

brackets :: Int -> [String]
brackets n = f 0 0 where
    f pos depth =
        if pos < 2*n
            then open <|> close
            else stop where
                -- Add an open bracket if we can
                open =
                    if depth < 2*n - pos
                        then ('(' :) <$> f (pos+1) (depth+1)
                        else empty

                -- Add a closing bracket if we can
                close = 
                    if depth > 0
                        then (')' :) <$> f (pos+1) (depth-1)
                        else empty

                -- Stop adding text.  We have 2*n characters now.
                stop = pure ""

main = readLn >>= putStr . unlines . brackets

почему это не так просто, эта идея довольно проста

скобки(n) --> '()' + скобки(n-1) 0 '(' + скобки (n-1) + ')' 0 скобки (n-1) + '()'

, где 0 — операция конкатенации, описанная выше

public static Set<String> brackets(int n) {
    if(n == 1){
        Set<String> s = new HashSet<String>();
        s.add("()");
        return s;
    }else{
        Set<String> s1 = new HashSet<String>();
        Set<String> s2 = brackets(n - 1);
        for(Iterator<String> it = s2.iterator(); it.hasNext();){
            String s = it.next();
            s1.add("()" + s);
            s1.add("(" + s + ")");
            s1.add(s + "()");
        }
        s2.clear();
        s2 = null;
        return s1;
    }
}