代码之家 › 专栏 › 技术社区 › Donotalo

通过重复从两个列表生成所有组合

combinations algorithm c++

Donotalo · 技术社区 · 7 年前

给出2个数据列表(列表 A &列表(amp;L) B )我需要一个算法来生成所有可能的组合 C 在每个组合中:

所有项目 一 必须在场,订购不重要(例如, abc 与 cba )
正好1个项目来自 乙 必须出现在每个项目之后 一
项目来自 乙 可以重复

实施例1

A = {a, b, c}
B = {1, 2}

回答:

a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

例2

A = {a, b}
B = {1, 2, 3}

回答:

a1b1
a1b2
a1b3
a2b1
a2b2
a2b3
a3b1
a3b2
a3b3

我可以使用什么算法来生成这个答案?谢谢。我看到了模式,但无法将其转换为代码。我将用C++编写代码,但是算法会为我工作。

关于这个话题,我查了下面的问题。但没有一个像我的问题。

How to find all combinations of sets of pairs -不允许在第二盘重复。

All combinations of pairs within one set -处理一组。

combinations between two lists? -不允许在第二盘重复。

Finding all possible value combinations between two arrays -不允许在第二盘重复。

An efficient method to generate all possible ways to pair up items in a data set -处理单个集合,不允许重复。

我不能想出一个最小的例子,因为我不知道算法。

4 回复 | 直到 7 年前

Scheff's Cat 7 年前

#include <iostream>
#include <list>
#include <vector>

typedef std::list<char> List1;
typedef std::list<int> List2;
typedef std::vector<List2::const_iterator> Counter;

std::ostream& operator << (std::ostream &out, const std::pair<List1&, Counter&> &pair)
{
  Counter::const_iterator iter = pair.second.begin();
  for (const List1::value_type value : pair.first) {
    out << value << **iter++;
  }
  return out;
}

bool count(const List2 &lst2, Counter &counter)
{
  for (size_t i = counter.size(); i--;) {
    if (++counter[i] != lst2.end()) return false;
    counter[i] = lst2.begin();
  }
  return true; // wrap-over
}

int main()
{
  List1 lst1 = { 'a', 'b', 'c' };
  List2 lst2 = { 1, 2 };
  // make/fill counter
  std::vector<List2::const_iterator> counter(lst1.size(), lst2.begin());
  do {
    std::cout << std::pair<List1&, Counter&>(lst1, counter) << '\n';
  } while (!count(lst2, counter));
  // done
  return 0;
}

a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Live Demo on coliru

trip meter

JHBonarius 7 年前

#include <vector>
#include <iostream>
#include <string>

using charVec = std::vector<char>;
using intVec = std::vector<int>;

void printEl(const std::string& start, charVec::const_iterator it, const charVec::const_iterator& endIt, const intVec& iV)
{
    if (it == endIt)
    {
        std::cout << start << "\n";
        return;
    }
    for (const auto& iVel : iV)
    {
        printEl(start + *it + std::to_string(iVel), it + 1, endIt, iV);
    }
}

void printComb(const charVec& cV, const intVec& iV)
{
    printEl("", cV.cbegin(), cV.cend(), iV);
}

int main()
{
    charVec A1{ 'a', 'b', 'c' };
    intVec B1{ 1, 2 };

    printComb(A1, B1);

    std::cout << "next example: \n";

    charVec A2{ 'a', 'b' };
    intVec B2{ 1, 2, 3 };

    printComb(A2, B2);
}

live example

Joseph Wood 7 年前

B

A

template <typename typeVec1, typename typeVec2>
void customPerms(typeVec1 a, typeVec2 b) {

    int r = a.size(), n = b.size();
    int r1 = r - 1, n1 = n - 1;
    std::vector<int> z(r, 0);
    int numRows = (int) std::pow(n, r);

    for (int i = 0; i < numRows; ++i) {
        for (int j = 0; j < r; ++j)
            std::cout << a[j] << b[z[j]];
        std::cout << std::endl;

        for (int k = r1; k >= 0; --k) {
            if (z[k] != n1) {
                ++z[k];
                break;
            } else {
                z[k] = 0;
            }
        }
    }
}

#include <iostream>
#include <cmath>
#include <vector>

int main() {
    std::cout << "Example 1 : " << std::endl;
    std::vector<std::string> a1 = {"a", "b", "c"};
    std::vector<int> b1 = {1, 2};
    customPerms(a1, b1);

    std::cout << "\nExample 2 : " << std::endl;
    std::vector<char> a2 = {'a', 'b'};
    std::vector<int> b2 = {1, 2, 3};
    customPerms(a2, b2);
    return 0;
}

Example 1 : 
a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Example 2 : 
a1b1
a1b2
a1b3
a2b1
a2b2
a2b3
a3b1
a3b2
a3b3

https://ideone.com/OUv49P

Samer Tufail 7 年前

void permute_helper(vector<string>& A, vector<string>& B, int ii, string curr)
{
    if(ii == A.size())
    {
        cout << curr << endl;
        return;
    }

    for(int i = 0; i < B.size(); ++i) permute_helper(A, B, ii + 1, curr + A[ii] + B[i]);
}

void permute(vector<string>& A, vector<string>& B)
{
    permute_helper(A,B,0,"");
}

int main() {
    vector<string> A = {"a","b","c"};
    vector<string> B = {"1","2"};
    permute(A,B);
    return 0;
}