制定一个列出所有可能序列的算法

我需要关于如何使用数组来打印所有可能序列的想法。例如，制定一个列出所有可能序列的算法

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

有谁知道或关闭上启动我这个怎么做？

来源

2013-03-12 Foxic

注意：这是一个基本的C++类，所以我需要使用这个基本的方法，而不是向量或任何东西 – Foxic 2013-04-17 20:45:26

[几个向量的笛卡尔积]的副本（http://stackoverflow.com/questions/2405242/笛卡尔积的-几个矢量）。 – 2013-04-17 21:59:52

正如我所说的，我需要一个不使用向量的基本方法，所以这个问题不会帮助我 – Foxic 2013-04-18 02:21:58

我假设你的意思是每个数组元素的数量是未知的，我使用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，而不是1是增量计数器的组合，从要素数量减去1不要去出界，和而连续打印2种元素比1.这将适用于任何数量的字符组合。

来源

2013-04-17 07:15:20 xyz

谢谢，这回答了我所有的问题。我可以复制粘贴到我的代码？ – Foxic 2013-04-17 07:23:39

你不能复制和粘贴，我建议做两个独立的函数包含每个例子。我也建议看看它是如何工作的，并且写下你自己的功能，而不仅仅是复制。最后，我在编程方面相对较新，因此这可能不是一个理想的解决方案，而且您可能能够写得更好。 – xyz 2013-04-17 07:32:00

我打算使用这个例子，因为在我的C++类中，我们没有涉及向量或任何其他高级主题，只有基本到目前为止。这对我来说似乎非常理想，谢谢所有答案 – Foxic 2013-04-17 20:41:25

如果这些是4个不同的数组，我想不出更好的选择，然后编写4个嵌套循环，每个循环遍历一个数组。如果你有一个包含所有数组的二维数组，我会建议你使用递归。

来源

2013-03-12 07:16:22

就我所见，您不需要关心从中获取序列的数组的顺序。在这种情况下，递归确实有帮助。看起来在某种程度上这样的：

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

所有你需要做的就是你的一阳指添加到列表中，并调用一个函数

printSequences(list, 0);

来源

2013-03-12 07:30:34

这将打印'AA BB ...' – 2013-03-12 09:30:45

另一种可能性将是“计数”目前的组合（例如，在计数二进制）。从（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） - > AA CC FF GG

（1,0,2,0） - > BB CC FF GG

来源

2013-03-12 09:15:14 arez

4回路引出到N POW（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 POW（4）

来源

2013-03-12 13:04:37 umeshkvguptha

不复杂复杂性不会改变这样做.. !!对于firt循环它是NPow（2）第二个循环它是Npow（2），对于第三个循环它（M）Pow（2）在这里M = NPow（2）你说容器的大小是NPow（2）。。！所以它不会改变，最后它是NPow（4）..！ – MissingNumber 2013-04-17 07:11:14

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

来源

2013-03-12 14:54:00 Tocs

的TOC答案是正确的，如果你有一个可变数量的阵列。如果你总是有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了解完整的代码。

来源

2013-04-17 07:14:01 Henrik

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个，其中一个用于打印。

来源

2013-04-17 19:14:43 Yakk

[ideone]（http://ideone.com/geStvt）美丽！ C++：“我希望我是哈斯克尔。” – 2013-04-17 20:30:23

@interrminatelysequenced Bah，我刚刚注意到我错过了'std :: vector '数据类型的'decltype'推理（而不是我使用了'std :: vector < const char *>'。哦， – Yakk 2013-04-17 20:33:08

我们仍然没有在我的C++类中使用向量，所以很遗憾我不能使用它，谢谢 – Foxic 2013-04-17 20:40:03

制定一个列出所有可能序列的算法

回答

相关问题