Making an algorithm for listing all possible sequences

Question

I need some sort of idea on how I can use arrays to print all possible sequences. For example,

array 1: AA BB
array 2: CC
array 3: DD EE FF
array 4: GG

Now I need to list all possible combinations from any given arrays, using only 1 sequence per array, like so:

AA CC DD GG
AA CC EE GG
AA CC FF GG
BB CC DD GG
BB CC EE GG
BB CC FF GG

Does anyone know or can start me off on how to do this?

Answer 1

C++11 style!

#include <iostream>
#include <vector>
#include <utility>
#include <iterator>

// metaprogramming boilerplate:

template<typename... L>
struct first_type {};
template<typename T, typename... L>
struct first_type<T, L...> {
  typedef T type;
};
template<typename... L>
using FirstType = typename first_type<L...>::type;

namespace aux {
    using std::begin;
    template<typename C>
    auto adl_begin( C&&c )->decltype( begin(std::forward<C>(c)) );
    template<typename C>
    auto adl_cbegin( C const&c )->decltype( begin(c) );
}
template<typename Container>
struct iterator_type {
  typedef decltype( aux::adl_begin(std::declval<Container>()) ) iterator;
  typedef decltype( aux::adl_cbegin(std::declval<Container>()) ) const_iterator;
};
template<typename Container>
using IteratorType = typename iterator_type<Container>::iterator;

template<typename Container>
struct value_type {
  typedef typename std::iterator_traits< IteratorType<Container> >::value_type type;
};
template<typename Container>
using ValueType = typename value_type<Container>::type;

// Actual problem specific code:
template<typename Func, typename T>
void ForEachPossibility_Helper( Func&& f, std::vector<T>& result) {
  f(result);
}

template<typename Func, typename T, typename Container, typename... Containers>
void ForEachPossibility_Helper( Func&& f, std::vector<T>& result, Container&& arr0, Containers&&... arrays) {
  for( auto const& str:arr0 ) {
    result.push_back(str);
    ForEachPossibility_Helper( std::forward<Func>(f), result, std::forward<Containers>(arrays)... );
    result.pop_back();
  }
}

template<typename Func, typename... Containers>
void ForEachPossibility( Func&& f, Containers&&... arrays) {
    typedef ValueType<FirstType<Containers...>> T;
    std::vector<T> result;
    ForEachPossibility_Helper( std::forward<Func>(f), result, std::forward<Containers>(arrays)... );
}

const char* arr1[] = {"AA", "BB"};
const char* arr2[] = {"CC"};
const char* arr3[] = {"DD", "EE", "FF"};
const char* arr4[] = {"GG"};

int main() {
  ForEachPossibility( []( std::vector<const char*> const& result ){
    for( auto&& str:result ) {
      std::cout << str;
    }
    std::cout << "\n";
  }, arr1, arr2, arr3, arr4 );
}

Notice that there are only 2 for loops, and one of them is for printing.

Answer 2

EDITED FOR UPDATE

We need to instead of updating each indice by one, update by iterating over combinations...

See: How can I iterate throught every possible combination of n playing cards

So now it looks like this

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

bool UpdateCombination (std::vector<int> &comboindices, int count, int n)
{
    for (int i = 1; i <= n; ++i)
    {
        if (comboindices[n - i] < count - i)
        {
            ++comboindices[n - i];
            for (int j = n - i + 1; j < n; ++j)
            {
                comboindices[j] = comboindices[j-1] + 1;
            }
            return false;
        }
    }
    return true;
}

void ResetCombination (std::vector<int> &comboindices, int n)
{
    comboindices.resize(n);
    for (int i = 0; i < n; ++i)
    {
        comboindices[i] = i;
    }
}

