programa - ¿Cómo obtener todas las combinaciones posibles de dos arreglos en Java?

insertar elementos en un arreglo java

Question

Tengo las dos matrices:

String[] operators = {"+", "-", "*"};
int[] numbers = {48, 24, 12, 6};

Y quiero obtener todas las combinaciones posibles en un formato de cadena como este:

48+24+12+6
48+24+12-6
48+24+12*6
48+24-12+6
48+24-12-6
48+24-12*6
..........
48*24*12*6

Esto es lo que he intentado:

for(int i = 0; i < operators.length; i++) {
    System.out.println(numbers[0] + operators[i] + numbers[1] + operators[i] + numbers[2] + operators[i] + numbers[3]);
}

Pero solo imprime:

48+24+12+6
48-24-12-6
48*24*12*6

¿Cómo resolver esto?

Esto no es un duplicado porque no quiero obtener cada dos pares de datos, quiero obtener cada combinación en 4 pares. El duplicado es diferente.

Answer 1

Como ya lo señaló findusl en su respuesta , el problema aquí es, estrictamente hablando, no encontrar ningún tipo de "combinación de dos matrices". En su lugar, básicamente solo desea encontrar todas las combinaciones posibles de los operadores disponibles.

(El hecho de que luego quieras "intervenir" con los operandos no tiene nada que ver con el núcleo de la pregunta)

Así que aquí hay otra opción para resolver esto: puede crear un iterable sobre todas las combinaciones de un cierto número de elementos de un determinado conjunto (en su caso: los operadores) y luego simplemente combinar los resultados con el otro conjunto (en su caso: los operandos).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class OperatorsTest
{
    public static void main(String[] args)
    {
        String[] operators = {"+", "-", "*"};
        int[] numbers = {48, 24, 12, 6};

        CombinationIterable<String> iterable = 
            new CombinationIterable<String>(3, Arrays.asList(operators));
        for (List<String> element : iterable)
        {
            System.out.println(interveave(element, numbers));
        }
    }

    private static String interveave(List<String> operators, int numbers[])
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<operators.size(); i++)
        {
            sb.append(numbers[i]);
            sb.append(operators.get(i));
        }
        sb.append(numbers[numbers.length-1]);
        return sb.toString();
    }

}

class CombinationIterable<T> implements Iterable<List<T>>
{
    private final List<T> input;
    private final int sampleSize;
    private final int numElements;
    public CombinationIterable(int sampleSize, List<T> input)
    {
        this.sampleSize = sampleSize;
        this.input = input;
        numElements = (int) Math.pow(input.size(), sampleSize);
    }

    @Override
    public Iterator<List<T>> iterator()
    {
        return new Iterator<List<T>>()
        {
            private int current = 0;
            private final int chosen[] = new int[sampleSize];

            @Override
            public boolean hasNext()
            {
                return current < numElements;
            }

            @Override
            public List<T> next()
            {
                if (!hasNext())
                {
                    throw new NoSuchElementException("No more elements");
                }

                List<T> result = new ArrayList<T>(sampleSize);
                for (int i = 0; i < sampleSize; i++)
                {
                    result.add(input.get(chosen[i]));
                }
                increase();
                current++;
                return result;
            }

            private void increase()
            {
                int index = chosen.length - 1;
                while (index >= 0)
                {
                    if (chosen[index] < input.size() - 1)
                    {
                        chosen[index]++;
                        return;
                    }
                    chosen[index] = 0;
                    index--;
                }
            }
        };
    }
}

La tarea se asemeja a la de encontrar un conjunto de operaciones que se pueden realizar con un cierto número de operandos y operadores, y por lo tanto, esta Q / A puede estar relacionada. Pero no se mencionó en la pregunta si las cosas como asociatividad o conmutatividad deben considerarse aquí.

Answer 2

Esto suena como un caso de libro de texto para una solución recursiva:

public static void combineAndPrint(String[] pieces, String[] operators) {
    if (pieces.length < 1) {
        // no pieces? do nothing!
    } else if (pieces.length == 1) {
        // just one piece? no need to join anything, just print it!
        System.out.println(pieces[0]);
    } else {
        // make a new array that''s one piece shorter
        String[] newPieces = new String[pieces.length - 1];
        // copy all but the first two pieces into it
        for (int i = 2; i < pieces.length; i++) {
            newPieces[i - 1] = pieces[i];
        }
        // combine the first two pieces and recurse
        for (int i = 0; i < operators.length; i++) {
            newPieces[0] = pieces[0] + operators[i] + pieces[1];
            combineAndPrint(newPieces, operators);
        }
    }
}

