Combinaciones de n arrays seleccionando un elemento de cada array

Dada una lista de arreglos, encuentre todas las combinaciones donde cada combinación contenga un elemento de cada arreglo dado.

Ejemplos:

Input : [ [1, 2], [3, 4] ]
Output : 1 3  
         1 4 
         2 3 
         2 4       

Input : [ [1], [2, 3, 4], [5] ]
Output : 1 2 5  
         1 3 5
         1 4 5           

Mantenemos una array de tamaño igual al número total de arrays. Esta array llamada índices nos ayuda a realizar un seguimiento del índice del elemento actual en cada una de las n arrays. Inicialmente, se inicializa con todos los 0 que indican que el índice actual en cada array es el del primer elemento. Seguimos imprimiendo las combinaciones hasta que no se encuentren nuevas combinaciones. Comenzando desde la array más a la derecha, verificamos si hay más elementos en esa array. En caso afirmativo, incrementamos la entrada de esa array en índices, es decir, pasamos al siguiente elemento de esa array. También hacemos que los índices actuales sean 0 en todas las arrays a la derecha de esta array. Seguimos moviéndonos hacia la izquierda para verificar todas las arrays hasta que se encuentre una de ellas. Si no se encuentran más arrays, nos detenemos allí.

Implementación:

// C++ program to find combinations from n
// arrays such that one element from each
// array is present
#include <bits/stdc++.h>
 
using namespace std;
 
// function to print combinations that contain
// one element from each of the given arrays
void print(vector<vector<int> >& arr)
{
    // number of arrays
    int n = arr.size();
 
    // to keep track of next element in each of
    // the n arrays
    int* indices = new int[n];
 
    // initialize with first element's index
    for (int i = 0; i < n; i++)
        indices[i] = 0;
 
    while (1) {
 
        // print current combination
        for (int i = 0; i < n; i++)
            cout << arr[i][indices[i]] << " ";
        cout << endl;
 
        // find the rightmost array that has more
        // elements left after the current element
        // in that array
        int next = n - 1;
        while (next >= 0 &&
              (indices[next] + 1 >= arr[next].size()))
            next--;
 
        // no such array is found so no more
        // combinations left
        if (next < 0)
            return;
 
        // if found move to next element in that
        // array
        indices[next]++;
 
        // for all arrays to the right of this
        // array current index again points to
        // first element
        for (int i = next + 1; i < n; i++)
            indices[i] = 0;
    }
}
 
// driver function to test above function
int main()
{
    // initializing a vector with 3 empty vectors
    vector<vector<int> > arr(3, vector<int>(0, 0));
 
    // now entering data
    // [[1, 2, 3], [4], [5, 6]]
    arr[0].push_back(1);
    arr[0].push_back(2);
    arr[0].push_back(3);
    arr[1].push_back(4);
    arr[2].push_back(5);
    arr[2].push_back(6);
 
    print(arr);
}

// Java program to find combinations from n
// arrays such that one element from each
// array is present
import java.util.*;
 
