Número de arranjos

votos
4

Suponhamos que temos n elementos, um 1 , um 2 , ..., um N , dispostos em um círculo. Isto é, um 2 é entre um 1 e um 3 , uma 3 é entre um 2 e um 4 , um n é entre um n -1 e um 1 , e assim por diante.

Cada elemento pode ter o valor de 1 ou 0. Duas modalidades são diferentes se existirem correspondente um i 's cujos valores diferem. Por exemplo, quando n = 3, (1, 0, 0) e (0, 1, 0) são arranjos diferentes, embora possam ser isomorfa sob rotação ou reflexão.

Uma vez que existem n elementos, cada um dos quais pode ter dois valores, o número total de arranjos é 2 n .

Aqui está a questão:

Quantos arranjos são possíveis, de tal forma que há dois elementos adjacentes ambos têm o valor 1? Se ajudar, considerar apenas os casos em que n > 3.

Peço aqui por várias razões:

  1. Este surgiu enquanto eu estava resolvendo um problema de programação
  2. Parece que o problema pode se beneficiar de lógica aritmética booleana / bit
  3. Talvez não há solução fechada.
Publicado 10/12/2008 em 00:41
fonte usuário
Em outras línguas...                            


4 respostas

votos
10

Vamos primeiro fazer a pergunta "quantas 0-1 seqüências de comprimento n estão lá sem dois 1s consecutivos?" Deixe a resposta ser A (n). Temos A (0) = 1 (a sequência vazia), um (1) = 2 ( "0" e "1"), e A (2) = 3 ( "00", "01" e "10", mas não "11").

Para torná-lo mais fácil de escrever uma recorrência, vamos calcular A (n) como a soma de dois números:
B (n), o número de tais seqüências que terminam com um 0, e
C (n), o número de tais sequências que terminam com um 1.

Então B (n) = A (n-1) (ter qualquer sequência de comprimento n-1, e anexar um 0)
e C (n) = B (n-1) (porque se dispõe de um 1 na posição n , tem de ter um 0 a n-1.)
Isto dá-a (n) = B (n) + C (n) = a (n-1) + B (n-1) = a (n-1) + Uma (N-2). Agora deve ser :-) familiarizado

A (n) é simplesmente o número de Fibonacci F n + 2 , onde a sequência de Fibonacci é definido por
F 0 = 0, F 1 = 1, e M n + 2 = M n + 1 + F n para n ≥ 0.

Agora, para sua pergunta. Nós vamos contar o número de acordos com um 1 = 0 e um 1 = 1 separadamente. Para o primeiro, um 2 ... um n pode ser qualquer sequência de todo (sem 1s consecutivos), de modo que o número é A (n-1) = F N + 1 . Para este último, que deve ter uma 2 = 0, e, em seguida, um 3 ... um n é qualquer sequência sem 1s consecutivos que termina com um 0 , ou seja, B (n-2) = A (n-3) = F n- 1 .

Assim, a resposta é F n + 1 + F n-1 .

Na verdade, podemos ir ainda mais longe do que a resposta. Note-se que se chamar a resposta como
L (n) = M n + 1 + F n-1 , em seguida,
= L (n + 1) F + 2 n + F n , e
L (n + 2) = F N + 3 + F n + 1 , então mesmo g (n) a mesma satisfaz recorrência como a sequência de Fibonacci! [Na verdade, qualquer combinação linear de sequências de Fibonacci como irá satisfazer o mesmo recorrência, por isso não é tudo o que surpreendente.] Assim, uma outra maneira para calcular as respostas seria usando:
L (2) = 3
L (3) = 4
G ( n) = L (n-1) + L (n-2) para n≥4.

E agora também é possível usar a forma fechada F n = (α nn ) / (α-β) (onde α e β são (1 ± √5) / 2, as raízes de x 2 -x-1 = 0), para obter
L (n) = ((1 + √5) / 2) n + ((1-√5) / 2) n .
[Pode ignorar o segundo termo, porque isso é muito próximo de 0 para n grande, na verdade, g (n) é o número inteiro mais próximo de ((1 + √5) / 2) n para todos n≥2.]

Respondeu 10/12/2008 em 01:00
fonte usuário

votos
1

Eu decidi cortar um pequeno script para experimentá-lo:

#!/usr/bin/python
import sys

# thx google 
bstr_pos = lambda n: n>0 and bstr_pos(n>>1)+str(n&1) or ""

def arrangements(n):
    count = 0
    for v in range(0, pow(2,n)-1):
        bin = bstr_pos(v).rjust(n, '0')
        if not ( bin.find("11")!=-1 or ( bin[0]=='1' and bin[-1]=='1' ) ):
            count += 1
            print bin
    print "Total = " + str(count)

arrangements(int(sys.argv[1]))

A execução deste para 5, me deu um total de 11 possibilidades com 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

PS - Desculpe a não () no código acima.

Respondeu 10/12/2008 em 01:14
fonte usuário

votos
0

Este problema é muito semelhante a representações Zeckendorf . Não consigo encontrar uma maneira óbvia para aplicar o Teorema de Zeckendorf, devido à restrição circularidade, mas os números de Fibonacci são, obviamente, muito prevalente neste problema.

Respondeu 10/12/2008 em 01:38
fonte usuário

votos
0

Jogando meu script ingênuo na mistura. Muitas oportunidades para o cache de resultados parciais, mas correu rápido o suficiente para pequenas n que eu não me incomodei.

def arcCombinations(n, lastDigitMustBeZero):
    """Takes the length of the remaining arc of the circle, and computes
       the number of legal combinations.
       The last digit may be restricted to 0 (because the first digit is a 1)"""

    if n == 1: 
        if lastDigitMustBeZero:
            return 1 # only legal answer is 0
        else:
            return 2 # could be 1 or 0.
    elif n == 2:
        if lastDigitMustBeZero:
            return 2 # could be 00 or 10
        else:
            return 3 # could be 10, 01 or 00
    else:
        # Could be a 1, in which case next item is a zero.
        return (
            arcCombinations(n-2, lastDigitMustBeZero) # If it starts 10
            + arcCombinations(n-1, lastDigitMustBeZero) # If it starts 0
            )

def circleCombinations(n):
    """Computes the number of legal combinations for a given circle size."""

    # Handle case where it starts with 0 or with 1.
    total = (
            arcCombinations(n-1,True) # Number of combinations where first digit is a 1.
            +
            arcCombinations(n-1,False) # Number of combinations where first digit is a 0.
        )
    return total


print circleCombinations(13)
Respondeu 10/12/2008 em 01:16
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more