¿Cómo calculo el número de permutaciones en combinatoria de base 3?

StackOverflow https://stackoverflow.com/questions/447783

  •  22-07-2019
  •  | 
  •  

Pregunta

Nunca he sido demasiado para las matemáticas y espero que alguien pueda ayudarme con lo siguiente.

Tengo 5 cajas: 

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

Los cuadros pueden ser blancos, grises o negros (o considerarlos 0, 1, 2)

¿En cuántos estados posibles puede estar el conjunto de cajas?

¿Cuál es el pseudocódigo (o en cualquier idioma) para generar todos los resultados posibles?

es decir ... 

00000
00001
00011
00111

etc, etc ...

Realmente aprecio cualquier ayuda que alguien pueda brindarme con esto.

¿Fue útil?

Solución

Este es un problema clásico de generación de permutación. Tienes 3 posibilidades para cada posición y 5 posiciones. El número total de cadenas generadas es 3 ^ 5 = 243. Necesita recurrencia si desea una solución general (un bucle iterativo simple solo funciona para una sola instancia del problema).

Aquí hay un ejemplo 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);
    }
}

Otros consejos

la respuesta para el número de combinaciones es: 3x3x3x3x3 (3 ^ 5) ya que cada cuadro puede tener 3 colores posibles.

En cuanto a generar los resultados, vea si puede resolverlo usando esta matriz con 0, 1 o 2 para representar el color del cuadro. En una escala más pequeña (supongamos 3 cuadros) se vería así: 

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

Para responder a su primera pregunta, ¿cuál sería la respuesta si los cuadros pudieran contener solo uno de los dos valores? Entonces, ¿cuál es la respuesta si los cuadros contienen uno de tres valores?

Para responder a su segunda pregunta, ¿qué pseudocódigo genera todos los resultados posibles de una casilla? Ahora, ¿el pseudocódigo genera todos los resultados posibles de dos cuadros?

Recomiendo resolver el problema en papel primero. Intenta resolverlo con un número menor de cajas (quizás tres) y enumera todas las posibilidades. Luego, piense en cómo fue su razonamiento, o cómo explicaría lo que le hizo a un niño pequeño.

Gracias a todos por sus respuestas, al menos aquellos de ustedes que realmente me dieron una.

Si bien puedo apreciar que la pregunta sonaba como si hubiera sido sacada directamente de Computer Science 101, no lo fue. La ironía del asunto es que era para la vida real en un plazo real y no tuve tiempo de escuchar cuando me enseñaron estas cosas y me dije a mí mismo: "¿Cuándo voy a necesitar esta basura?" ;

Si quisiera ser patrocinado y tratado como un niño de escuela, volvería a mi escuela primaria y le preguntaría a mi maestro de quinto grado si puedo ir al baño

Gracias de nuevo

el número de estados es 3 ^ 5.

pseudocódigo es 

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

donde base3 es una función que toma repetidamente el módulo 3 para obtener un dígito, luego lo elimina (dividiendo por 3)

Sugerencia: imagine que cada cuadro es una posición en un número y cada color es un dígito diferente. En el mundo real, ¿cuántas combinaciones (incluido cero) obtienes con 2 posiciones y 10 dígitos posibles? ¿Qué pasa con 3 posiciones? ¿Cuál es la relación entre agregar una posición adicional y la cantidad de combinaciones, dada la cantidad de dígitos que tiene disponibles?

Número único de combinaciones: 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
}

Así es como aprendí por primera vez a hacer esto: primero piense en cuántas elecciones está haciendo. Estás haciendo cinco elecciones, una para cada caja. Escriba cinco líneas en blanco con signos de multiplicación: 

__ x __ x __ x __ x __ = ?

En cada espacio en blanco, escriba el número de objetos que debe elegir para ese cuadro. Como tiene 3 números para elegir para cada cuadro, escriba un 3 en cada en blanco: 

3 x 3 x 3 x 3 x 3 = 243

Esto le da el número total de permutaciones para esas opciones.

El número de posibilidades es 3 a la potencia 5

Si realiza un bucle de 0 a ese número menos 1 y lo expresa en la base 3, tendrá todas las posibilidades (recuerde anteponer 0 cuando sea necesario)

En 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

¿Puedo preguntar qué pasa con esto que no entiendes o qué te hace tropezar? Veo que todos aquí simplemente han respondido la pregunta, pero si ha copiado sus respuestas, no ha aprendido nada y, por lo tanto, se ha perdido completamente el punto de la tarea. Suponiendo que su próxima lección se base en esta, simplemente se quedará más atrás.

Si trabajaste para mí o estabas en mi clase, simplemente te preguntaría lo siguiente ...

" ¿Cómo crees que debería resolverse el problema? " La respuesta a la cual podría revelar dónde te estás colgando. Un sabio profesor mío en CMU dijo una vez: "No puedo ayudarte a entender esto hasta que sepas lo que no entiendes". Nunca descubrí lo que no entendía y abandoné su clase, pero la lección me quedó grabada.

Sé que probablemente sea demasiado tarde, pero para estas preguntas de tarea realmente creo que deberíamos ayudar a la persona a aprender en lugar de simplemente dar una respuesta y hacer la tarea por ella.

Su problema no necesita más que la regla del producto en combinatoria.

Puede elegir el estado del cuadro primero de 3 formas, y el estado del cuadro segundo de 3 maneras, y ... y el estado del 5to cuadro de 3 maneras. El número de formas en que puede establecer el estado de todos los cuadros es el producto de los cinco números (iguales) de formas, es decir, 3x3x3x3x3 = 3 5 .

Pregunta similar: ¿cuántos números puedes formar con 5 dígitos en el sistema decimal, contando los ceros a la izquierda? Es decir, ¿cuántos números hay de 00000 a 99999? Puede elegir el primer dígito de 10 maneras (0 ... 9), y así sucesivamente, y la respuesta es 10x10x10x10x10 = 100000, como ya sabe.

Esto parece un problema de tarea. Entonces te daré ayuda en cuanto a la solución.

Lo que está diciendo es que cada cuadro tiene tres estados, que son independientes. Una caja tendría 3 soluciones, y dos cajas tendrían 3 * 3 soluciones: para cada estado de la primera caja, la segunda caja también tendría tres estados. Extienda eso a 5 cajas.

Para generar cada solución, simplemente puede recorrerla. Es fácil hacer bucles anidados para cada cuadro, y multiplicar por potencias de 10 puede permitirle mostrar el número a la vez.

Puede generalizar el código para varios cuadros de manera similar.

¡Ni siquiera intentes escribir código para responder esto! La razón es que necesita algunos números muy grandes (factoriales) para calcularlo. Estos crean números mucho más grandes que cualquier tipo base en el CLR. Puede utilizar esta biblioteca de código abierto para hacer el 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 bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top