Java: Generador de combinaciones de true y falso dando el número N;

Question

Atado para simplificar la tarea tanto como sea posible, para poder aplicarla a mi algoritmo.

Y aquí es el reto para los matemáticos y programadores:

Necesito crear un método en el Paso parámetro int n:

public void optionality_generator(int n){ 
    //some kind of loops, or recursions...to make it workable 
    System.out.println("current combination: ..."); 
} 

La salida debe mostrar todas las combinaciones posibles de los verdaderos y falsos de.

Aquí hay ejemplos donde N = 1; N = 2; N = 3; N = 4; N = 5 donde x = falso y 0 = verdadero; Tenga en cuenta que las líneas de ruptura vacías son solo para que usted reconozca más fácilmente los patrones. Con suerte, he incluido todas las combinaciones posibles):

Combination of 1: 
0 
x 

Combination of 2: 
00 
x0 
0x 
xx 

Combination of 3: 
000 
X00 
0X0 
00X 
XX0 
0XX 
XXX 

Combination of 4: 
0000 

X000 
0X00 
00X0 
000X 

XX00 
X0X0 
X00X 

0XX0 
0X0X 

00XX 

XXX0 
XX0X 
X0XX 
0XXX 

XXXX 

Combination of 5: 
00000 
X0000 
0X000 
00X00 
000X0 
0000X 

XX000 
X0X00 
X00X0 
X000X 

X0X00 
X00X0 
X000X 

0XX00 
0X0X0 
0X00X 

00XX0 
00X0X 

000XX 

XXX00 
XX0X0 
XX00X 

X0XX0 
X0X0X 
X00XX 

0XXX0 
0XX0X 

00XXX 

XXXX0 
XXX0X 
XX0XX 
X0XXX 
0XXXX 

XXXXX 

Además, si usted ve la salida, aquí es el patrón me di cuenta, que todas las combinaciones son invertidas en medio (por ejemplo, primera combinación es 00000 última será XXXXX, el segundo X0000, uno antes del último será 0XXXX, etc.). Tal vez, este patrón ayudará a que todo el algoritmo sea más eficiente, no estoy seguro de esto. ¡Gracias de antemano!

Answer 1

Aquí es una manera muy básica utilizando sólo las API de Java:

final int n = 3; 
for (int i = 0; i < Math.pow(2, n); i++) { 
    String bin = Integer.toBinaryString(i); 
    while (bin.length() < n) 
     bin = "0" + bin; 
    System.out.println(bin); 
} 

Resultado:

000 
001 
010 
011 
100 
101 
110 
111 

Por supuesto, se puede establecer n a lo que quiera. Y, con este resultado, puede elegir el carácter n th de la cadena como verdadero/falso.

Si solo necesita comprobar si un bit es verdadero, no necesita convertirlo en una cadena. Esto es solo para ilustrar los valores de salida.

Answer 2

Solo una pista, pero piense en los bits que se establecen para un número con la mayoría de 'n' bits. Verá si pasa de 0 a 'n' cantidad de bits (3 en este caso); los bits son 000, 001, 010, 011, 100, 101, 110, 111. Puede calcular el número máximo que puede caber en 'n' bits utilizando la fórmula ((n * n) -1).

Answer 3

Aquí es una versión simple implementado utilizando la recursividad

public void optionality_generator(int n){ 
    ArrayList<String> strings = generatorHelper(n); 
    for(String s : strings){ 
     System.out.println(s); 
    } 
} 

private ArrayList<String> generatorHelper(int n){ 
    if(n == 1){ 
     ArrayList<String> returnVal = new ArrayList<String>(); 
     returnVal.add("0"); 
     returnVal.add("X"); 
     return returnVal; 
    } 
    ArrayList<String> trueStrings = generatorHelper(n-1); 
    for(String s : trueStrings){ 
     s += "0"; 
    } 
    ArrayList<String> falseStrings = generatorHelper(n-1); 
    for(String s : falseStrings){ 
     s += "X"; 
    } 
    trueStrings.addAll(falseStrings); 
    return trueStrings; 
} 

Answer 4

Esto debería hacer el truco

int cols = 3; 
int rows = (int) Math.pow(2, cols); 
for (int row = 0; row < rows; row++) 
    System.out.println(String.format("%" + cols + "s", 
      Integer.toBinaryString(row)).replace(' ', '0').replace('1', 'X')); 

a cabo:

000 
00X 
0X0 
0XX 
X00 
X0X 
XX0 
XXX 

Answer 5

Aquí hay una versión en pruebas:

import static org.junit.Assert.assertEquals; 

import java.util.ArrayList; 
import java.util.List; 

import org.junit.Test; 

public class OptionalityTest { 

    @Test 
    public void testOptionality0() throws Exception { 
     assertEquals("[]", optionality(0).toString()); 
    } 

    @Test 
    public void testOptionality1() throws Exception { 
     assertEquals("[0, x]", optionality(1).toString()); 
    } 

    @Test 
    public void testOptionality2() throws Exception { 
     assertEquals("[00, x0, 0x, xx]", optionality(2).toString()); 
    } 

    @Test 
    public void testOptionality3() throws Exception { 
     assertEquals("[000, x00, 0x0, xx0, 00x, x0x, 0xx, xxx]", optionality(3).toString()); 
    } 

    private List<String> optionality(int i) { 
     final ArrayList<String> list = new ArrayList<String>(); 
     if (i == 1) { 
      list.add("0"); 
      list.add("x"); 
     } 
     if (i > 1) { 
      List<String> sublist = optionality(i - 1); 
      for (String s : sublist) { 
       list.add("0" + s); 
       list.add("x" + s); 
      } 
     } 
     return list; 
    } 

} 

Answer 6

Aquí hay una modificación del código Erics anterior, que usa C# y permite la entrada de cualquier número de nombres de variables booleanas. Emitirá todas las combinaciones posibles en el código C# listo para insertar en una instrucción if. Simplemente edite la primera línea de código con nombres var, y luego ejecútelo en LINQpad para obtener una salida de texto.

Ejemplo de salida ...

!VariableNameA && !VariableNameB && !VariableNameC 
!VariableNameA && !VariableNameB && VariableNameC 
!VariableNameA && VariableNameB && !VariableNameC 
!VariableNameA && VariableNameB && VariableNameC 
VariableNameA && !VariableNameB && !VariableNameC 
VariableNameA && !VariableNameB && VariableNameC 
VariableNameA && VariableNameB && !VariableNameC 
VariableNameA && VariableNameB && VariableNameC 

//To setup edit var names below 
 
    string[] varNames = { "VariableNameA", "VariableNameB", "VariableNameC" }; 
 

 
    int n = varNames.Count();   
 
    for (int i = 0; i < Math.Pow(2, n); i++) { 
 
     String bin = Convert.ToString(i, 2); 
 
     while (bin.Length < n) { 
 
      bin = "0" + bin; 
 
     }   
 
     string and = " && "; 
 
     string f = "!"; 
 
     string t = " "; 
 
     var currentNot = bin[0] == '0' ? f : t; 
 
     //string visual = bin[0].ToString(); 
 
     string visual = currentNot + varNames[0]; 
 
     for (var j = 1; j < n; j++) { 
 
     currentNot = bin[j] == '0' ? f : t; 
 
     //visual = visual + and + bin[j].ToString(); 
 
     visual = visual + and + currentNot + varNames[j]; 
 
     } \t \t 
 
     Console.WriteLine(visual); \t 
 
    }