void PrintArrays (const std::vector<std::vector<std::string>> items, int count)
{
    std::vector<std::vector<int>> indices;
    int n = items.size();
    indices.resize(items.size());

    for(auto i = indices.begin (); i != indices.end (); ++i)
    {
        ResetCombination((*i),count);
    }

    while (true) //Iterate until we've used all of the last array of items
    {
            for (int i = 0; i < n; ++i)
            {
                cout << "{";
                for (auto j = indices[i].begin (); j != indices[i].end (); ++j)
                {
                    int ji = (*j);
                    cout << (items[i])[ji] << " ";
                }
                cout << "} ";

            }
            cout << endl;

            //Update to the next indice
            for (int i = n - 1; i >= 0; --i)
            {
                    bool done = UpdateCombination (indices[i],items[i].size(),count);
                    if (!done)
                    {
                            break;
                    }
                    else if (done && i == 0)
                    {
                        return; //Escape.
                    }
                    else
                    {
                        ResetCombination(indices[i],count);
                    }
            }
    }

}
 //{A,B,C,D},{A,B},{A,B},{A,B,C,D,E,F},{A,B}


int main() {

    vector<vector<string>> lists;
    lists.resize(5);
    lists[0].push_back("A");
    lists[0].push_back("B");
    lists[0].push_back("C");
    lists[0].push_back("D");

    lists[1].push_back("A");
    lists[1].push_back("B");

    lists[2].push_back("A");
    lists[2].push_back("B");

    lists[3].push_back("A");
    lists[3].push_back("B");
    lists[3].push_back("C");
    lists[3].push_back("D");
    lists[3].push_back("E");
    lists[3].push_back("F");

    lists[4].push_back("A");
    lists[4].push_back("B");



    PrintArrays(lists,2);

    int pause;
    cin >> pause;
    return 0;
}

Giving us...

