Enfoque iterativo para imprimir todas las combinaciones de un Array

Dada una array arr[] de tamaño N , la tarea es generar e imprimir todas las combinaciones posibles de elementos R en la array.

Ejemplos:

Entrada: arr[] = {0, 1, 2, 3}, R = 3
Salida:
0 1 2
0 1 3
0 2 3
1 2 3

Entrada: arr[] = {1, 3, 4, 5, 6, 7}, R = 5
Salida:
1 3 4 5 6
1 3 4 5 7
1 3 4 6 7
1 3 5 6 7
1 4 5 6 7
3 4 5 6 7

Enfoque: Los métodos recursivos se discuten aquí . En esta publicación, se discutirá un método iterativo para generar todas las combinaciones para una array dada.
El método iterativo actúa como una máquina de estados. Cuando se llama a la máquina, emite una combinación y pasa a la siguiente.
Para una combinación de r elementos de una array de tamaño n , un elemento determinado puede incluirse o excluirse de la combinación.
Tengamos una array booleana de tamaño n para etiquetar si se incluye el elemento correspondiente en la array de datos. Si se incluye el i – ésimo elemento en la array de datos, entonces el i -ésimo elemento en la array booleana es verdadero o falso en caso contrario.
Después,r booleanos en la array booleana se etiquetarán como verdaderos. Podemos inicializar la array booleana para que tenga r verdaderos desde el índice 0 hasta el índice r – 1 . Durante la iteración, escaneamos la array booleana de izquierda a derecha y encontramos el primer elemento que es verdadero y el anterior es falso y el primer elemento que es verdadero y el siguiente es falso.
Entonces, tenemos el primer tramo continuo de valores verdaderos en la array booleana. Suponga que hay m verdaderos en este tracto, comenzando desde index Start y terminando en index End . La próxima iteración sería

1. Establezca el índice End + 1 de la array booleana en verdadero.
2. Establezca index Start en index End – 1 de la array booleana en false.
3. Establezca el índice 0 en el índice k – 2 en verdadero.

Por ejemplo ,
si la array booleana actual es {0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0} , entonces k = 4 , Start = 2 y End = 5 . La siguiente array booleana sería {1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0} . En el caso de Inicio == Fin donde solo hay un verdadero en el tracto, simplemente establecemos el índice Fin en falso y el índice Fin + 1 en verdadero.
También necesitamos registrar el inicio y el final actuales y actualizar el inicio y el final durante cada iteración. cuando la última rbooleanos se establecen en verdadero, no podemos pasar a la siguiente combinación y nos detenemos.

La siguiente imagen ilustra cómo cambia la array booleana de una iteración a otra.

Para generar la combinación, simplemente escaneamos la array booleana. Si su i -ésimo índice es verdadero, imprimimos el i -ésimo elemento de la array de datos.

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

// C++ implementation of the approach
#include <iostream>
using namespace std;
  
class Combination {
private:
    // Data array for combination
    int* Indices;
  
    // Length of the data array
    int N;
  
    // Number of elements in the combination
    int R;
  
    // The boolean array
    bool* Flags;
  
    // Starting index of the 1st tract of trues
    int Start;
  
    // Ending index of the 1st tract of trues
    int End;
  
public:
    // Constructor
    Combination(int* arr, int n, int r)
    {
        this->Indices = arr;
        this->N = n;
        this->R = r;
        this->Flags = nullptr;
    }
    ~Combination()
    {
        if (this->Flags != nullptr) {
            delete[] this->Flags;
        }
    }
  
    // Set the 1st r Booleans to true,
    // initialize Start and End
    void GetFirst()
    {
        this->Flags = new bool[N];
  
        // Generate the very first combination
        for (int i = 0; i < this->N; ++i) {
            if (i < this->R) {
                Flags[i] = true;
            }
            else {
                Flags[i] = false;
            }
        }
  
        // Update the starting ending indices
        // of trues in the boolean array
        this->Start = 0;
        this->End = this->R - 1;
        this->Output();
    }
  
