質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.37%

  • C++

    2409questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • 配列

    402questions

    配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

  • Visual C++

    82questions

    Microsoft Visual C++はWindowsのCとC++の統合開発環境(IDE)であり、コンパイラやデバッガを含んでいます。

  • Visual Studio 2012

    79questions

    Microsoft Visual Studio 2012は、Microsoftによる統合開発環境(IDE)であり、多種多様なプログラミング言語に対応しています。 Visual Studio 2010の次のバージョンです

  • 関数型プログラミング

    20questions

    関数型プログラミングとは、関数を用いて演算子を構築し、算出し、コンピュータプログラムを構成する枠組みです。

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

受付中

回答 3

投稿 2017/12/01 05:16

  • 評価
  • クリップ 0
  • VIEW 116

前提・実現したいこと

プログラミング言語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 ”()”で括っている部分を除く数が1回だけ出現しているか検査するプログラムをつくっています。

発生している問題・エラーメッセージ

莫大な量の計算なので効率化を図りたいので、kの4つの要素が例えば(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;
}

/**
引数の2次元配列をきれいに表示するやつ
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です

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+1

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

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

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

投稿 2017/12/01 08:10

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/01 10:59

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

    キャンセル

0

  • 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')

投稿 2017/12/01 12:41

編集 2017/12/01 17:46

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

すごい愚直に回したコードが以下になります。
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);
                }
            }
        }
    }


}

投稿 2017/12/01 14:50

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

ただいまの回答率

91.37%

関連した質問

  • 解決済

    半角スペース区切りの文字を数える

    vs2015を使用して半角スペース区切りで入力された文字の数(例えばT T Y Y T Y T T T Yような入力)を数えるため #include <iostream> u

  • 解決済

    C++でJavaのcontainsAllを実現したい

    前提・実現したいこと C++のstd::setでJavaのcontainsAllを実現しようとしているのですが,イテレータの値を使ってset内を検索しようとすると以下のエラーが出ま

  • 解決済

    配列の要素間の和を全パターン求めるプログラムを作成したい。

    皆様ありがとうございました。 前提・実現したいこと <CもしくはC++> 配列の要素間の和を全パターン求めるプログラムを作成したい。 【例】 /*-------------

  • 受付中

    Ajax通信でCGIを使いJSONデータを操作したいです

    前提・実現したいこと AjaxでPOST関数を使い、C++で作成したCGIを呼び出し、JSONデータを取得したいです。 Ajaxからは JSONデータを送信しています。 そのため、

  • 解決済

    数字の合計を表示させる方法

    こんにちは。C++で、int a,bにいくつかの数字を入力し、それぞれの合計を表示するプログラムを作りたいのですが、合計を表示させる方法が分かりません。どなたか教えていただけないで

  • 解決済

    2次元配列の値を関数の引数として渡したい

    タイトルの通り2次元配列で作ったものを関数の引数として渡したいです。また、2次元配列の大きさは固定ではありません。 私が書いたコードは、以下のようになります。 #inclu

  • 解決済

    行と列が違う配列の掛け算

    前提 書籍で勉強している学生です。 書籍の2周目をしています。 書籍の解答がないため問題のヒントや解説をしていただけると嬉しいです。 問題 4行3列の行列と3行4列の行列の積を

  • 解決済

    【vector】vector.erase()を高速化したい

     解決済みですが、まだまだこんなのあるよ!という方のコメントを随時募集してます! 前提・実現したいこと タイトルの通り、C++のSTLコンテナの一つvectorクラスの"vecto

同じタグがついた質問を見る

  • C++

    2409questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • 配列

    402questions

    配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

  • Visual C++

    82questions

    Microsoft Visual C++はWindowsのCとC++の統合開発環境(IDE)であり、コンパイラやデバッガを含んでいます。

  • Visual Studio 2012

    79questions

    Microsoft Visual Studio 2012は、Microsoftによる統合開発環境(IDE)であり、多種多様なプログラミング言語に対応しています。 Visual Studio 2010の次のバージョンです

  • 関数型プログラミング

    20questions

    関数型プログラミングとは、関数を用いて演算子を構築し、算出し、コンピュータプログラムを構成する枠組みです。