{A B } {A B } {A B } {A B } {A B } 
{A B } {A B } {A B } {A C } {A B } 
{A B } {A B } {A B } {A D } {A B } 
{A B } {A B } {A B } {A E } {A B } 
{A B } {A B } {A B } {A F } {A B } 
{A B } {A B } {A B } {B C } {A B } 
{A B } {A B } {A B } {B D } {A B } 
{A B } {A B } {A B } {B E } {A B } 
{A B } {A B } {A B } {B F } {A B } 
{A B } {A B } {A B } {C D } {A B } 
{A B } {A B } {A B } {C E } {A B } 
{A B } {A B } {A B } {C F } {A B } 
{A B } {A B } {A B } {D E } {A B } 
{A B } {A B } {A B } {D F } {A B } 
{A B } {A B } {A B } {E F } {A B } 
{A C } {A B } {A B } {A B } {A B } 
{A C } {A B } {A B } {A C } {A B } 
{A C } {A B } {A B } {A D } {A B } 
{A C } {A B } {A B } {A E } {A B } 
{A C } {A B } {A B } {A F } {A B } 
{A C } {A B } {A B } {B C } {A B } 
{A C } {A B } {A B } {B D } {A B } 
{A C } {A B } {A B } {B E } {A B } 
{A C } {A B } {A B } {B F } {A B } 
{A C } {A B } {A B } {C D } {A B } 
{A C } {A B } {A B } {C E } {A B } 
{A C } {A B } {A B } {C F } {A B } 
{A C } {A B } {A B } {D E } {A B } 
{A C } {A B } {A B } {D F } {A B } 
{A C } {A B } {A B } {E F } {A B } 
{A D } {A B } {A B } {A B } {A B } 
{A D } {A B } {A B } {A C } {A B } 
{A D } {A B } {A B } {A D } {A B } 
{A D } {A B } {A B } {A E } {A B } 
{A D } {A B } {A B } {A F } {A B } 
{A D } {A B } {A B } {B C } {A B } 
{A D } {A B } {A B } {B D } {A B } 
{A D } {A B } {A B } {B E } {A B } 
{A D } {A B } {A B } {B F } {A B } 
{A D } {A B } {A B } {C D } {A B } 
{A D } {A B } {A B } {C E } {A B } 
{A D } {A B } {A B } {C F } {A B } 
{A D } {A B } {A B } {D E } {A B } 
{A D } {A B } {A B } {D F } {A B } 
{A D } {A B } {A B } {E F } {A B } 
{B C } {A B } {A B } {A B } {A B } 
{B C } {A B } {A B } {A C } {A B } 
{B C } {A B } {A B } {A D } {A B } 
{B C } {A B } {A B } {A E } {A B } 
{B C } {A B } {A B } {A F } {A B } 
{B C } {A B } {A B } {B C } {A B } 
{B C } {A B } {A B } {B D } {A B } 
{B C } {A B } {A B } {B E } {A B } 
{B C } {A B } {A B } {B F } {A B } 
{B C } {A B } {A B } {C D } {A B } 
{B C } {A B } {A B } {C E } {A B } 
{B C } {A B } {A B } {C F } {A B } 
{B C } {A B } {A B } {D E } {A B } 
{B C } {A B } {A B } {D F } {A B } 
{B C } {A B } {A B } {E F } {A B } 
{B D } {A B } {A B } {A B } {A B } 
{B D } {A B } {A B } {A C } {A B } 
{B D } {A B } {A B } {A D } {A B } 
{B D } {A B } {A B } {A E } {A B } 
{B D } {A B } {A B } {A F } {A B } 
{B D } {A B } {A B } {B C } {A B } 
{B D } {A B } {A B } {B D } {A B } 
{B D } {A B } {A B } {B E } {A B } 
{B D } {A B } {A B } {B F } {A B } 
{B D } {A B } {A B } {C D } {A B } 
{B D } {A B } {A B } {C E } {A B } 
{B D } {A B } {A B } {C F } {A B } 
{B D } {A B } {A B } {D E } {A B } 
{B D } {A B } {A B } {D F } {A B } 
{B D } {A B } {A B } {E F } {A B } 
{C D } {A B } {A B } {A B } {A B } 
{C D } {A B } {A B } {A C } {A B } 
{C D } {A B } {A B } {A D } {A B } 
{C D } {A B } {A B } {A E } {A B } 
{C D } {A B } {A B } {A F } {A B } 
{C D } {A B } {A B } {B C } {A B } 
{C D } {A B } {A B } {B D } {A B } 
{C D } {A B } {A B } {B E } {A B } 
{C D } {A B } {A B } {B F } {A B } 
{C D } {A B } {A B } {C D } {A B } 
{C D } {A B } {A B } {C E } {A B } 
{C D } {A B } {A B } {C F } {A B } 
{C D } {A B } {A B } {D E } {A B } 
{C D } {A B } {A B } {D F } {A B } 
{C D } {A B } {A B } {E F } {A B }

Check out the output. http://ideone.com/L5AZVv

Old ideone link: http://ideone.com/58ARAZ

Answer 3

I assume you meant the amount of elements per array are unknown, for which I used sizeof(). And like others have mentioned, you just nest 5 for loops.

int main()
{
    //naming arrays a,b,c,d,e, change accordingly
    //this function prints the combinations of 1 char
    int aElements = sizeof(a) / sizeof(a[0]);
    int bElements = sizeof(b) / sizeof(b[0]);
    int cElements = sizeof(c) / sizeof(c[0]);
    int dElements = sizeof(d) / sizeof(d[0]);
    int eElements = sizeof(e) / sizeof(e[0]);
    for (int i = 0; i < aElements; i++){
        for (int j = 0; j < bElements; j++){
            for (int k = 0; k < cElements; k++){
                for (int l = 0; l < dElements; l++){
                    for (int m = 0; m < eElements; m++){
                        cout << a[i] << b[j] << c[k] << d[l] << e[m] << endl;
                    }
                }
            }
        }
    }
}

