Divida una array A[] en subconjuntos que tengan la misma suma y tamaños iguales a los elementos de la array B[]

Dada una array A[] que consta de N enteros, la tarea es dividir la array A[] en subconjuntos que tengan la misma suma y una longitud igual a los elementos de la array B[] .

Ejemplos:

Entrada: A[] = {17, 13, 21, 20, 50, 29}, B[] = {2, 3, 1}
Salida:
21 29
17 13 20
50

Entrada: A[] = { 1, 2, 3, 4, 5, 6}, B[] = { 2, 2, 2}
Salida:
1 6
2 5
3 4

Enfoque: siga los pasos a continuación para resolver el problema:

  • Dado que el recuento de subconjuntos ya está dado, calcule la suma de cada subconjunto.
  • Recorra cada elemento de la array B[], encuentre cada combinación posible de longitud B[i] y verifique si la suma de la combinación es igual a la suma deseada o no.
  • Repita los pasos anteriores para cada elemento de array B[i] e imprima la respuesta final

A continuación se muestra la implementación del enfoque anterior:

Python

# Python Program to implement
# the above approach
from itertools import combinations
  
# Function to split elements of first
# array into subsets of size given as
# elements in the second array
def main(A, B):
  
    # Required sum of subsets
    req_sum = sum(A) // len(B)
  
    # Stores the subsets
    final = []
  
    # Iterate the array B[]
    for i in B:
  
        # Generate all possible
        # combination of length B[i]
        temp = list(combinations(A, i))
  
    # Iterate over all the combinations
        for j in temp:
  
            # If the sum is equal to the 
            # required sum of subsets
            if(sum(j) == req_sum):
  
                # Store the subset
                temp = list(j)
                final.append(temp)
  
                for k in temp:
  
                    # Removing the subset
                    # from the array
                    A.remove(k)
                break
  
    # Printing the final result
    print(final)
  
  
# Driver Code
if __name__ == '__main__':
    # Value of array A and B
    A = [1, 2, 3, 4, 5, 6]
    B = [2, 2, 2]
  
    # Function call
    main(A, B)
Producción:

[[1, 6], [2, 5], [3, 4]]

Complejidad de tiempo: O(N 3 )
Espacio auxiliar: O(2 maxm ), donde maxm es el elemento máximo en el arreglo B[]

Publicación traducida automáticamente

Artículo escrito por jatindscl015 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *