C++で重複配列を省くプログラム追加して作業効率を上げたいです。

Question

###前提・実現したいこと
プログラミング言語C++でk*kのある配列を作ろうとしています。
まずkの要素は4つでそれぞれ1~12の値が入ります。kの4つの要素をそれぞれabcdとして
以下のような配列を作っています。そして0より値が小さくなった場合0と12を基準に巡回しています。例えば-2の場合9、-1の場合12です。
(a-a), a-b , a-c, a-d
b-a ,(b-b), b-c, b-d
c-a , c-b, (c-c), c-d
d-a , d-b , d-c, (d-d)
そして、この配列が対角線上になる0　”()”で括っている部分を除く数が１回だけ出現しているか検査するプログラムをつくっています。
###発生している問題・エラーメッセージ
莫大な量の計算なので効率化を図りたいので、kの４つの要素が例えば(1,2,3,4)の時と
(1,2,4,3)や(2,1,4,3)の時などの重複配列は一緒なので配列を作る前に省きたいのですが、どのように省けばよいでしょうか？以下のプログラムコードを貼りますので改良のほうお願いします。
###該当のソースコード

#include <iostream>

using namespace std;

/**
引数の配列をきれいに表示するやつ
int* a  -> 配列データの先頭アドレス
int size -> 配列の大きさ
*/
void drawSgArray(int* a, int size) {
	for (int i = 0; i < size; i++) {
		if (a[i] < 10) { cout << " " << a[i]; }
		else { cout << a[i]; }
		if (i < size - 1) cout << ",";
	}

	return;
}

/**
引数の２次元配列をきれいに表示するやつ
int** a  -> 二次元配列データの先頭アドレス
int low -> 行の大きさ
int col -> 列の大きさ
*/
void drawDwArray(int** a, int row, int col) {
	for (int i = 0; i < col; i++) {
		for (int j = 0; j < row; j++) {
			if (a[i][j] < 10) { cout << " " << a[i][j]; }
			else { cout << a[i][j]; }
			if (j < row - 1) cout << ",";
		}
		cout << endl;
	}

	return;
}

/**
巡回差行列になっているか。なっていたらtrueを返す。
int** a  -> 二次元配列の先頭アドレス
int size -> 配列の長さ
int max  -> 最大値
int imp  -> 各値の表示回数
*/
bool check(int** a, int size, int max, int imp) {
	int* checker = new int[max + 1];  // 各値の表示回数を数えるやつ

	// checkerの初期化
	for (int i = 0; i < max + 1; i++) checker[i] = 0;

	// 行列の各要素の値を見て、どの値が何回出ているのかをcheckerに記録
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			if (i != j)	checker[a[i][j]]++;
		}
	}

	// 数字の出る回数がおかしかったらfalse
	for (int k = 1; k < max; k++) {
		if (checker[k] != imp) return false;
	}

	// 何事もなかったらtrue
	return true;
}