In order to find out the number of combinations you can either put a counter in the inner loop, or just divide the number of elements by the combination number (1 in this case) and multiplying all of them. E.G, in your example it would be (4 / 1) * (2 / 1) * (2 / 1) * (6 / 1) * (2 / 1) = 192 combinations. If you do combinations per 2 chars, in your second example it would be (4 / 2) * (2 / 2) * (2 / 2) * (6 / 2) * (2 / 2) = 6 combinations. The following function prints out combinations of 2.

int main()
    {
    //naming arrays a,b,c,d,e, change accordingly
    //this function prints the combinations of 2 chars
    int aElements = sizeof(a) / sizeof(a[0]);
    int bElements = sizeof(b) / sizeof(b[0]);
    int cElements = sizeof(c) / sizeof(c[0]);
    int dElements = sizeof(d) / sizeof(d[0]);
    int eElements = sizeof(e) / sizeof(e[0]);
    for (int i = 0; i < aElements - 1; i+=2){
        for (int j = 0; j < bElements - 1; j+=2){
            for (int k = 0; k < cElements - 1; k+=2){
                for (int l = 0; l < dElements - 1; l+=2){
                    for (int m = 0; m < eElements - 1; m+=2){
                        cout << a[i] << a[i+1] << b[j] << b[j+1] << c[k] << c[k+1]  << d[l] << d[l+1] << e[m] << e[m+1] << endl;
                        }
                    }
                }
            }
        }
}

All I did for the 2nd was increment counters by 2 rather than 1, subtract 1 from number of elements not to go out of bounds, and print 2 consecutive elements rather than 1. This will work for any number of char combinations.

Answer 4

Tocs' answer is correct, if you have a variable number of arrays. If you always have 4 arrays you can simply use 4 nested loops.

   for (unsigned int i1 = 0; i1 < a1.size(); ++i1)
        for (unsigned int i2 = 0; i2 < a2.size(); ++i2)
            for (unsigned int i3 = 0; i3 < a3.size(); ++i3)
                for (unsigned int i4 = 0; i4 < a4.size(); ++i4)
                    cout << a1[i1] << " " << a2[i2] << " " << a3[i3] << " " << a4[i4] << std::endl;

See here http://ideone.com/YcW84Q for complete code.

Answer 5

4 loops leads to N pow(4).

Split 4 arrays looping into 2.

for each(arr 1){
  for each(arr 2)
  insert into container 1.
}


for each(arr 3){
  for each(arr 4)
  insert into container 2.
}


for each(container 1){
  for each(container 2)
  insert into container3 (*iter 1 + *iter 2)
}

so complexity will be max 3NPow(2) which will be less than N pow(4)

Answer 6

another possibility would be to "count" the current combination (e.g. as in counting binary). Start with (0,0,0,0) and count to the maximum array-indices (1,0,2,0). In each step, start by adding 1 to the first index. If it is greater than the maximum index (here 1), set it to zero and proceed with the next index

result:

(0,0,0,0) --> AA CC DD GG

(1,0,0,0) --> BB CC DD GG

(0,0,1,0) --> AA CC EE GG

(1,0,1,0) --> BB CC EE GG

(0,0,2,0) --> AA CC FF GG

(1,0,2,0) --> BB CC FF GG

Answer 7

So far as I can see, you do not need to care about the order of the arrays you're getting sequences from. In this case recursion is indeed helpful. Looks somehow like that:

void printSequences(ListOfYourArrays list, int index) {
    if (list.size() > index) {
        array a = list.getElementAt(index);
        //Make a cycle that reads items from your array one by one
        while (...)
            System.out.print(item);
        //And now you need to print all combinations for the rest of arrays in you list
        printSequences(list, index + 1);
    } else
        System.out.println();
}

All you need to do is add your arays to the list and call a function

printSequences(list, 0);

Answer 8

If these are 4 different arrays I can not think of a better option then writing 4 nested cycles each iterating over one of the arrays. If You have a two dimensional array that holds all the arrays I would advice you to use recursion.