class GFG{
 
// Function to print combinations that contain
// one element from each of the given arrays
static void print(Vector<Integer> []arr)
{
     
    // Number of arrays
    int n = arr.length;
 
    // To keep track of next element in
    // each of the n arrays
    int []indices = new int[n];
 
    // Initialize with first element's index
    for(int i = 0; i < n; i++)
        indices[i] = 0;
 
    while (true)
    {
 
        // Print current combination
        for(int i = 0; i < n; i++)
            System.out.print(
                arr[i].get(indices[i]) + " ");
                 
        System.out.println();
 
        // Find the rightmost array that has more
        // elements left after the current element
        // in that array
        int next = n - 1;
        while (next >= 0 &&
              (indices[next] + 1 >=
                   arr[next].size()))
            next--;
 
        // No such array is found so no more
        // combinations left
        if (next < 0)
            return;
 
        // If found move to next element in that
        // array
        indices[next]++;
 
        // For all arrays to the right of this
        // array current index again points to
        // first element
        for(int i = next + 1; i < n; i++)
            indices[i] = 0;
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Initializing a vector with 3 empty vectors
    @SuppressWarnings("unchecked")
    Vector<Integer> []arr = new Vector[3];
    for(int i = 0; i < arr.length; i++)
        arr[i] = new Vector<Integer>();
         
    // Now entering data
    // [[1, 2, 3], [4], [5, 6]]
    arr[0].add(1);
    arr[0].add(2);
    arr[0].add(3);
    arr[1].add(4);
    arr[2].add(5);
    arr[2].add(6);
 
    print(arr);
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program to find combinations from n
# arrays such that one element from each
# array is present
 
# function to print combinations that contain
# one element from each of the given arrays
def print1(arr):
     
    # number of arrays
    n = len(arr)
 
    # to keep track of next element
    # in each of the n arrays
    indices = [0 for i in range(n)]
 
    while (1):
 
        # print current combination
        for i in range(n):
            print(arr[i][indices[i]], end = " ")
        print()
 
        # find the rightmost array that has more
        # elements left after the current element
        # in that array
        next = n - 1
        while (next >= 0 and
              (indices[next] + 1 >= len(arr[next]))):
            next-=1
 
        # no such array is found so no more
        # combinations left
        if (next < 0):
            return
 
        # if found move to next element in that
        # array
        indices[next] += 1
 
        # for all arrays to the right of this
        # array current index again points to
        # first element
        for i in range(next + 1, n):
            indices[i] = 0
 
# Driver Code
 
# initializing a vector with 3 empty vectors
arr = [[] for i in range(3)]
 
# now entering data
# [[1, 2, 3], [4], [5, 6]]
arr[0].append(1)
arr[0].append(2)
arr[0].append(3)
arr[1].append(4)
arr[2].append(5)
arr[2].append(6)
 
print1(arr)
 
# This code is contributed by mohit kumar

// C# program to find
// combinations from n
// arrays such that one
// element from each
// array is present
using System;
using System.Collections.Generic;
class GFG{
 
// Function to print combinations
// that contain one element from
// each of the given arrays
static void print(List<int> []arr)
{
  // Number of arrays
  int n = arr.Length;
 
  // To keep track of next
  // element in each of
  // the n arrays
  int []indices = new int[n];
 
  // Initialize with first
  // element's index
  for(int i = 0; i < n; i++)
    indices[i] = 0;
 
  while (true)
  {
    // Print current combination
    for(int i = 0; i < n; i++)
      Console.Write(arr[i][indices[i]] + " ");
     
    Console.WriteLine();
 
    // Find the rightmost array
    // that has more elements
    // left after the current
    // element in that array
    int next = n - 1;
    while (next >= 0 &&
          (indices[next] + 1 >=
           arr[next].Count))
      next--;
 
    // No such array is found
    // so no more combinations left
    if (next < 0)
      return;
 
    // If found move to next
    // element in that array
    indices[next]++;
 
    // For all arrays to the right
    // of this array current index
    // again points to first element
    for(int i = next + 1; i < n; i++)
      indices[i] = 0;
  }
}
 
// Driver code
public static void Main(String[] args)
{
  // Initializing a vector
  // with 3 empty vectors
  List<int> []arr = new List<int>[3];
  for(int i = 0; i < arr.Length; i++)
    arr[i] = new List<int>();
 
  // Now entering data
  // [[1, 2, 3], [4], [5, 6]]
  arr[0].Add(1);
  arr[0].Add(2);
  arr[0].Add(3);
  arr[1].Add(4);
  arr[2].Add(5);
  arr[2].Add(6);
 
  print(arr);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program to find combinations from n
// arrays such that one element from each
// array is present
 
// Function to print combinations that contain
// one element from each of the given arrays
function print(arr)
{
     
    // Number of arrays
    let n = arr.length;
     
    // To keep track of next element in
    // each of the n arrays
    let indices = new Array(n);
     
    // Initialize with first element's index
    for(let i = 0; i < n; i++)
        indices[i] = 0;
     
    while (true)
    {
     
        // Print current combination
        for(let i = 0; i < n; i++)
            document.write(
            arr[i][indices[i]] + " ");
          
        document.write("<br>");
         
        // Find the rightmost array that has more
        // elements left after the current element
        // in that array
        let next = n - 1;
        while (next >= 0 && (indices[next] + 1 >=
                                 arr[next].length))
            next--;
         
        // No such array is found so no more
        // combinations left
        if (next < 0)
            return;
         
        // If found move to next element in that
        // array
        indices[next]++;
         
        // For all arrays to the right of this
        // array current index again points to
        // first element
        for(let i = next + 1; i < n; i++)
            indices[i] = 0;
    }
}
 
// Driver code
 
// Initializing a vector with 3 empty vectors
let arr = new Array(3);
for(let i = 0; i < arr.length; i++)
    arr[i] = [];
 
// Now entering data
// [[1, 2, 3], [4], [5, 6]]
arr[0].push(1);
arr[0].push(2);
arr[0].push(3);
arr[1].push(4);
arr[2].push(5);
arr[2].push(6);
 
print(arr);
     
// This code is contributed by unknown2108
 
</script>

1 4 5 
1 4 6 
2 4 5 
2 4 6 
3 4 5 
3 4 6 

Este artículo es una contribución de aditi sharma 2 . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.