Como faço para calcular o número de permutações na base de 3 combinatória?

https://stackoverflow.com/questions/447783

22-07-2019
|

Pergunta

Eu nunca fui muito de matemática e eu estou esperando que alguém pode me ajudar com o seguinte.

Eu tenho 5 caixas:

 1   2   3   4   5
[ ] [ ] [ ] [ ] [ ]

As caixas podem ser branco, cinza ou preto (ou pensar nele como 0, 1, 2)

Como muitos estados possíveis pode o conjunto de caixa estar?

O que é o pseudocódigo (ou em qualquer língua) para gerar todos os resultados possíveis ??

ou seja ...

etc, etc ...

Eu realmente aprecio qualquer ajuda ninguém pode me dar com isso.

Solução

Este é um problema clássico geração permutação. Você tem 3 possibilidades para cada posição, e 5 posições. O número total de cadeia gerada é 3 ^ 5 = 243. Você precisa recursão se você quer uma solução geral (um loop iterativo simples só funciona para uma única instância do problema).

Aqui está um exemplo rápido:

public static void Main(string[] args){

    Generate("", 5);
}

private void Generate(string s, int limit)
{
    if (s.Length == limit)
        Console.WriteLine(s);
    else
    {
        Generate(s+"0", limit);
        Generate(s+"1", limit);
        Generate(s+"2", limit);
    }
}

Outras dicas

a resposta para o número de combinações é:. 3x3x3x3x3 (3 ^ 5) uma vez que cada caixa pode ter 3 cores possíveis

Como para gerar os resultados, veja se você pode descobrir isso usando esta matriz com 0, 1, ou 2 para representar a cor da caixa. Em uma escala menor (vamos supor 3 caixas) que seria parecido com isto:

Para responder à sua primeira pergunta, o que a resposta seria se as caixas poderia conter apenas um de dois valores? Então, qual é a resposta se as caixas contêm um dos três valores?

Para responder à sua segunda pergunta, o que pseudocódigo gera todos os possíveis resultados de uma caixa? Agora, pseudocódigo gera todos os possíveis resultados de duas caixas?

Eu recomendo resolver o problema no papel primeiro. Tentar resolvê-lo com um número menor de caixas (talvez três), e lista todas as possibilidades. Então, pense em como o seu raciocínio foi, ou como você explicar o que você fez para uma criança pequena.

Obrigado a todos por suas respostas, pelo menos aqueles de vocês que realmente me deu um.

Embora eu possa compreender que a questão parecia que estava puxado para fora em linha reta de Ciência da Computação 101, não foi. A ironia da questão é que era para a vida real em um prazo real e eu não tinha tempo para ouvir de volta a quando eu estava sendo ensinado isso e disse a mim mesmo "quando é que eu vou precisar essa porcaria"

Se eu quisesse ser apadrinhado e tratado como um menino de escola eu iria voltar para minha escola primária e pedir meu 5o professor da categoria se eu pode ir ao banheiro

Obrigado novamente

o número de estados é de 3 ^ 5.

pseudocódigo seja

for value from 0 to 3^5-1
    print base3(value)

onde base3 é uma função que leva repetidamente modulo 3 para obter um dígito, em seguida, remove esse dígito (dividindo por 3)

Dica: imagine que cada caixa é uma posição em um número e cada cor é um dígito diferente. No mundo real, quantas combinações (incluindo zero) que você ganha com 2 posições e 10 dígitos possíveis? O que cerca de 3 posições? Qual é a relação entre adicionar uma posição extra e o número de combinações, dado o número de dígitos que você tem disponível?

Número único de combinações: 3^5=243

Código:

n = 0
for i = 0 to 3^5-1
{
    s = ""
    for j = 1 to 5
    {
        d = n mod 3
        s = toascii(d) . s
        n = n / 3
    }
    println s
    i = i + 1
}

Aqui está como eu aprendi a fazer isso: primeiro pensar em quantas escolhas que você está fazendo. Você está fazendo cinco opções, uma para cada caixa. Então escreva cinco linhas em branco com a multiplicação sinais:

