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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

LINQ

LINQとはLanguage INtegrated Queryの略で、「統合言語クエリ」という意味です。C#やVisual Basicといった言語のコード内に記述することができるクエリです。

Q&A

2回答

4762閲覧

(C#)全順列から条件を満たすものを検索する方法について

KeFynXpDww

総合スコア8

C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

LINQ

LINQとはLanguage INtegrated Queryの略で、「統合言語クエリ」という意味です。C#やVisual Basicといった言語のコード内に記述することができるクエリです。

0グッド

0クリップ

投稿2015/06/26 15:32

編集2022/01/12 10:55

魔方陣の規則を満足する組合せ全てを動的に計算する方法を探っています。
そのために次の処理を考えました。
しかし、最終的にToList<Int32[]>をするために、
Edge = 3 から 5に増やすと、パフォーマンスが格段に落ちています。
一番の原因は組合せ数の増加だと考えていますが、これを3, 5, 7と増やしてもある程度の
パフォーマンスを期待できる方法があればご教示ください。

どうぞよろしくお願いします。

処理の概要を、以下に記述します。

List<Int32[]> indexers // (行・列等の合計算出に使用するindexの集合)
int Edge // (辺の段数)
int Average // (各行・列の基準の合計)

lang

1IEnumerable<IEnumerable<Int32>> ap = allpermutation(Edge * Edge, nums) 2 .Where(line => indexers.All<Int32[]>( 3 indexes => (from index in indexes select line.ElementAt<Int32>(index)).Sum() == Average)); 4 5// 全順列を求めるメソッド 6static IEnumerable<IEnumerable<T>> allpermutation<T>(int count, IEnumerable<T> nums) 7{ 8 if (count == 1) 9 yield return new T[1] { nums.First<T>() }; 10 else 11 { 12 foreach (T t in nums) 13 { 14 T[] Current = new T[1] { t }; 15 IEnumerable<IEnumerable<T>> Rear = allpermutation(count - 1, nums.Except(Current)); 16 foreach (IEnumerable<T> childR in Rear) 17 yield return Current.Concat<T>(childR); 18 } 19 } 20}

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

順列をすべて列挙して試すという単純な方法では 魔法陣のサイズが大きくなると時間がかかります。
なならかの工夫が必要になります。
参考情報:

...
多重for文(笑)ですべての場合を探索するというのが基本方針ですが、それではさすがに終わらないので、次のような工夫をします。
...

他にも google で "C" 魔法陣 で検索すると、いろいろ情報を得られます。

投稿2015/06/26 23:10

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

C#は使ったことないですが
考え方はあっていると思うので参考までに

再帰処理後の判定よりも
再帰処理中の判定の方がはるかに効率が良いです

順列を生成する再帰処理の中で
合計値を判定し以降の処理を省略すれば
大幅に処理時間を削減できると思います

例えば3×3の魔法陣の場合
インデックスと値の関係を次の配置とします
T[0] T[1] T[2]
T[3] T[5] T[6]
T[4] T[7] T[8]

あらかじめindexersを
その集合の最大値で呼び出せるようにしておきます
例えば上の横列からなる0,1,2の集合を
最大値である2で呼び出せるようにします
(上の例では0,1,3を最大値とするものはなく
最後の8を最大値とする組みは3つも存在するので
なんらかのオブジェクトでラップした方がいいかもです)

T[2]まで生成
T[2]の2より0,1,2の組みを呼び出す
T[0]+T[1]+T[2] == 15(Average)
を満たすまでT[2]を変更

T[4]まで生成
T[0]+T[3]+T[4] == 15
を満たすまでT[4]を変更

T[5]を生成
T[2]+T[5]+T[4] == 15
を満たすまでT[5]を変更

T[6]を生成
T[3]+T[5]+T[6] == 15
を満たすまでT[6]を変更

T[7]を生成
T[1]+T[5]+T[7] == 15
を満たすまでT[7]を変更

T[8]は自動で決まるので
あとは残りの
T[4]+T[7]+T[8] == 15
T[2]+T[6]+T[8] == 15
T[0]+T[5]+T[8] == 15
をチェックする

説明図

投稿2015/08/22 06:38

e-cube

総合スコア284

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問