    // Function that returns true if another
    // combination can still be generated
    bool HasNext()
    {
        return End < (this->N - 1);
    }
  
    // Function to generate the next combination
    void Next()
    {
  
        // Only one true in the tract
        if (this->Start == this->End) {
            this->Flags[this->End] = false;
            this->Flags[this->End + 1] = true;
            this->Start += 1;
            this->End += 1;
            while (this->End + 1 < this->N
                   && this->Flags[this->End + 1]) {
                ++this->End;
            }
        }
        else {
  
            // Move the End and reset the End
            if (this->Start == 0) {
                Flags[this->End] = false;
                Flags[this->End + 1] = true;
                this->End -= 1;
            }
            else {
                Flags[this->End + 1] = true;
  
                // Set all the values to false starting from
                // index Start and ending at index End
                // in the boolean array
                for (int i = this->Start; i <= this->End; ++i) {
                    Flags[i] = false;
                }
  
                // Set the beginning elements to true
                for (int i = 0; i < this->End - this->Start; ++i) {
                    Flags[i] = true;
                }
  
                // Reset the End
                this->End = this->End - this->Start - 1;
                this->Start = 0;
            }
        }
        this->Output();
    }
  
private:
    // Function to print the combination generated previouslt
    void Output()
    {
        for (int i = 0, count = 0; i < this->N
                                   && count < this->R;
             ++i) {
  
            // If current index is set to true in the boolean array
            // then element at current index in the original array
            // is part of the combination generated previously
            if (Flags[i]) {
                cout << Indices[i] << " ";
                ++count;
            }
        }
        cout << endl;
    }
};
  
// Driver code
int main()
{
    int arr[] = { 0, 1, 2, 3 };
    int n = sizeof(arr) / sizeof(int);
    int r = 3;
    Combination com(arr, n, r);
    com.GetFirst();
    while (com.HasNext()) {
        com.Next();
    }
    return 0;
}

// Java implementation of the approach
class Combination 
{
  
    // Data array for combination
    private int[] Indices;
  
    // Number of elements in the combination
    private int R;
  
    // The boolean array
    private boolean[] Flags;
  
    // Starting index of the 1st tract of trues
    private int Start;
  
    // Ending index of the 1st tract of trues
    private int End;
  
    // Constructor
    public Combination(int[] arr, int r)
    {
        this.Indices = arr;
        this.R = r;
    }
  
    // Set the 1st r Booleans to true,
    // initialize Start and End
    public void GetFirst()
    {
        Flags = new boolean[this.Indices.length];
  
        // Generate the very first combination
        for (int i = 0; i < this.R; ++i) 
        {
            Flags[i] = true;
        }
  
        // Update the starting ending indices
        // of trues in the boolean array
        this.Start = 0;
        this.End = this.R - 1;
        this.Output();
    }
  
    // Function that returns true if another
    // combination can still be generated
    public boolean HasNext()
    {
        return End < (this.Indices.length - 1);
    }
  
    // Function to generate the next combination
    public void Next()
    {
  
        // Only one true in the tract
        if (this.Start == this.End)
        {
            this.Flags[this.End] = false;
            this.Flags[this.End + 1] = true;
            this.Start += 1;
            this.End += 1;
            while (this.End + 1 < this.Indices.length
                && this.Flags[this.End + 1]) 
            {
                ++this.End;
            }
        }
        else 
        {
  
            // Move the End and reset the End
            if (this.Start == 0)
            {
                Flags[this.End] = false;
                Flags[this.End + 1] = true;
                this.End -= 1;
            }
            else 
            {
                Flags[this.End + 1] = true;
  
                // Set all the values to false starting from
                // index Start and ending at index End
                // in the boolean array
                for (int i = this.Start; i <= this.End; ++i)
                {
                    Flags[i] = false;
                }
  
                // Set the beginning elements to true
                for (int i = 0; i < this.End - this.Start; ++i) 
                {
                    Flags[i] = true;
                }
  
                // Reset the End
                this.End = this.End - this.Start - 1;
                this.Start = 0;
            }
        }
        this.Output();
    }
  
