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?

NOTE: this is for a basic c++ class so I need to use a basic method for this, not vectors or anything — Seb, Apr 17 '13 at 20:45
Duplicate of [Cartesian product of several vectors](http://stackoverflow.com/questions/2405242/cartesian-product-of-several-vectors). — Raymond Chen, Apr 17 '13 at 21:59
As I said, I need a basic method NOT using vectors, so that question doesn't help me — Seb, Apr 18 '13 at 02:21
Converting to a non-vector solution is trivial. Instead of an iterator, use an index. The algorithm is the same. Also, you asked for "some sort of idea" and that other solution is a perfectly good idea. The constraint that you cannot use a vector is artificial and not practical. Also, make sure to say in your assignment that you got the answer from StackOverflow, in conformance with the SO license (attribution required) as well as academic honesty rules. — Raymond Chen, Apr 18 '13 at 04:20

score 2 · Answer 1 · answered Mar 12 '13 at 07:16

2

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.

answered Mar 12 '13 at 07:16

Ivaylo Strandjev

69,226
18
123
176

score 2 · Accepted Answer · answered Apr 17 '13 at 07:15

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.

Thanks, this answers all my problems. Can I just copy paste this into my code? — Seb, Apr 17 '13 at 07:23
You can't copy and paste as is, I'd advise to make 2 separate functions containing each example. I also recommend seeing how this works and writing your own function rather than just copying. And conclusively, I'm relatively new at programming so this may not be an ideal solution, and you might be able to write something better. — xyz, Apr 17 '13 at 07:32
I'm going to use this example because in my c++ class we didn't go over vectors or any other advanced topics, only basics so far. This seems pretty ideal for me, thanks for all the answers though — Seb, Apr 17 '13 at 20:41
Ah no wonder, honestly I was a little surprised that you chose my answer — xyz, Apr 17 '13 at 23:49

Yakk - Adam Nevraumont · Answer 3 · 2013-04-18T02:42:51.827

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.

@interrminatelysequenced Bah, I just noticed I'm missing a `decltype` deduction for the `std::vector` data type (instead I used `std::vector< const char* >`. Oh well. — Yakk - Adam Nevraumont, Apr 17 '13 at 20:33
We still didn't go over vectors in my c++ class, so unfortunately I can't use this, thank you though — Seb, Apr 17 '13 at 20:40
@Yakk nitpick: You probably shouldn't name those variables `stack` and `list` even if there is no ambiguity here. — indeterminately sequenced, Apr 17 '13 at 20:52
@indeterminatelysequenced Yes, there was. It now works with any container type as a bonus (not just containers of `const char*`). Sadly this required writing a small metaprogramming library. — Yakk - Adam Nevraumont, Apr 18 '13 at 02:44
@Foxic there are many many reasons why you wouldn't want to submit this as an answer to your problem in a class before you covered `std::vector`. :) — Yakk - Adam Nevraumont, Apr 18 '13 at 02:45

score 1 · Answer 4 · answered Mar 12 '13 at 07:30

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);

this will print `AA BB ...` – Karoly Horvath Mar 12 '13 at 09:30 — Karoly Horvath, Mar 12 '13 at 09:30

score 1 · Answer 5 · edited May 23 '17 at 10:32

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

score 1 · Answer 6 · answered Apr 17 '13 at 07:14

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.

score 0 · Answer 7 · edited Jun 20 '20 at 09:12

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

score 0 · Answer 8 · edited Mar 12 '13 at 13:27

0

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)

edited Mar 12 '13 at 13:27

Barnee

3,212
8
41
53

answered Mar 12 '13 at 13:04

umeshkvguptha

1

2

nope complexity wont change doing so ..!! for the firt loop it is NPow(2) second loop it is Npow(2) and for the third loop it (M)Pow(2) here M= NPow(2) Are size of containers you say is NPow(2)..!! So it wont change and finally it is NPow(4)..! – MissingNumber Apr 17 '13 at 07:11

Making an algorithm for listing all possible sequences

8 Answers8