• ベストアンサー
※ ChatGPTを利用し、要約された質問です(原文:順列の列挙の方法)

順列の列挙の方法

stomachmanの回答

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.6

既に答を得ているんですが、説明をまとめる時間がとれません。もうちょっと待ってね。プログラムを書いた方が早いかも知れないけど、それじゃ考え方や面白みが伝わらない。  なお、巡回セールスマン問題は、「最短経路を求めよ」という条件があるからNP完全になるんであって、単にハミルトン閉路を求めるのはそんなに難しい問題じゃありません。

関連するQ&A

  • 完全順列の証明

    赤チャートに完全順列の証明が載っていました <証明> n個の数の順列1,2,・・・,nの完全順列の個数をW(n)で表す。 1,2,・・・,nの完全順列をf(1),f(2),・・・f(n)とする。 f(1)=k とするとこの完全順列は[1],[2]のどちらかである。 [1]f(k)=1 であるもの  1,k を除いた 2,・・・,k-1,k+1,・・・,n のn-2個について完全順 列であるからその個数はW(n-2)個 [2]f=(k) ではないもの   f(h)=1とするとh=kではないから,f(1)=1,f(h)=kと置き換えると,1を 除いた 2,・・・,n のn-1個について完全順列であるから,その個数  はW(n-2)個 2≦k≦nであるから,kのとりうる値は n-1通り したがってW(n)=(n-1){W(N-1)+W(N-2)}    <終> いくつか理解できない点があります (1)なぜf(k)=1と、f(k)=1でないものに分けて考えているのでしょうか? (2)[2]で、f(1)=1,f(h)=kと置き換えるとはどういう事なのでしょうか?  何のために置き換えるのですか?

  • 円順列

    1~nの数字を書いたカードがそれぞれm枚ずつ、計nm枚ある。 これを1列に並べる順列の数F(n,m)は、F(n,m)=(nm)!/(m!)^n では、このm枚を円環状に並べる円順列の数G(n,m)はどうなるでしょうか? m=1なら、 G(n,1)=F(n,1)/n=(n-1)! m=p (pは素数)なら、 G(n,p)=(F(n,p)-F(n,1))/(np)+F(n,1)/n =((np)!/(p!)^n-n!)/(np)+(n-1)! mが任意の自然数のとき、G(n,m)をnとmの式、または漸化式で表すことは可能でしょうか? ちなみに、n,mが小さい数値のときのG(n,m)の値は次のようになっています。 G(2,2)=2 G(2,3)=4 G(2,4)=10 G(2,5)=26 G(2,6)=80 G(2,7)=246 G(2,8)=810 G(2,9)=2704 G(2,10)=9252 G(3,2)=16 G(3,3)=188 G(3,4)=2896 G(3,5)=50452 G(4,2)=318 G(4,3)=30804 G(5,2)=11352

  • モンモール問題、完全順列、攪乱順列の拡張

    モンモール問題、完全順列、攪乱順列で検索するといろいろな言い回しがあります。 1,2,3,・・・,n の数を並び替えたとき、先頭から数えた順番と数が一致するものが1つもない並べ方 n人がプレゼントをもちよって、バラバラに交換したとき、1人も自分自身の用意したプレゼントをもらわない方法 写像f:{1,2,…,n}→{1,2,…,n}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i の総数 これらの場合の数は、n!Σ[k=0,n]{(-1)^k}/k!であることはよく知られています。 そこで、拡張として次の総数を考えるとどうなるのでしょうか? n≦mとする。 写像f:{1,2,…,n}→{1,2,…,m}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i の総数 たとえば、n=3,m=4のとき、 (f(1),f(2),f(3))=(2,1,4),(2,3,1),(2,3,4),(3,1,2),(3,1,4),(3,4,1),(3,4,2),(4,1,2),(4,3,1),(4,3,2)

  • 同じものを含む順列(YOKOHAMA)

    赤チャート数学I+A(例題32)の問題の解答の一部を理解できず,質問をしています。 YOKOHOMAの8文字(AとOが2つ,YKHMが1つ)を横1列に並べての順列を考える問題です。 ただし,AOという並び,または,OAという並びの少なくとも一方を含むことです。 考え方は,少なくとも一方ですから,排反を考えて, (解答)=(制約なしの順列全体)-(一つも含まない) そこで,一つも含まない場合を考えるため, 次の□にはAまたはOが入り,〇にはYKHMが入るものとしたとき,題意より,次の並びとなります。 □〇□〇□〇□〇□ 〇は4つ,YKHMも4文字ですから,この順列の場合の数は 4!です。 ここまでは納得しています。 困ったのが次です。 五つの□に入るパターンは,次の4つ [1] A, A, O, O [2] AA, O, O [3] OO, A, A [4] OO, AA [1]の場合,私は, 五つの□から四つを選び(5_C_4),その中で,A,A,O,Oを並べるので4!,そして,A,A と O,Oはひっくり返しても同じだから,それぞれ 2!で割ると考え,この場合の数は 5_C_4 × 4 ! /( 2 ! × 2! ) ・・・・・(1) と考えたのですが,解答では, 5_C_2 × 3_C_2         ・・・・・(2) です。  (2)式も説明を受ければ納得できるのですが,(1)式の考え方なぜ違うのかがわかりません。 まず,この私の考え違いをご教示お願いします。 次に,[4]の場合,私は, 五つの□から二つを選べばよいと考えて,この場合の数は 5_C_2        ・・・・・(3) と考えたのですが,解答では 5_P_2        ・・・・・(4) となっています。 (3)式の考え方が なぜ違うのか,この点のご教示をお願いします。

  • 順列文字の生成処理

    次のような左端の番号に対応した右側の文字列を作りたいのです。 これらの4個の文字列は、重複無しの順列になります。 下表では文字列が4個ですが、実際には7個程度まで生成したいのです。7個の場合は合計1*2*3*4*5*6*7=5040個になります。 言語はFORTRANですがCでも、あるいは手順説明でも良いです。文字列でなくともn桁数字あるいは配列でも良いです。c++のクラス処理も候補かも知れませんが、FORTRANで書くには荷が重いです。再帰処理は何とかなるかも知れませんが、できれば無しを希望します。 4個程度ならデータとして書けば済みますが、6,7個となるとそうは行きませんので、プログラムで生成したいのです。処理時間は問題になりません。 N個の処理を使ってn+1個の処理の形式で大分頭を悩ませましたが、ギブアップ気味です(まだ1日程度ですが)。虫の良いお願いですが奇特な諸兄のお知恵を拝借したく存じます。 1: 1234 2: 2134 3: 1324 4: 3124 5: 2314 6: 3214 7: 1243 8: 2143 9: 1423 10: 4123 11: 2413 12: 4213 13: 1342 . . 18: 4312 19: 2341 . . 24: 4321

  • 遺伝的アルゴリズムの評価式に関する質問です。

    膨大な数の組み合わせから正解の組み合わせを求めるという大規模組み合わせ問題があったとします。 このような問題を遺伝的アルゴリズムを用いて解こうとしているのですが、今用いている評価式より良いアイデアが自分では考えつかなかったため質問します。 以下、問題や用いている遺伝的アルゴリズムに関する詳しい説明です。 例えば、仮に、23, 21, 65, 78, 43, 78, 83, 56, 78 ,89 の10個の数の組み合わせがあるとき、 合計して109になる組み合わせ(23,21,65)を見つけたいという問題です。(正解の組み合わせは複数個あっても、一個見つかれば良い。また正解の組み合わせは必ずあるものとする。) この問題を遺伝的アルゴリズム(GA)を使って解くとします。 以下、簡単なGAの説明です。 表現型に2進数ビット列を用いる。 個体数は200とし、初期個体はランダムで生成する。 評価式はf(x) = b/(b+|b-t|)(bは正解の組み合わせの合計値で、tは2進数ビット列で1を立てた場所の数の合計値である。)。終了条件はこの評価値がf(x)=1になることである。 交叉は一様交叉で突然変異も行う。 表現型について詳しく説明すると、 コード化に 0と 1の並びである2進数ビット列を用いて、 その場所に対応する数を加算する場合は1を, 逆に加算しない場合は0を遺伝子の表現型に立てビット列を生成しました。 例えば今回の正解の組み合わせ(109)を2進数ビットで表すと下のようになる。 23, 21, 65, 78, 43, 78, 83, 56, 78 ,89 1 1 1 0 0 0 0 0 0 0 ←2進数ビットを用いた表現型。 (1が立っている場所の数が加算されて合計で109となり、これが正解の組み合わせであることがわかる。) そして、この遺伝的アルゴリズムの評価式を f(x) = b/(b+|b-t|) とします。(bは正解の組み合わせの合計値で、tはビット列で1を立てた場所に対応する数の合計値である。) 評価式f(x)=1になる、つまり正解の組み合わせが見つかれば、遺伝的アルゴリズムは終了する。 この評価式で遺伝的アルゴリズムを回しているのですが、この簡単な評価式では近似解に陥ったとき、解を求めるのがどうしても遅くなってしまいます。 全体的に長く、わかりにくい説明で申し訳ないのですが、この評価式の改善案、またはこの遺伝的アルゴリズムの改善案などがあれば教えていただきたいです。 以上、よろしくお願いします。

  • 状況の変化をある関数で表す問題(順列)

    「m個所の送信施設を持つA国から、n個所の受信施設を持つB国へ信号を送る。A国の各施設はB国の施設の中のただ1個所に必ず信号を送るものとし、その送受信は一斉に行われる。いまm≧nとし、B国のどの受信施設もA国のどこかの送信施設からの信号を少なくとも1つは受信する場合を考える。このような送信パターンの数をf(m,n)と表す。以下m,nを変化させて考えるとき、次の問いに答えよ。 (1)n=3のときf(m,3)をmを用いて表せ。 (2)f(m+1,n)をf(m,n)およびf(m,n-1)を用いて表せ。ただしn≧2とする。 (3)f(m+1,m)をmを用いて表せ。」 という長い問題に取り組んでいます (1)すら解けなくて困っています。 m=3のときをまず考えました。mの3箇所からの送信がnの3箇所に受信されるので、mの3箇所の並び替えで3P3=3!=6  m=4のときはmの4箇所のうち3箇所を選んで並び替えて残り1箇所がnの3箇所のうちどれかに送信されるので4P3*3=72  という考え方でいいのでしょうか? 順列や組み合わせや確率がかなり苦手なので全く自信がありません。 (2)(3)は(1)がよくわからないのでできません。 教えていただければ幸いです。 宜しくお願いいたします

  • C++でのアルゴリズム

    次の条件を満たすアルゴリズムをC++のコードで教えてください! 大きさ2×1の長方形n個を 縦2 横n の長方形になるように並べるときの並べ方の総数を求めるアルゴリズム 入力nは、1以上の整数が入力される前提でよい。 例として、 n=1 1通り n=2 2通り n=3 3通り n=5 8通り n=7 21通り となります お願いします。

  • 文字列を数値に高速変換

    みなさんこんばんは。 文字列のセットがあります。 1.各文字列にインデックスを割り当てるには、   どのような方法がありますか?   0 から N-1 まで。N は文字列の個数 2.上記で作成したルールに基づき、   文字列をインデックスに高速に変換するには、   どのような方法がありますか? 原理、アルゴリズム、ソースコード、 なんでも結構です。 よろしくお願いいたします。

  • マクロで色つけ

    EXCEL2000で、条件に合うときセルを塗りつぶすマクロを作りたいので教えて下さい。 A列にはA01やB02など「英数数」の3桁のコードがあります。 A列がDから始まるときにF列G列をグレーに塗りつぶしたいのですが、 元々セルには黄色で配色していて、その後F列G列に入っている数値を確認したあとは、塗りつぶしを消します。 A列がDから始まるとき、F列とG列が、塗りつぶしがなければそのままで、黄色の時はグレーにするマクロを作成するにはどのようにすればよいでしょうか?