    // Function to print the combination generated previouslt
    private void Output()
    {
        for (int i = 0, count = 0; i < Indices.length
                                && count < this.R; ++i)
        {
  
            // If current index is set to true in the boolean array
            // then element at current index in the original array
            // is part of the combination generated previously
            if (Flags[i]) 
            {
                System.out.print(Indices[i]);
                System.out.print(" ");
                ++count;
            }
        }
        System.out.println();
    }
}
  
// Driver code
class GFG 
{
    public static void main(String[] args)
    {
        int[] arr = { 0, 1, 2, 3 };
        int r = 3;
        Combination com = new Combination(arr, r);
        com.GetFirst();
        while (com.HasNext())
        {
            com.Next();
        }
    }
}
  
// This code is contributed by Rajput-Ji

// C# implementation of the approach
using System;
namespace IterativeCombination {
class Combination {
  
    // Data array for combination
    private int[] Indices;
  
    // Number of elements in the combination
    private int R;
  
    // The boolean array
    private bool[] Flags;
  
    // Starting index of the 1st tract of trues
    private int Start;
  
    // Ending index of the 1st tract of trues
    private int End;
  
    // Constructor
    public Combination(int[] arr, int r)
    {
        this.Indices = arr;
        this.R = r;
    }
  
    // Set the 1st r Booleans to true,
    // initialize Start and End
    public void GetFirst()
    {
        Flags = new bool[this.Indices.Length];
  
        // Generate the very first combination
        for (int i = 0; i < this.R; ++i) {
            Flags[i] = true;
        }
  
        // Update the starting ending indices
        // of trues in the boolean array
        this.Start = 0;
        this.End = this.R - 1;
        this.Output();
    }
  
    // Function that returns true if another
    // combination can still be generated
    public bool HasNext()
    {
        return End < (this.Indices.Length - 1);
    }
  
    // Function to generate the next combination
    public void Next()
    {
  
        // Only one true in the tract
        if (this.Start == this.End) {
            this.Flags[this.End] = false;
            this.Flags[this.End + 1] = true;
            this.Start += 1;
            this.End += 1;
            while (this.End + 1 < this.Indices.Length
                   && this.Flags[this.End + 1]) {
                ++this.End;
            }
        }
        else {
  
            // Move the End and reset the End
            if (this.Start == 0) {
                Flags[this.End] = false;
                Flags[this.End + 1] = true;
                this.End -= 1;
            }
            else {
                Flags[this.End + 1] = true;
  
                // Set all the values to false starting from
                // index Start and ending at index End
                // in the boolean array
                for (int i = this.Start; i <= this.End; ++i) {
                    Flags[i] = false;
                }
  
                // Set the beginning elements to true
                for (int i = 0; i < this.End - this.Start; ++i) {
                    Flags[i] = true;
                }
  
                // Reset the End
                this.End = this.End - this.Start - 1;
                this.Start = 0;
            }
        }
        this.Output();
    }
  
    // Function to print the combination generated previouslt
    private void Output()
    {
        for (int i = 0, count = 0; i < Indices.Length
                                   && count < this.R;
             ++i) {
  
            // If current index is set to true in the boolean array
            // then element at current index in the original array
            // is part of the combination generated previously
            if (Flags[i]) {
                Console.Write(Indices[i]);
                Console.Write(" ");
                ++count;
            }
        }
        Console.WriteLine();
    }
}
  
// Driver code
class AppDriver {
    static void Main()
    {
        int[] arr = { 0, 1, 2, 3 };
        int r = 3;
        Combination com = new Combination(arr, r);
        com.GetFirst();
        while (com.HasNext()) {
            com.Next();
        }
    }
}
}

0 1 2 
0 1 3 
0 2 3 
1 2 3