public static void main(String[] args) {
    String[] operators = {"+", "-", "*"};
    String[] numbers = {"48", "24", "12", "6"};
    combineAndPrint(numbers, operators);
}

Pruébalo en línea!

Por cierto, para generalizar este método para que pueda hacer más cosas con las expresiones generadas que solo imprimirlas, recomendaría que acepte un parámetro Consumer<String> adicional. Es decir, podría reescribir la declaración del método como:

public static void combine(String[] pieces, String[] operators, Consumer<String> consumer) {

y reemplace System.out.println(pieces[0]) con consumer.accept(pieces[0]) y la llamada recursiva a combineAndPrint(newPieces, operators) con combine(newPieces, operators, consumer) . Entonces simplemente llámelo desde su método principal, por ejemplo, como:

combine(numbers, operators, s -> System.out.println(s));

Pruébalo en línea!

(Por supuesto, hacerlo de esta manera más flexible requiere una versión de Java algo moderna, Java 8 o posterior, para ser específico), mientras que el primer ejemplo que mostré arriba debería funcionar incluso en versiones antiguas hasta Java 1.0. en alguna versión futura de Java obtendremos el soporte adecuado para coroutines y generadores, como Python y Kotlin e incluso los JS modernos que ya tienen, y entonces ya no necesitaremos pasarle más al consumidor.)

Answer 3

He desarrollado una clase que cubre este caso de uso y muchos otros. Yo lo llamo el TallyCounter . Tu pregunta sería respondida con esta clase como esta:

package app;

import java.util.HashMap;
import java.util.Map;

import app.TallyCounter.Type;

public class App {

    public static void main(String args[]) throws Exception {

        Map<Long, String> map = new HashMap<>();
        map.put(0l, "+");
        map.put(1l, "-");
        map.put(2l, "*");

        TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
        do {
            System.out.format("48%s24%s12%s6/n",
                map.get(counter.getArray()[2]),
                map.get(counter.getArray()[1]),
                map.get(counter.getArray()[0])
            );
            counter.increment();
        } while (!counter.overflowFlag);
    }
}

Answer 4

Hice una solución de "negocio" alternativa, en exceso de ingeniería (¡pero flexible!). Las longitudes y valores de la matriz ( numbers y operators ) pueden ser flexibles.

package test1;

import java.io.IOException;
import java.util.ArrayList;

public class MainClass
{
    public static void main(String[] args) throws IOException
    {
        String[] operators = {"+", "-", "*"};
        int[] numbers = {48, 24, 12, 6};

        ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);

        for (String string : strings)
        {
            System.out.println(string);
        }
    }

    private ArrayList<String> getAllPossibleCombinations(int[] numbers, String[] operators)
    {
        if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2");
        if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1");

        ArrayList<String> returnList = new ArrayList<>();
        int[] indexes = new int[numbers.length - 1];

        while (true)
        {
            StringBuilder line = new StringBuilder();

            for (int i = 0; i < numbers.length; i++)
            {
                int number = numbers[i];
                line.append(number);

                if (i < indexes.length)
                {
                    line.append(operators[indexes[i]]);
                }
            }

            returnList.add(line.toString());

            try
            {
                this.updateIndexes(indexes, operators.length - 1);
            }
            catch (NoMoreCombinationsException e)
            {
                break;
            }
        }

        return returnList;
    }

    private void updateIndexes(int[] currentIndexes, int maxValue) throws NoMoreCombinationsException
    {
        if (this.intArrayIsOnly(currentIndexes, maxValue))
        {
            throw new NoMoreCombinationsException();
        }

        for (int i = currentIndexes.length - 1; i >= 0; i--)
        {
            int currentIndex = currentIndexes[i];

            if (currentIndex < maxValue)
            {
                currentIndexes[i] = currentIndex + 1;
                break;
            }
            else
            {
                currentIndexes[i] = 0;
            }
        }
    }

    private boolean intArrayIsOnly(int[] array, int value)
    {
        for (int iteratedValue : array)
        {
            if (iteratedValue != value) return false;
        }

        return true;
    }
}

