2次元配列の組み合わせについて

[ace-k@]

はじめまして．
C++で2次元配列 (vector_A) から任意の2行を取り出し，その2行の要素を内積した値を組み合わせ配列 (vector_B) の要素とする新たな2次元配列を作りたいのですが，どのように実装すればよいでしょうか？
教えて頂けると幸いです．

具体的には，以下のようなことをやりたいと考えています．

コード:

//元の配列： ( i=3, j=4)
std::vector<int> vector_A[i][j] = { 	0,1,0,1,
					1,1,0,0,
					1,1,0,1 };

//生成したい配列： ( i=3, i'=3)                                                  
std::vector<int> vector_B[i][i'] = {	2,1,2,
					1,2,2,
					2,2,3	 };
 

[みけCAT]

どのように実装すればよいでしょうか？

• パフォーマンス優先か、保守性・わかりやすさ優先か
• 移植性を重視するか、特定の環境(CPU・GPU・OS・コンパイラなど)だけで動けばいいか
• 要素の型は固定か、汎用にするか

などの条件によって変わってくると思うので、条件を教えてください。

コード:

//元の配列： ( i=3, j=4)
std::vector<int> vector_A[i][j] = { 	0,1,0,1,
					1,1,0,0,
					1,1,0,1 };

//生成したい配列： ( i=3, i'=3)                                                  
std::vector<int> vector_B[i][i'] = {	2,1,2,
					1,2,2,
					2,2,3	 };
 

それぞれの要素がstd::vector<int>なのですか？

[ace-k@]

ご回答ありがとうございます．
情報が足らず申し訳ありません．

実際の要素数はvector_Bが500×500程度になります．
ですが，実装は計算速度は気にせず，分かりやすさを重視したいと思っております．
また，移植性は気にせず，特定の環境で動けばよいです．
私の開発環境は，CPU：core-i7-4810MQ, GPU:Quadro K2100M, OS:windows7, VisualStudio2010pro になります．
要素の型は，int型のみです．

また，2次元配列をvectorで生成しており，各要素はint型になります．

よろしくお願いいたします．

[かずま]

コード:

//元の配列： ( i=3, j=4)
std::vector<int> vector_A[i][j] = { 	0,1,0,1,
					1,1,0,0,
					1,1,0,1 };

//生成したい配列： ( i=3, i'=3)                                                  
std::vector<int> vector_B[i][i'] = {	2,1,2,
					1,2,2,
					2,2,3	 };

どの 2行をとっても、内積が 3になることはないと思います。

コード:

#include <iostream>  // cout, endl
#include <vector>    // push_back, begin, end
#include <algorithm> // sort, next_permutation
using namespace std;

int iprod(vector<int>& a, vector<int>& b)  // inner product
{
	int p = 0;
	for (size_t i = 0; i < a.size(); i++) p += a[i] * b[i];
	return p;
}

int main()
{
	vector<vector<int>> a = {
		{ 0, 1, 0, 1 },
		{ 1, 1, 0, 0 },
		{ 1, 1, 0, 1 },
	};
	vector<vector<int>> b;

	size_t m = a.size();
	vector<int> p(m * (m - 1) / 2);
	for (size_t k = 0, i = 0; i < m - 1; i++)
		for (size_t j = i + 1; j < m; j++) p[k++] = iprod(a[i], a[j]);
	sort(begin(p), end(p));
	do b.push_back(p); while (next_permutation(begin(p), end(p)));

	for (size_t i = 0; i < b.size(); i++, endl(cout))
		for (size_t j = 0; j < b[i].size(); j++) cout << " " << b[i][j];
}

実行結果

コード:

 1 2 2
 2 1 2
 2 2 1

[ace-k@]

かずまさんご返信ありがとうございます．

コードも参考にさせて頂きます．
ただ，実行結果が私が手計算した結果と異なっているのですが．．．
たとえば，　行列ｂの {3,3} の要素は，　行列aの3行目同士の内積なので，1*1+1*1+0*0+1*1 = 3 になんると思ったのですが，
この場合，ご提示いただいたコードのどの部分を修正すると良いですか？

[かずま]

3行から任意の 2行を取り出すのは、(a[0], a[1]), (a[0], a[2]),
(a[1], a[2]) の 3通りしかないと考えていました。

1つの行を取り出して、(a[0], a[0]) としてもよいし、
(a[0], a[1]) と (a[1], a[0]) も異なる組み合わせと考えるんですね。

それならもっと簡単です。

コード:

#include <iostream>  // cout, endl
#include <vector>    // push_back, begin, end
using namespace std;

int iprod(vector<int>& a, vector<int>& b)  // inner product
{
	int p = 0;
	for (size_t i = 0; i < a.size(); i++) p += a[i] * b[i];
	return p;
}

int main()
{
	vector<vector<int>> a = {
		{ 0, 1, 0, 1 },
		{ 1, 1, 0, 0 },
		{ 1, 1, 0, 1 },
	};
	size_t n = a.size();
	vector<vector<int>> b(n);

	for (size_t k = 0, i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++) b[i].push_back(iprod(a[i], a[j]));

	for (size_t i = 0; i < b.size(); i++, endl(cout)) 
		for (size_t j = 0; j < b[i].size(); j++) cout << ' ' << b[i][j];
}

コード:

 2 1 2
 1 2 2
 2 2 3

[かずま]

コード:

	for (size_t k = 0, i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++) b[i].push_back(iprod(a[i], a[j]));

「k = 0, 」は不要です。

[かずま]

コード:

	size_t n = a.size();
	vector<vector<int>> b(n);

	for (size_t i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++) b[i].push_back(iprod(a[i], a[j]));

これだと、n x 0 の b を用意して、あとから、push_back で
列の数を増やしていますが、最初から n x n の b を用意して、
しかも、b[ i] == b[j] であることから、内積の計算回数を減らす
ことができます。

コード:

	size_t n = a.size();
	vector<vector<int>> b(n, vector<int>(n));  // b は n x n

	for (size_t i = 0; i < n; i++)
		for (size_t j = i; j < n; j++)    // j は i 以上
			b[i][j] = b[j][i] = iprod(a[i], a[j]);

[かずま]

しかも、b[ i] == b[j] であることから、内積の計算回数を減らす
ことができます。

コード:

訂正。b[i] == b[j] ではなく、b[i][j] == b[j][i] です。