动态迭代编程来生成组合 [英] dynamic iterative programming to generate combinations
问题描述
使用我自己的程序版本更新：
我正在尝试一个迭代动态编程来生成 n选择k 组合。
说我有4个向量向量
v1：1 1 1
v2：2 2 2
v3：3 3 3
v4：4 4 4
现在我使用加法作为我的聚合函数，我想生成 4选择2 向量组合如下：
v1v2：3 3 3
v1v3：4 4 4
v1v4：5 5 5
v2v3：5 5 5
v2v4：6 6 6
v3v4：7 7 7
一个天真的方法这样做是通过每一对，找到结果。如果 N 和 k 非常大，这是非常非常低效的。所以一个替代方法就是递归/迭代动态规划。对于非常大的N和k的递归将占用很多内存，所以理想的方式是迭代动态规划，可以如下进行：
考虑以下内容表行标题是 N ，列标题是 k ，我们的目标是找到 N选择k ：
我们可以通过以下方式使用动态程序找到 N选择k 组合：
方法如下：
- 块[0,1]和块[0,2]总是返回[]。 {[]表示一个空值，因为没有值}
- 块[1,1]接收[]，计算{v1} + []（这是v1本身）将其保存到Block [1,1]。
- 阻止[1,2]收到[]，{v1} + []& {v2} + []，将其保存到Block [1,2]。
- 阻止[1,3]收到[]，{v1} + []，{v2} [] + {v3} U []，块[1,3]。
- 阻止[2,4]收到：
- $ b $来自[1,1]的b
- [{v1}]，并从[1,2]中计算{v1} + {v2}，
- [{v1} {v2}]并从[1,3]中计算{v1} + {v3}和{v2} + {v3}
- [{v1}，{v2}，{v3}]， v4} + {v1}，{v4} + {v2}和{v4} + {v3}将其保存到Block [2,4]。
现在我们在Block [2,4]中有了我们需要的所有值。我如何在C ++中高效地编写这个概念？
任何帮助都非常感谢。谢谢。
这是我的想法：
我不知道这是否正确。对不起
============================== =====================
// Block [0 ... k]的[0 ... n]的;
//块[i] [j]包含i-set组（例如：如果i = 2，它将具有v1v2，v1v3等）
//最初，块[0] [i] = [] for 0 <= i <= n，所有其他Block [i] [j] = [$]
//$只是一个符号，表示没有在该块上进行计算
算法（int k，int n）// n点数的k点天际线组。
{
if（Block [k] [n]！= [$]）return memory [k] [n];
Group = []; // G表示矢量的集合
for（int i = k; i <= n; i ++）
{
Group` = algorithm（k-1，i-1）;
（组中的每个v`）
{
Group = Group +（group` + v_i）;
}
}
内存[k] [n] =组;
返回组;
}
============== $ / $ $ $ $ $ $ $
这是我上述算法的程序：
#include< iostream>
#include< iterator>
#include< set>
#include< vector>
#include< map>
#define DIMENSIONS 5 //矢量中的元素数量。例如。 v1：1 1 1 1 1
using namespace std;
typedef std :: set< int> my_set; //保持向量id的
typedef std :: vector< int> my_vector; //保存向量的
typedef std :: vector< std :: pair my_set，my_vector> > my_vector_pair;
typedef std :: map< my_set，my_vector> my_map;
typedef std :: vector<载体std :: pair int，my_map> > > my_pair;
typedef my_map :: iterator m_it;
my_vector_pair基地//保存所有初始< id，vector_values>对
my_map数据，G;
my_pair memory;
void print（my_map& data）
{
for（m_it it（data.begin（））; it！= data.end（）; ++ it）
{
cout<< ID ： ;
copy（it-> first.begin（），it-> first.end（），ostream_iterator< int>（cout，））;
cout<<< => value：;
copy（it-> second.begin（），it-> second.end（），ostream_iterator< int>（cout，））;
cout<<< ENDL;
}
cout<<< ------------------------------------------------- -------------- \\\
;
}
my_map union_（my_map& G，int p）
{
static my_map result;
my_set id;
my_vector得分;
result.clear（）;
for（m_it it（G.begin（））; it！= G.end（）; ++ it）
{
id = it-> first;
scores = it-> second;
id.insert（bases.at（p-1）.first.begin（），bases.at（p-1）.first.end（））;
for（int j = 0; j< DIMENSIONS; j ++）
{
scores.at（j）+ = bases.at（p - 1）.second。在（J）;
}
result.insert（make_pair（id，scores））;
}
返回结果;
}
my_map algorithm_（int k，int n）{
unsigned long size = memory.at（n）.size（）;
（unsigned long i = 0; i< size; i ++）{
if（memory.at（n）.at（i）.first == k）{
return memory .AT（N）。在（ⅰ）。第二; //如果存在于哈希表中，则不需要再次计算
}
}
my_map G_k_1;
if（k！= n）
{
G_k_1 = algorithm_（k，n - 1）;
if（G_k_1.size（）== 0）
{
return G_k_1;
}
}
G_k_1 = algorithm_（k-1，n-1）;
if（G_k_1.size（）== 0）
{
return G_k_1;
}
G_k_1 = union_（G_k_1，n）;
if（k！= n）{
for（unsigned long i = 0; i
G_k_1.insert（memory.at（n - 1）.at（i）.second.begin（） ，memory.at（n-1）.at（i）.second.end（））;
memory.at（n - 1）.at（i）.second.clear（）;
break;
}
}
}
std :: pair< int，my_map>温度;
temp.first = k;
temp.second = G_k_1;
memory.at（n）.push_back（temp）; //存储在哈希表中进一步使用
return memory.at（n）.back（）。second;
}
int main（）
{
my_vector v1，v2，v3，v4，v5;
my_set s1，s2，s3，s4，s5; （int i = 1; i< = 5; ++ i）
{
v1.push_back（1）;
v2.push_back（2）;
v3.push_back（3）;
v4.push_back（4）;
v5.push_back（5）;
}
s1.insert（1）;
s2.insert（2）;
s3.insert（3）;
s4.insert（4）;
s5.insert（5）;
bases.insert（bases.end（），make_pair（s1，v1））;
bases.insert（bases.end（），make_pair（s2，v2））;
bases.insert（bases.end（），make_pair（s3，v3））;
bases.insert（bases.end（），make_pair（s4，v4））;
bases.insert（bases.end（），make_pair（s5，v5））;
my_set empty_set;
my_vector empty_group（DIMENSIONS）;
G.insert（make_pair（empty_set，empty_group））;
vector< std :: pair< int，my_map> > empty_element;
empty_element.push_back（make_pair（0，G））; （int i = 0; i< = 5; i ++）{// 5是总数量向量：v1，v2，v3，v4，v5
memory.push_back（empty_element）;
}
data.insert（bases.begin（），bases.end（））;
cout<<< endl< 初始向量集合是：< ENDL;
打印（数据）;
int k;
cout<<< N = 5< endl< 输入值k：;
cin>> K表;
cout<<< N选择k的值是：< ENDL;
data = algorithm_（k，5）;
打印（数据）;
}
如果你运行该程序，你知道我想要实现的并以什么方式。这个算法（而不是程序）对于较少数量的向量可能不是有效的，但是当N> 50k和k〜10时，这个算法（我的程序）的实现是非常低效的。有什么办法可以改进吗？我认为相同的算法可以以更优雅的方式实现。任何帮助深表感谢。谢谢。
我以前对您的答案误解了我的歉意，我真的不明白您在发帖中想要做什么我以为你只是在寻找非递归的计算方式nCk：P
我创建了一个类， CombinationGenerator 来生成矢量的组合，我相信是你想要的。它通过生成一个代表要聚合的元素的索引的int的向量（我已经包括一个 main 函数），它应该有助于以编程方式解释它）。 >
这是头文件： http://pastebin.com/F5x4WKD9
源文件： http://pastebin.com / CTV1PLRb
这里是一个示例主要功能：
typedef std :: vector< int> vecInt;
int main（）{
//我们有一个包含3个元素的deque（尝试使用实验数据
//类型来测试空间复杂性，std： ：set或std :: unordered_set可能是一个选项）
vecInt vec1; （int i = 0; i <3; i ++）
{
vec1.push_back（1）;
}
vecInt vec2; （int i = 0; i< 3; i ++）
{
vec2.push_back（2）;
}
vecInt vec3; （int i = 0; i <3; i ++）
{
vec3.push_back（3）;
}
vecInt vec4; （int i = 0; i <3; i ++）
{
vec4.push_back（4）;
}
vecInt vec5; （int i = 0; i< 3; i ++）
{
vec5.push_back（5）;
}
std :: deque< std :: vector< int>> dequeVecs;
dequeVecs.push_back（vec1）;
dequeVecs.push_back（vec2）;
dequeVecs.push_back（vec3）;
dequeVecs.push_back（vec4）;
dequeVecs.push_back（vec5）;
//创建我们的CombinationGenerator：
CombinationGenerator * gen = new CombinationGenerator（）;
g_pCombinationGen = gen;
gen = NULL;
unsigned long long size = g_pCombinationGen-> ComputeBinomialCoefficient（dequeVecs.size（），2）;
std :: vector< int> currCombination;
g_pCombinationGen-> Initialize（dequeVecs.size（），2，size）;
while（！g_pCombinationGen-> IsFinished（））
{
currCombination = g_pCombinationGen-> NextCombination（）;
std :: vector< int>结果; （int i = 0; i< dequeVecs [0] .size（）; i ++）
{
result.push_back（dequeVecs [currCombination [0]] [i] + dequeVecs [currCombination [1]] [i]）;
}
std :: cout<<< （;
for（int i = 0; i< result.size（）; i ++）
{
std :: cout< result [i];
}
std :: cout<<）<<的std :: ENDL;
}
返回0;
}
虽然这可能看起来相当大，如果您分析空间使用它（假设你使用n = 50,000和k = 1000：
有50,000个矢量，每个包含3个int（让我们假设一个相当苛刻的开销矢量32字节，大多数实现通常约为20）：所以，$ code>（50,000 * 3 * 4）+（50,000 * 32）= 2,200,000字节
然后，您将在一个deque中包含这个，我们也假设有一个32bytes的开销： 2,200,000 + 32 = 2,200,032 Bytes / p>
我们还有一个运行组合生成器的实例，它有5个成员变量，两个int，两个long longs和一个包含k ints的向量（在这种情况下1000），所以： 2,200,032 +（2 * 4）+（2 * 8）+（1000 * 4）+32 = 2,204,056字节
我们还使用k ints再次包含每次迭代的结果向量： 2,204,056 +（1000 * 4）+ 32 = 2,208,088字节
如你所见，这远远低于你的4GB内存。注意：无论您使用什么实现，都不可能将这些向量存储在内存中，因为将包含结果的 9.94 x 10 ^ 2126 向量。即使你选择了一个小的值，例如10，你仍然会超过 2.69 x 10 ^ 40 。
<我希望这一次我明白你要问的是什么！如果没有，我会再次尝试了解你想要实现的目标。 ：）
Updated with my own version of the program :
I'm trying to do an iterative dynamic programming to generate n choose k combination.
Say I've 4 vectors of values
v1 : 1 1 1
v2 : 2 2 2
v3 : 3 3 3
v4 : 4 4 4
Now I use addition as my aggregate function and I want to generate 4 choose 2 combinations of vectors as follows :
v1v2 : 3 3 3
v1v3 : 4 4 4
v1v4 : 5 5 5
v2v3 : 5 5 5
v2v4 : 6 6 6
v3v4 : 7 7 7
A naive way to do this would be to go through every pair and find the result. if the N and k are very large this is very very inefficient. So an alternative way to this would be recursive/iterative dynamic programming. Recursion for very large N and k would take up a lot of memory so the ideal way to this would be iterative dynamic programming which can be done as follows :
Consider the following table row header is N and the column header is k and our objective is to find N choose k :
We can find N choose k combination using dynamic program by following way :
The approach is as follows :
- Block[0,1] and Block[0,2] always returns [ ]. {[ ] denotes an empty value as there are no values there}.
- Block[1,1] receives [ ], computes {v1} + [ ] (which is v1 itself) , saves it to Block [1,1].
- Block[1,2] receives [ ], does {v1} + [ ] & {v2} + [ ], saves it to Block [1,2].
- Block[1,3] receives [ ], does {v1} + [ ], {v2} + [ ] + {v3} U [ ], Block [1,3].
- Block[2,4] receives :
- [{v1}] from [1,1] and computes {v1} + {v2},
- [{v1}{v2}] from [1,2] and computes {v1} + {v3} and {v2} + {v3}
- [{v1}, {v2}, {v3}] from [1,3] and computes {v4} + {v1}, {v4} + {v2} and {v4} + {v3}, saves it to Block [2,4].
Now we have all the values we need in Block [2,4]. how can i code this concept efficiently in C++ ?
Any help is greatly appreciated. Thanks.
Here is my idea :
I don't know if this is right. Sorry
=========================================================
//Block [0...k][0...n];
//Block[i][j] contains i-set groups (for eg :if i = 2 it will have v1v2, v1v3, etc..)
//initially, Block[0][i] = [ ] for 0 <= i <= n and all other Block [i][j] = [ $ ]
// "$" is just a symbol to indicate that no computation is done on that block
algorithm(int k, int n) //k-point skyline groups from n number of points.
{
if( Block[k][n] != [ $ ] ) return memory[k][n];
Group = [ ]; //G indicate a collection of vectors
for( int i = k; i <= n; i++ )
{
Group` = algorithm(k-1, i-1);
for( each v` in Group` )
{
Group = Group + (group` + v_i);
}
}
memory[k][n] = Group;
return Group;
}
=========================================================
Here is my program for the above mentioned algorithm :
#include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <map>
#define DIMENSIONS 5 // No. of elements in the vector. eg. v1: 1 1 1 1 1
using namespace std;
typedef std::set < int > my_set; // To hold vector id's
typedef std::vector < int > my_vector; // To hold values of the vector's
typedef std::vector < std::pair < my_set, my_vector > > my_vector_pair;
typedef std::map < my_set, my_vector > my_map;
typedef std::vector < vector < std::pair < int,my_map > > > my_pair;
typedef my_map::iterator m_it;
my_vector_pair bases; // To hold all the initial <id,vector_values> pair
my_map data, G;
my_pair memory;
void print(my_map& data)
{
for( m_it it(data.begin()) ; it!=data.end(); ++it)
{
cout << "Id : ";
copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
cout << " => value : ";
copy (it->second.begin(),it->second.end(),ostream_iterator<int>(cout," "));
cout << endl;
}
cout << "---------------------------------------------------------------\n";
}
my_map union_(my_map& G, int p)
{
static my_map result;
my_set id;
my_vector scores;
result.clear();
for (m_it it(G.begin()); it != G.end(); ++it)
{
id = it->first;
scores = it->second;
id.insert( bases.at(p-1).first.begin(),bases.at(p-1).first.end() );
for (int j = 0; j < DIMENSIONS; j++)
{
scores.at(j) += bases.at(p - 1).second.at(j);
}
result.insert(make_pair(id, scores));
}
return result;
}
my_map algorithm_(int k, int n) {
unsigned long size = memory.at(n).size();
for (unsigned long i = 0; i < size; i++) {
if (memory.at(n).at(i).first == k) {
return memory.at(n).at(i).second; //if exists in hash table then no need to calculate again
}
}
my_map G_k_1;
if (k != n)
{
G_k_1 = algorithm_(k, n - 1);
if(G_k_1.size() == 0)
{
return G_k_1;
}
}
G_k_1 = algorithm_(k - 1, n - 1);
if(G_k_1.size() == 0)
{
return G_k_1;
}
G_k_1 = union_(G_k_1, n);
if (k != n) {
for (unsigned long i = 0; i < memory.at(n - 1).size(); i++) {
if (memory.at(n - 1).at(i).first == k) {
G_k_1.insert(memory.at(n - 1).at(i).second.begin(), memory.at(n - 1).at(i).second.end());
memory.at(n - 1).at(i).second.clear();
break;
}
}
}
std::pair<int,my_map> temp;
temp.first = k ;
temp.second = G_k_1;
memory.at(n).push_back( temp ); //storing in hash table for further use
return memory.at(n).back().second;
}
int main()
{
my_vector v1,v2,v3,v4,v5;
my_set s1,s2,s3,s4,s5;
for(int i = 1; i<=5; ++i)
{
v1.push_back(1);
v2.push_back(2);
v3.push_back(3);
v4.push_back(4);
v5.push_back(5);
}
s1.insert(1);
s2.insert(2);
s3.insert(3);
s4.insert(4);
s5.insert(5);
bases.insert(bases.end(),make_pair(s1,v1));
bases.insert(bases.end(),make_pair(s2,v2));
bases.insert(bases.end(),make_pair(s3,v3));
bases.insert(bases.end(),make_pair(s4,v4));
bases.insert(bases.end(),make_pair(s5,v5));
my_set empty_set;
my_vector empty_group(DIMENSIONS);
G.insert(make_pair(empty_set,empty_group));
vector<std::pair<int,my_map> > empty_element;
empty_element.push_back(make_pair(0,G));
for (int i = 0; i <= 5; i++) { // 5 is the total number od vectors : v1,v2,v3,v4,v5
memory.push_back(empty_element);
}
data.insert(bases.begin(),bases.end());
cout << endl << "The intial set of vectors are : " << endl;
print ( data );
int k;
cout << "N = 5 " << endl << "Enter the value of k : ";
cin >> k;
cout << "The values for N choose k are : " << endl;
data = algorithm_(k,5);
print ( data );
}
If you run the program you know what I wanted to achieve and in what way. This ALGORITHM (not program) might not be efficient for a smaller number of vectors but it will be when N > 50k and k ~ 10. I'm aware the implementation of the algorithm (my program) is very inefficient. Is there any way to improve it ? I think the same algorithm can be implemented in a much more elegant fashion. Any help is much appreciated. Thanks.
My apologies for misunderstanding your answer previously, I didn't really understand what you were trying to do in your post, I thought you were just looking for a non-recursive way of computing nCk :P
I've created a class, CombinationGenerator to produce the combinations of vectors, which I believe is what you want. It works by producing a vector of ints representing the indices of the elements to aggregate (I've included a main function below which should help to explain it programmatically).
Here is the header file: http://pastebin.com/F5x4WKD9
And the source file: http://pastebin.com/CTV1PLRb
And here is a sample main function:
typedef std::vector<int> vecInt;
int main() {
// We have a deque containing 3 elements (try using experimenting with data
// types to test space complexity, std::set or std::unordered_set might be an option)
vecInt vec1;
for( int i = 0; i < 3; i++ )
{
vec1.push_back(1);
}
vecInt vec2;
for( int i = 0; i < 3; i++ )
{
vec2.push_back(2);
}
vecInt vec3;
for( int i = 0; i < 3; i++ )
{
vec3.push_back(3);
}
vecInt vec4;
for( int i = 0; i < 3; i++ )
{
vec4.push_back(4);
}
vecInt vec5;
for( int i = 0; i < 3; i++ )
{
vec5.push_back(5);
}
std::deque<std::vector<int>> dequeVecs;
dequeVecs.push_back( vec1 );
dequeVecs.push_back( vec2 );
dequeVecs.push_back( vec3 );
dequeVecs.push_back( vec4 );
dequeVecs.push_back( vec5 );
// Create our CombinationGenerator:
CombinationGenerator* gen = new CombinationGenerator();
g_pCombinationGen = gen;
gen = NULL;
unsigned long long size = g_pCombinationGen->ComputeBinomialCoefficient( dequeVecs.size(), 2 );
std::vector<int> currCombination;
g_pCombinationGen->Initialize( dequeVecs.size(), 2, size );
while( !g_pCombinationGen->IsFinished() )
{
currCombination = g_pCombinationGen->NextCombination();
std::vector<int> result;
for( int i = 0; i < dequeVecs[0].size(); i++ )
{
result.push_back( dequeVecs[currCombination[0]][i] + dequeVecs[currCombination[1]][i] );
}
std::cout << "(";
for( int i = 0; i < result.size(); i++ )
{
std::cout << result[i];
}
std::cout << ")" << std::endl;
}
return 0;
}
Whilst this may look rather large, if you analyze the space usage of it (let's assume that you're using n = 50,000 and k = 1000:
There are 50,000 vectors each containing 3 ints (let's assume a reasonably harsh overhead per vector of 32bytes, it's normally around 20 on most implementations): So, (50,000 * 3 * 4) + (50,000 * 32) = 2,200,000 Bytes
You're then containing this in a deque, which we will also assume has an overhead of 32bytes: 2,200,000 + 32 = 2,200,032 Bytes
We're also having an instance running of the Combination Generator, this has 5 member variables, two ints, two long longs, and a vector containing k ints (in this case 1000), so: 2,200,032 + (2*4) + (2*8) + (1000*4) + 32 = 2,204,056 Bytes
We also have the vector containing the result for each iteration again with k ints: 2,204,056 + (1000*4) + 32 = 2,208,088 Bytes
As you can see, this is far below your 4GB of memory. NOTE: It would not be possible to store each of these vectors in memory regardless of what implementation you used, as there would be over 9.94 x 10^2126 vectors containing results. Even if you chose a small value of k such as 10, you would still have over 2.69 x 10^40.
I hope this time I've understood what it is you're asking for! If not, I'll try and understand again what it is you're trying to achieve. :)
这篇关于动态迭代编程来生成组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