class NoMoreCombinationsException extends Exception
{
    public NoMoreCombinationsException()
    {
    }

    public NoMoreCombinationsException(String message)
    {
        super(message);
    }

    public NoMoreCombinationsException(String message, Throwable cause)
    {
        super(message, cause);
    }

    public NoMoreCombinationsException(Throwable cause)
    {
        super(cause);
    }

    public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace)
    {
        super(message, cause, enableSuppression, writableStackTrace);
    }
}

Funciona de maravilla :)

Answer 5

No necesitas múltiples bucles ni recursión.

Aquí hay un ejemplo que muestra un número limitado de bucles y ninguna recursión.

int[][] combine (int[] values) {
  int size = values.length;
  int combinations = 1;
  for(int i = 0; i < size; i++) {
    combinations *= size;
  }
  // or int combinations = (int)Math.pow(size, size);
  int[][] result = new int[combinations][size];
  for(int i = 0; i < combinations; i++) {
    int index = i;
    for(int j = 0; j < size; j++) {
      result[i][j] = values[index % size];
      index /= size;
    }
  }
  return result;
}

Si lo usa con tres elementos, [1, 2, 3] , como en el siguiente código:

void testCombine() {
  int[][] combinations = combine(new int[]{1, 2, 3});
  for(int[] combination: combinations) {
    System.out.println(Arrays.toString(combination));
  }
}

Terminas con el siguiente resultado:

[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
[3, 3, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[1, 1, 3]
[2, 1, 3]
[3, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]

Answer 6

Si bien la solución @TimBiegeleisen funcionaría como un encanto, su complejidad podría ser un problema. El mejor enfoque sería un código como este:

static void combinationUtil(int[] arr, int n, int r, int index, int[] data, int i) 
    { 
        // Current combination is ready to be printed, print it 
        if (index == r) 
        { 
            for (int j=0; j<r; j++) 
                System.out.print(data[j]+" "); 

            System.out.println(""); 

        return; 

        } 

        // When no more elements are there to put in data[] 
        if (i >= n) 
           return; 

        // current is included, put next at next location 
        data[index] = arr[i]; 
        combinationUtil(arr, n, r, index+1, data, i+1); 

        // current is excluded, replace it with next (Note that 
        // i+1 is passed, but index is not changed) 
        combinationUtil(arr, n, r, index, data, i+1); 
    } 

    // The main function that prints all combinations of size r 
    // in arr[] of size n. This function mainly uses combinationUtil() 
    static void printCombination(int arr[], int n, int r) 
    { 
        // A temporary array to store all combination one by one 
        int data[]=new int[r]; 

        // Print all combination using temprary array ''data[]'' 
        combinationUtil(arr, n, r, 0, data, 0); 
    } 

Fuente: GeeksForGeeks y mi IDE :)

Answer 7

Un poco de información de fondo por qué las respuestas son como son. Este problema realmente no se denomina "todas las combinaciones posibles", ya que suele ser el problema en el que puede representar los elementos como bits y cambiarlos a 0 o 1, ya sea que el elemento esté incluido o no. Esto tiene una complejidad de 2 ^ N donde N es la cantidad de operadores que tiene. Esto se puede resolver fácilmente en un solo bucle.

Sin embargo, en su caso tiene el "problema de la urna con el reemplazo y la secuencia". La complejidad de esto es N ^ n donde n es la cantidad de puntos que debe llenar con los operadores. (Esto se ve a menudo para pincodes donde cada puntos puede tener 10 valores). Por lo tanto, debido a que este problema es de mayor complejidad que el problema de "todas las combinaciones posibles", necesita múltiples bucles o llamadas recursivas.

Así que para responder a la pregunta, "¿cómo resolver esto?". Tienes que resolverlo con múltiples bucles o recursividad debido a la complejidad del problema subyacente.

Answer 8

Utilice un bucle triple:

for (int i=0; i < operators.length; ++i) {
    for (int j=0; j < operators.length; ++j) {
        for (int k=0; k < operators.length; ++k) {
            System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
                numbers[2] + operators[k] + numbers[3]);
        }
    }
}

Básicamente, debes tomar el producto cruzado del vector de operadores (si fuera un vector). En Java, esto se traduce en un conjunto de bucles anidados por triplicado.