__ x __ x __ x __ x __ = ?

Em cada espaço em branco, escreva o número de objetos que você tem para escolher para que a caixa. Desde que você tem 3 números para escolher para cada caixa, você escreve um 3 em todas em branco:

3 x 3 x 3 x 3 x 3 = 243

Isto dá-lhe o número total de permutações para essas escolhas.

O número de possibilidades é de 3 a 5 a potência

Se você ciclo de 0 a esse número menos 1 e expressá-lo na base 3 você terá todas as possibilidades (lembre-se de 0s preceder quando necessário)

Em Ruby:

number_of_possibilities = 3**5-1

for i in (0..number_of_possibilities)
  base_3_number = i.to_s(3)
  puts "%05d" % base_3_number # number formatting used to prepend 0s where necessary
end

Posso perguntar o que sobre isso que você não entende ou o que é que você tropeçar? Eu vejo que todo mundo aqui tem simplesmente respondeu à pergunta, mas se você copiou as suas respostas, você aprendeu nada, e, assim, perdeu completamente o ponto do trabalho de casa. Supondo que sua próxima lição baseia-se este, você só vai cair ainda mais para trás.

Se você quer trabalhou para mim ou estavam em minha classe eu simplesmente pedir o seguinte ...

"Como você acha que o problema deve ser resolvido?" A resposta para que possa revelar onde você está ficando pendurado. Um professor sábio da mina na CMU, uma vez disse: "Eu não posso ajudá-lo a entender isso até que você sabe o que você não entende" Eu nunca fiz pensar no que eu não entendia e eu soltou sua classe, mas a lição preso com me.

Eu sei que é provavelmente tarde demais, mas para estas perguntas de casa Eu realmente acho que deveríamos estar ajudando a pessoa a aprender ao invés de simplesmente dar uma resposta e fazer sua lição de casa para eles.

Seu problema não precisa de nada mais do que a regra de produto em análise combinatória.

Você pode escolher o estado da início caixa de 3 maneiras, e o estado da segunda caixa de 3 maneiras, e ... e o estado da 5ª caixa de 3 maneiras. O número de maneiras em que você pode definir o estado de todas as caixas é o produto de todos os cinco números (iguais) de formas, ou seja, 3x3x3x3x3 = 3 ⁵.

pergunta homóloga: quantos números você pode formar com 5 dígitos no sistema decimal, contando os zeros à esquerda? Ou seja, quantos números estão lá 00000-99999? Você pode escolher o primeiro dígito em 10 maneiras (0 ... 9), e assim por diante e assim por diante, ea resposta é 10x10x10x10x10 = 100000, como você já sabe.

Este parece ser um problema lição de casa. Eu só vou lhe dar alguma ajuda quanto à solução seguida.

O que você está dizendo é que cada caixa tem três estados, que são todos independentes. Uma caixa teria 3 soluções, e duas caixas teria 3 * 3 soluções - para cada estado da primeira caixa a segunda caixa teria três estados também. Estender isso para 5 caixas.

Para gerar cada solução, você pode apenas percorrer-lo. É fácil de fazer aninhados loops para cada caixa, e multiplicando por potências de 10 pode deixá-lo mostrar o número de uma só vez.

Você pode generalizar o código para múltiplas caixas de uma forma similar.

Nem sequer tentar escrever código para responder a esta! A razão é que você precisa de alguns números muito grandes (fatoriais) para calculá-lo. Estes criam um número muito maior do que qualquer tipo de base no CLR. Você pode usar este opensource biblioteca para fazer o cálculo.

void solve(int p=0,int n=5,int d=0)
{
    if (n==p)
    {
        int rev=d;
        int i=0;
        while (i<5) {
            cout << rev%10;
            rev /= 10;
            i++;## Heading ##
        }
        cout << endl;
        return;
    }
    for(int i=0; i<3 ; i++)
    {
        solve(p+1,n, d*10 + i);
    }
}

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow