Como se produz eficientemente todas as seqüências binárias com um número igual de 0 e 1?

Uma sequência binária de comprimento é apenas uma sequência ordenada para que cada seja ou . Para gerar todas essas seqüências binárias, pode-se usar a estrutura óbvia da árvore binária da seguinte maneira: a raiz está "vazia", mas cada filho esquerdo corresponde à adição de à cadeia existente e cada filho direito a um . Agora, cada sequência binária é simplesmente um caminho de comprimento começando na raiz e terminando em uma folha. $n$ $x_1,\ldots,x_n$ $x_j$ $0$ $1$ $0$ $1$ $n+1$

Aqui está a minha pergunta:

Podemos fazer melhor se quisermos gerar apenas todas as seqüências binárias de comprimento que possuem exatamente zeros e ? $2n$ $n$ $n$

Por "podemos melhorar", quero dizer que devemos ter uma complexidade menor do que o algoritmo tolo que primeiro constrói a árvore inteira acima e depois tenta encontrar esses caminhos com um número igual de bordas "esquerda" e "direita".

algorithms graphs binary-trees Vidit Nanda
fonte

Você consegue encontrar uma maneira de gerar com eficiência todas as seqüências estritamente crescentes de números no intervalo de 1 a ?

n

$n$

2 n

$2n$

Cornelius Marca

Não posso comentar sobre a complexidade, mas meu algoritmo ingênuo geraria os passeios ao longo das bordas de uma grade quadrada de um canto a um diagonal, usando o tipo de esquema de retorno. Isso significa que 01 e 10 terminam na mesma posição (ao contrário da sua árvore), mas com retorno sabemos essa história.

Hendrik Jan

Em uma observação possivelmente diferente, aqui está uma implementação em Java de umiterador .

(\binom{n}{k})

${n \choose k}$

Gål GD

Respostas:

Obviamente, existem cadeias binárias de comprimento . Para percorrer o binário, um algoritmo precisa visitar cada nó uma vez, ou seja, etapas. $4^{n}$ $2n$

\sum_{i = 0}^{2 n} 2^{i} = 2^{2 n + 1} - 1 = O (4^{n})

$\sum_{i=0}^{2n} 2^i = 2^{2n+1} - 1 = \mathcal{O}(4^n)$

Vamos considerar um algoritmo recursivo que atravessa a árvore que você descreveu, mas conta o número de uns e zeros no caminho, ou seja, ele percorre apenas a parte boa da árvore.
Mas quantas cadeias binárias com 0 e 1 existem? Escolhemos 1s para nossas seqüências de comprimento e usamos a fórmula de Stirling na etapa 2: $n$ $n$ $n$ $2n$

(\binom{2 n}{n}) = \frac{(2 n)!}{(n!)^{2}} = \frac{4^{n}}{\sqrt{π n}} (1 + O (1 / n))

${2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{4^n}{\sqrt{\pi n}} (1 + \mathcal{O}(1/n))$

EDIT
Graças aos comentários de Peter Shor, também podemos analisar o número de etapas necessárias pelo segundo algoritmo, que conta os 1 e os 0. Estou citando seu comentário abaixo:

Queremos encontrar todas as seqüências binárias com exatamente 0 e 1. Atravessamos a árvore binária em que cada nó é uma sequência de no máximo 0 e 1. Não precisamos visitar nenhum nó com mais de 0 ou mais de 1. quantos nós precisamos visitar? Existem strings com 0 e 1's. Somando isso fornece . Agora, precisamos visitar cada um desses nós a um custo médio constante por nó. Podemos fazer isso visitando cada filho esquerdo primeiro e cada filho direito segundo. $n$ $n$ $2n$ $n$ $n$ ${i+j \choose i}$ $i$ $j$ $i,j \leq n$ $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} − 1$

Usando a fórmula de Stirling novamente, obtemos como o tempo de execução do novo algoritmo.

(\binom{2 n + 2}{n + 1}) - 1 = 4^{n + 1} \frac{1}{\sqrt{n + 1}} (1 + O (1 / n)) - 1 = O (\frac{4^{n}}{\sqrt{n}})

${2n + 2 \choose n + 1} - 1 = 4^{n+1} \frac{1}{\sqrt{n+1}} (1 + \mathcal{O}(1/n)) - 1 = \mathcal{O}(\frac{4^n}{\sqrt{n}})$

tranisstor
fonte

Você tem que ter um pouco mais de cuidado. Presumivelmente, depois de gerar cada string, nós a processamos em . Portanto, apenas o processamento de todas as seqüências balanceadas leva tempo . Se o algoritmo de geração "bobo" otimizado é de fato , não há muito a ganhar com a mudança para um algoritmo mais inteligente, além de oportunidades para bugs.

Ω (n)

$\Omega(n)$

Ω (4^{n} \sqrt{n})

$\Omega(4^n \sqrt{n})$

O (4^{n})

$O(4^n)$

Yuval Filmus

@Yuval Filmus: O que exatamente você quer dizer com "processamento de strings"? Se você quer dizer o tempo gasto na saída, que é certamente , também é necessário considerar esse fator no tempo de execução do algoritmo "bobo", que é .

Θ (n)

$\Theta(n)$

O (4^{n} n)

$O(4^n n)$

Travisstor

Meu argumento foi que, se você está preocupado com a diferença entre e , então, no mínimo, você precisa indicar os tempos de execução corretos; não é suficiente para revelar qualquer diferença de potencial entre os dois algoritmos. Além disso, você deve ter cuidado ao analisar o novo algoritmo proposto, para verificar se esses pequenos fatores "desprezíveis" não o tornam mais lento que o trivial.

4^{n}

$4^n$

4^{n} / \sqrt{n}

$4^n/\sqrt{n}$

\tilde{O} (4^{n})

$\tilde{O}(4^n)$

Yuval Filmus

Como você constrói apenas a "parte boa" da árvore sem precisar incluir também as "partes ruins"? Você precisa incluir todos os nós da árvore que não tenham mais que filhos esquerdos ou filhos certos no caminho da raiz para eles. Isso funciona, mas você precisa de um argumento adicional para mostrar que funciona. Especificamente, você precisa usar a fórmula .

n

$n$

n

$n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n} (\binom{i + j}{i}) = (\binom{2 n + 2}{n + 1}) - 1

$\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} -1$

Peter Shor

Queremos encontrar todas as seqüências binárias com exatamente 0 e 1. Atravessamos a árvore binária em que cada nó é uma sequência de no máximo 0 e 1. Não precisamos visitar nenhum nó com mais de 0 ou mais de 1. quantos nós precisamos visitar? Existem strings com 0 e 1's. Somando tudo isso fornece . Agora, precisamos visitar cada um desses nós a um custo médio constante por nó. Podemos fazer isso visitando cada filho esquerdo primeiro e cada filho direito segundo.

n

$n$

n

$n$

2 n

$2n$

n

$n$

n

$n$

(\binom{i + j}{i})

$i+j \choose i$

i

$i$

j

$j$

i, j \leq n

$i,j \leq n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n} (\binom{i + j}{i}) = (\binom{2 n + 2}{n + 1}) - 1

$\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i}={2n+2 \choose n+1}-1$

Peter Shor

Talvez eu esteja sendo grossa, mas a pergunta original pediu uma maneira de gerar todas as seqüências binárias "equilibradas" de comprimento 2n que fossem mais eficientes do que atravessar uma árvore de todas as sequências binárias de comprimento 2n e produzir apenas aquelas que estavam equilibradas. Então, por que usar uma árvore?

Aqui está o pseudocódigo para um algoritmo recursivo que gera todas essas seqüências (a palavra-chave "yield" envia uma sequência para a saída):

function all-balanced(n) {
  all-specified( "", n, n );
};

function all-specified( currentString, zeroes, ones ) {

  if (zeroes == 0) {
    for i = 0 to ones {
      currentString += "1";
    };
    yield currentString;
    return;
  };

  if (ones == 0) {
    for i = 0 to zeroes {
      currentString += "0";
    };
    yield currentString;
    return;
  };

  all-specified( currentString+"0", zeroes-1, ones );
  all-specified( currentString+"1", zeroes, ones-1 );
  return;
};

Se estou entendendo algo errado, diga-me, mas me parece que essa é a resposta mais eficiente para o problema realmente colocado, que nunca especificou o uso de uma árvore.

afeldspar
fonte