int main() {
	// ============================================================================================
	// 初期設定
	int cnt=0;		 //カウント
	int matrixSize;  // 行列の大きさ
	int numberMax;   // 最大値
	int impression;  // 出現回数
	int isAll;       // デバッグ

	cout << "配列の大きさ：";
	cin >> matrixSize;

	cout << "最大値：";
	cin >> numberMax;

	cout << "出現回数：";
	cin >> impression;

	cout << "すべての配列を出力する？(YES=1 / NO=0)：";
	cin >> isAll;

	// ============================================================================================
	// 間違い検知
	if ((matrixSize * (matrixSize - 1)) % (numberMax - 1) != 0 || matrixSize <= 1) {
		cout << "numberMaxの値、もしくはmatrixSizeの値を間違えて入力しています。" << endl;
		cin.get();
		cin.get();
		return 0;
	}
	// ============================================================================================
	// 計測開始
	int number[99] = {};  // 行列に代入する値を入れておく配列
	for (;;) {
		// 行列を表す二次元配列(matrix)の準備
		int** matrix = new int*[matrixSize];
		for (int i = 0; i < matrixSize; i++) {
			matrix[i] = new int[matrixSize];
		}

		// 行列に値を代入
		for (int i = 0; i < matrixSize; i++) {
			for (int j = 0; j < matrixSize; j++) {
				matrix[i][j] = number[i] - number[j];
				if (matrix[i][j] < 0) matrix[i][j] += numberMax;
			}
		}


		// ============================================================================================
		// 巡回差行列になっているかのチェック
		if (check(matrix, matrixSize, numberMax, impression) || isAll) {
			// もしも巡回差行列になっていたらコンソールに表示（isAllが1なら無理やり表示）
			cout << "========================" << endl;
			cnt++;
			// 代入した値をとりあえず書き出す
			cout << "(";
			drawSgArray(number, matrixSize);
			cout << ")" << endl;

			// 行列を書き出す
			drawDwArray(matrix, matrixSize, matrixSize);

		}

		// ============================================================================================
		// 次の数字へ（2,3,0,1なら、3,3,0,1になる）
		number[0]++;
		for (int i = 0; i < matrixSize - 1; i++) {
			if (number[i] >= numberMax) number[i + 1]++;
		}
		for (int i = 0; i < matrixSize - 1; i++) {
			// 繰り上げが必要ならやっておく
			if (number[i] >= numberMax) number[i] %= numberMax;
		}

		// ============================================================================================
		// メモリの開放
		for (int i = 0; i < matrixSize; ++i) delete matrix[i];
		delete matrix;

		// ============================================================================================
		// 最後まで計測できたのなら止める
		if (number[matrixSize - 1] >= numberMax) break;
	}

	cin.get();
	cout<<"巡回差集合は"<<cnt/24<<"個あります。"<<endl;
	cin.get();

	return 0;
}

###試したこと
メモ化も試してみたのですが12121212個も配列を作ることが出来なかったので無理でした・・・
###補足情報(言語/FW/ツール等のバージョンなど)
統合開発環境はVisual studio 2012です

Answer 1

順番と要素間での差しか影響しないので、

• a=0に決め打つ
• a<b<c<dとなるようなものだけ生成する

とすれば、生成数は大きく削減できます。

Comments

[i-am-programar]

質問の前提で大きなミスがありました。このプログラムは4つの要素が1~12までのある特定（０を除く配列が１回ずつ出現する）条件をみたす４つの要素を全て何個あるか見つけるプログラムでした。a=0にすると必ず0を含む残り３つ要素がそれぞれ数値が入っているという事で合っているでしょうか？

Answer 2

すごい愚直に回したコードが以下になります。
eSet.set.beginで戦闘のイテレータ取れるのでそのイテレータのvecの中身から自由に調理してください。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
class QuadElem
{
public:
	QuadElem();
	~QuadElem();
	bool operator==(const QuadElem& rhs) const;
	bool operator<(const QuadElem& rhs)const;
	void setArray(const int el1,const int el2,const int el3,const int el4);
	std::vector<int> vec;

private:
};

QuadElem::QuadElem()
{
	this->vec.resize(4);
}

QuadElem::~QuadElem()
{
}
bool QuadElem::operator==(const QuadElem & rhs) const
{
	return this->vec == rhs.vec;
}
bool QuadElem::operator<(const QuadElem&  rhs) const
{
	int left, right;
	left = this->vec[0] * 1000 + this->vec[1] * 100 + this->vec[2] * 10 + this->vec[3];
	right = rhs.vec[0] * 1000 + rhs.vec[1] * 100 + rhs.vec[2] * 10 + rhs.vec[3];
	return left<right;
}
void QuadElem::setArray(const int el0, const int el1, const int el2, const int el3)
{
	this->vec[0] = el0;
	this->vec[1] = el1;
	this->vec[2] = el2;
	this->vec[3] = el3;
	std::sort(this->vec.begin(), this->vec.end());
}

