C++ Code for Combination and Permutation of an array

Question

Good day everyone, I am quite new to C++ coding but I am taking courses on it.

I want to write a code that will find the combination of r elements of an array and then permutate the result.

I have been able to research from various sources and have separate codes that will print combination and permutation of the array.

The challenge I am facing is how to combine the two codes and make it work as one.

The first code is for the combination of the array of 5 elements in which 4 elements are to be selected at a time.

/*C++ program to print all combination  of size r in an array of size n*/ 
#include <iostream> 
using namespace std; 
 
void combinationUtil(string arr[], string data[], 
                    int start, int end, 
                    int index, int r); 
 
/*The main function that prints all combinations of size r in arr[] of
  size n. This function mainly uses combinationUtil()*/
void printCombination(string arr[], int n, int r) 
{ 
    /*A temporary array to store all combination one by one*/
    string data[r]; 

    /*Print all combination using temporary array 'data[]'*/
    combinationUtil(arr, data, 0, n-1, 0, r); 
} 
 
/*arr[] ---> Input Array 
  data[] ---> Temporary array to 
  store current combination 
  start & end ---> Starting and
  Ending indexes in arr[] 
  index ---> Current index in data[] 
  r ---> Size of a combination to be printed */
void combinationUtil(string arr[], string data[], 
                    int start, int end, 
                    int index, int r) 
{ 
   
    if (index == r) 
    { 
        for (int j = 0; j < r; j++) 
            cout << data[j] << " "; 
        cout << endl; 
        return; 
    } 
 
    /*replace index with all possible elements. The condition "end-i+1 >= r-index"
      makes sure that including one element at index will make a combination
      with remaining elements at remaining positions*/
    for (int i = start; i <= end && 
        end - i + 1 >= r - index; i++) 
    { 
        data[index] = arr[i]; 
        combinationUtil(arr, data, i+1, 
                        end, index+1, r); 
    } 
} 
 
// Driver code 
int main() 
{ 
    string arr[] = {"Red", "Orange", "Green", "Blue", "Indigo"}; 
    int r = 4; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printCombination(arr, n, r); 
} 

The second code is to permutate each of the results of the combination (previous code) of the array, which means permutation of 4 elements. In this code below, the permutation of the first-line of results from the first code was used.

#include <iostream>
#include <string>
using namespace std;

// Function to display the array
void display(string a[], int n)
{
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

// Function to find the permutations
void findPermutations(string a[], int n)
{
    // Sort the given array
    sort(a, a + n);

    // Find all possible permutations
    cout << "Possible permutations are:\n";
    do {
        display(a, n);
    } while (next_permutation(a, a + n));
}

// Driver code
int main()
{
    string a[] = { "Red", "Orange", "Green", "Blue"};
    int n = sizeof(a) / sizeof(a[0]);
    findPermutations(a, n);
    return 0;
}

In summary, a code that will find the combination of an array of words and the permutate each line of result of the combination is required.

Answer 1

You have 2 pieces of code, each of which prints some data. You want to connect them. One way to do that is to change one piece of code to store the data in some data structure, instead of printing. Then change the other piece of code to get this data structure, and work on its contents.

This brings up the idea of data structures. C++ has std::vector, which is an array with variable size. This is a very simple and most useful data structure in C++. The elements of a vector can have any specific type, including vector, which allows using nested lists (see below).

Change your printCombination function to return std::vector instead of void (also change its name appropriately):

std::vector<std::vector<std::string>>
findCombinations(std::vector<std::string> strings, int r)
{
    ...
}

I omitted the implementation, because I want to concentrate on interfaces in my answer.

Note that this function's return type is std::vector<std::vector<std::string>>. In general, std::vector<T> means "a list of items, each of which has type T". So the return type of this function is a list of combinations, where each combination is a list of strings. Also, I replaced an array of strings by std::vector<std::string>, which is a list of strings. It's functionally the same as an array, but slightly better, because it stores the length inside, and doesn't require a dedicated additional argument to your function.

Then change your findPermutations to receive its data using std::vector instead of array.

void findPermutations(std::vector<std::string> a)
{
   ...
}

(I omitted pass-by-reference for brevity)

Then make your "driver" function call the first function and pass its output to the second function:

// Driver code
int main()
{
    std::vector<std::string> arr{"Red", "Orange", "Green", "Blue", "Indigo"};
    int r = 4;
    auto combinations = findCombinations(arr, r);
    for (auto combination: combinations)
        findPermutations(combination);
}

(I omitted pass-by-reference in the for-loop for brevity)