2013-03-12 2 views
1

Мне нужна какая-то идея о том, как я могу использовать массивы для печати всех возможных последовательностей. Например,Создание алгоритма для перечисления всех возможных последовательностей

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

Теперь мне нужно перечислить все возможные комбинации из любых заданных массивов, используя только 1 последовательность каждого массива, например:

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

Кто-нибудь знает или может начать меня на как это сделать?

+0

ПРИМЕЧАНИЕ: это базовый класс C++, поэтому мне нужно использовать базовый метод для этого, а не векторы или что-либо. – Foxic

+0

Дубликат [Декартово произведение нескольких векторов] (http://stackoverflow.com/questions/2405242/ декартово-продукт-оф-несколько векторов). –

+0

Как я уже сказал, мне нужен базовый метод, не использующий векторы, так что вопрос мне не помогает – Foxic

ответ

2

Я предполагаю, что вы имели в виду, что количество элементов в массиве неизвестно, для которых я использовал sizeof(). И, как и многие другие, вы только гнездились 5 для петель.

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

Для того, чтобы выяснить количество комбинаций вы можете поставить счетчик во внутреннем цикле, или просто разделить количество элементов комбинации числа (1, в данном случае) и умножая их всех. E.G, в вашем примере это будет (4/1) * (2/1) * (2/1) * (6/1) * (2/1) = 192 комбинаций. Если вы делаете комбинации на 2 символа, во втором примере это будет (4/2) * (2/2) * (2/2) * (6/2) * (2/2) = 6 комбинаций. Следующая функция выводит комбинации 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; 
         } 
        } 
       } 
      } 
     } 
} 

Все, что я сделал для 2-го было счетчики увеличиваются на 2, а не 1, вычесть 1 из числа элементов, которые не выходят за пределы, и печать 2 последовательных элементов, а чем 1. Это будет работать для любого количества комбинаций символов.

+0

Спасибо, это отвечает на все мои проблемы. Могу ли я просто скопировать это в свой код? – Foxic

+2

Вы не можете копировать и вставлять как есть, я бы посоветовал сделать две отдельные функции, содержащие каждый пример. Я также рекомендую посмотреть, как это работает, и написать свою собственную функцию, а не просто копировать. И, наконец, я относительно новичок в программировании, поэтому это может быть не идеальное решение, и вы могли бы написать что-то лучше. – xyz

+0

Я собираюсь использовать этот пример, потому что в моем классе C++ мы не переходили векторы или любые другие расширенные темы, а только основы.Это кажется для меня идеальным, спасибо за все ответы, хотя – Foxic

2

Если это 4 разных массива, я не могу придумать лучший вариант, а затем записать 4 вложенных цикла, каждый из которых будет итерации по одному из массивов. Если у вас есть двумерный массив, содержащий все массивы, я бы посоветовал вам использовать рекурсию.

1

Насколько я вижу, вам не нужно заботиться о порядке массивов, из которых вы получаете последовательности. В этом случае рекурсия действительно полезна. Выглядит как-то так:

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

Все, что вам нужно сделать, это добавить свои Arays в список и вызвать функцию

printSequences(list, 0); 
+0

это напечатает 'AA BB ...' –

0

другая возможность будет «считать» текущую комбинацию (например, как в подсчет двоичных данных). Начните с (0,0,0,0) и сосчитайте до максимального массива-индексов (1,0,2,0). На каждом шаге начинайте с добавления 1 к первому индексу. Если он больше, чем максимальный индекс (здесь 1), установите его равным нулю и перейти к следующему индексу

результат:

(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) -> АА СС Ф. Г.

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

0

4 контура приводит к N мощн (4).

Split 4 массивы зацикливания в 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) 
} 

так сложность будет не более 3NPow (2), который будет меньше, чем N мощн (4)

+2

nope сложность не изменится делая так .. !! для петли firt это NPow (2) второй цикл, это Npow (2), а для третьего цикла это (M) Pow (2) здесь M = NPow (2) Являются ли размеры контейнеров, которые вы говорите, NPow (2). . !! Так что это не изменится, и, наконец, это NPow (4) ..! – MissingNumber

1

EDITED FOR UPDATE

Нам нужно вместо обновления каждого индекса на единицу, обновить путем итерации по комбинациям ...

См.: How can I iterate throught every possible combination of n playing cards

Так что теперь он выглядит так

#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; 
} 

Давать нам ...

{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 } 

Проверьте выход. http://ideone.com/L5AZVv

Старый ideone ссылка: ответ http://ideone.com/58ARAZ

1

КТВ является правильным, если у вас есть переменное число массивов. Если у вас всегда есть 4 массива, вы можете просто использовать 4 вложенных цикла.

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; 

См. Здесь http://ideone.com/YcW84Q для полного кода.

2

C++ 11 стиль!

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

Обратите внимание, что для петель всего 2, и один из них предназначен для печати.

+1

[ideone] (http://ideone.com/geStvt) Красиво! C++: «Хотелось бы, чтобы я был Хаскелом». –

+0

@interrminatelysequenced Bah, я просто заметил, что у меня отсутствует вывод 'decltype' для' std :: vector 'тип данных (вместо этого я использовал' std :: vector < const char *> '. Ну хорошо. – Yakk

+0

Мы по-прежнему не переходили через векторы в моем классе C++, поэтому, к сожалению, я не могу использовать это, спасибо вам – Foxic

Смежные вопросы