class ElemSet
{
public:
	ElemSet();
	~ElemSet();
	bool insert(const QuadElem);


private:
	std::set<QuadElem> set;

};

ElemSet::ElemSet()
{
}

ElemSet::~ElemSet()
{
}

bool ElemSet::insert(const QuadElem quadElem)
{
	auto t =this->set.insert(quadElem);
	return t.second;
}

int main(){
	QuadElem qE1, qE2, qE3, qE4;
	ElemSet eSet;
	for (size_t i = 1; i < 13; i++)
	{
		for (size_t j = 1; j < 13; j++)
		{
			for (size_t k = 1; k < 13; k++)
			{
				for (size_t l = 1; l < 13; l++)
				{
					qE1.setArray(i, j, k, l);
					eSet.insert(qE1);
				}
			}
		}
	}


}

Answer 3

• 1～K*(K-1) (= 1～12)の数値から相異なるK(=4)個を選ぶ。
• 上記のK個の相異なる2つの差がすべて( =4!=12種類)異なる。

ものを選べばいけると思います。

a...dの制約条件がうまく決めきれませんでしたが
以下pythonコードで全探索と上記の手法とで結果が一致したので正しいと思います。

K=2で2個, K=3で12個, K=4で96個, K=5で240個

import itertools

K = 4              # 正方行列 K * K
NUM_CNT = K*(K-1)  # 対角線以外を埋める数値の個数
NUMS = [i+1 for i in range(NUM_CNT)] # a...nの走査範囲値 1...NUM_CNT (= K*(K-1) )
#NUMS = [i for i in range(NUM_CNT+1)]

# 循環数を返す -1 = NUM_CNT, -2 = NUM_CNT-1, ...
def circleNum( n):
    if n < 0:
        n += NUM_CNT+1
    return n

# 数値リストから行列を作成
def getMat( nums):
    return [[circleNum( nums[i]-nums[j]) for j in range(K)] for i in range(K)]

# 重複判定 : 行列から
def isMatDup( mat):
    dup = set()
    for i,j in itertools.product([k for k in range(K)], repeat=2): # 直積
        if i != j:
            if mat[i][j] in dup:
                return True
            dup.add(mat[i][j])
    return False

# 重複判定 : 数値リストから
def isNumDup( nums):
    dup = set()
    for n in itertools.permutations(nums, 2):   # 順列
        diff = circleNum(n[0] - n[1])
        if diff in dup:
            return True
        dup.add(diff)
    return False


# 計算 : 全探索＋行列から判定
def calc1( path):
    print(path)
    with open(path, 'w') as f:
        dup = set() # 解（行列）の重複チェック用
        lopCnt,dupCnt,okCnt = 0,0,0
        for nums in itertools.product(NUMS, repeat=K): # 直積
            mat = getMat( nums)
            if not isMatDup(mat):
                key = str(mat)
                if key not in dup:
                    f.write( 'nums[%s] mat[%s]\n'%(nums,mat))
                    okCnt += 1
                    dup.add(key)
                else:
                    dupCnt += 1
            lopCnt += 1
        f.write( 'lop[%d] dup[%d] ok[%d]\n'%(lopCnt,dupCnt,okCnt))


# 計算 : 順列＋数値リストから判定
def calc2( path):
    print(path)
    with open(path, 'w') as f:
        dup = set() # 解（行列）の重複チェック用
        lopCnt,dupCnt,okCnt = 0,0,0
        for nums in itertools.permutations(NUMS, K):   # 順列
            if not isNumDup(nums):
                mat = getMat(nums)
                key = str(mat)
                if key not in dup:
                    f.write( 'nums[%s] mat[%s]\n'%(nums,mat))
                    okCnt += 1
                    dup.add(key)
                else:
                    dupCnt += 1
            lopCnt += 1
        f.write( 'lop[%d] dup[%d] ok[%d]\n'%(lopCnt,dupCnt,okCnt))

if __name__ == '__main__':
    calc1('calc1.txt')
    calc2('calc2.txt')