- ベストアンサー
順列文字の生成処理について
f272の回答
- f272
- ベストアンサー率46% (8011/17123)
#4 ＆ #5です。 fortranが好きそうなので，fortranで同じプログラムを書いてみた。 なお，#4でのEnd Subの直前のNextは単なる消し忘れです。 program main implicit none integer::k,n,np,nt,nt1 integer,allocatable,dimension(:)::nn integer,allocatable,dimension(:)::pp n=7 allocate(nn(n-1)) allocate(pp(n)) np=factorial(n) do nt=0,np-1 nt1=np-1-nt Call n2f(nt1,n,nn) Call f2p(n,nn,pp) print*,nt+1,": ",pp end do contains integer function factorial(n) integer::n integer::n1 factorial=1 n1=n do factorial=factorial*n1 n1=n1-1 if (n1==1) exit end do end function subroutine n2f(nt1,n,nn) integer::nt1,n integer,dimension(*)::nn integer::i do i=1,n-1 nn(i)=0 end do k=1 Do k=k+1 nn(n-k+1)=mod(nt1,k) nt1=int(nt1/k) if (nt1<=0) exit end do end subroutine subroutine f2p(n,nn,pp) integer::n integer,dimension(*)::nn,pp integer::i,j,j2,k2,t do i=1,n pp(n+1-i)=i end do k=n-1 k2=n-1 do i=1,k j=nn(i) t=pp(k2+1-j) do j2=k2+1-j,k2 pp(j2)=pp(j2+1) end do pp(k2+1)=t k2=k2-1 end do end subroutine end program
関連するQ&A
- 順列生成アルゴリズムについて仕組みを教えてください
ある本を参考に順列を出力するプログラムをJavaScript用に書き直しました。 上手く動いたのですが、どうして、順列を出力できるのか理解できません。 まず、プログラムは以下になります。 <script> // 対象の配列 var array = [0,1,2,3]; // 配列の数 var N = array.length; // 順列を出力するプ関数 function permutation( n ) { // テンポラリー用 var temp; // 順列を生成する処理部分 if ( n < N ) { for ( var i = n; i < N; i++ ) { // （1）対象の配列から数字を一つ取り出して、他の数字と入れかえる temp = array[n]; array[n] = array[i]; array[i] = temp; // （2）再起呼び出し permutation( n + 1 ); // （3）入れ替えた数字を元に戻す temp = array[n]; array[n] = array[i]; array[i] = temp; } } else { // 出力 console.log( "結果：" + array); } } // エントリーポイント permutation(0); </script> 処理を理解するために、コメントの（1）や（3）などに console.log を入れて、出力したところ、全く理解できないスタックの流れになっていました。 具体的には、1～2を条件を満たす間繰り返した後、一度出力（スタック開放）します。その後、（3）の処理をするのですが、その直ぐ後に、また（3）の処理をするのです。 具体的なログは以下のようになりました。 【n=0】**************************// 関数の呼出しと呼出し時の引数です。 i=0 再帰前:1回:0,1,2,3 n=0 // （1）の処理です。0,1,2,3は、対象の配列です。 【n=1】************************** i=1 再帰前:2回:0,1,2,3 n=1 【n=2】************************** i=2 再帰前:3回:0,1,2,3 n=2 【n=3】************************** i=3 再帰前:4回:0,1,2,3 n=3 【n=4】************************** スタック開放：0,1,2,3 n=4 再帰後:1回:0,1,2,3 n=3 // （3）の処理です。 再帰後:2回:0,1,2,3 n=2 // なぜ連続して呼ばれているのか i=3 再帰前:5回:0,1,3,2 n=2 【n=3】************************** i=3 再帰前:6回:0,1,3,2 n=3 【n=4】************************** スタック開放：0,1,3,2 n=4 再帰後:3回:0,1,3,2 n=3 再帰後:4回:0,1,2,3 n=2 // なぜ連続して呼ばれているのか 再帰後:5回:0,1,2,3 n=1 // なぜ連続して呼ばれているのか i=2 再帰前:7回:0,2,1,3 n=1 【n=2】************************** “なぜ連続して呼ばれているのか”の部分が理解できません。予想では、再帰後の部分が一度呼ばれて、このプログラムは止まってしまうと思うですが、最後まで動きます。 なぜ、止まらずに動くのか教えてください。
- ベストアンサー
- JavaScript
- 数A 同じものを含む順列
数学Aの『同じものを含む順列』について質問です。 問. E , C , O , N , O , M , I , C , Sの9文字を並べて出来る順列の総数を求めよ 答. 9! / 2! * 2! とあります。 これを『C』または、『P』で表すことは出来るのでしょうか。 すみませんが、ありましたら、ご教授願います。
- ベストアンサー
- 数学・算数
- 文字列生成を総当りで行う場合
初めての質問で分かりにくいところもあるかと思いますが宜しくお願いします。 あ,い/うえ/おか,き,くけこ/さ/しす という文字列から、 あ/うえ/おか/さ/しす あ/うえ/き/さ/しす あ/うえ/くけこ/さ/しす い/うえ/おか/さ/しす い/うえ/き/さ/しす い/うえ/くけこ/さ/しす このような文章を作りたいのです。 言葉で説明しにくいのですが、"/"と"/"の間にある文字列を必ず１つ使い、","があるところを総当りで文字列を生成します。 私の作ったプログラムでは、この例のように6文で済む場合なら対応できるのですが、実際に使う文章はもっと長く、"/"の区切りも多く、更に"."が10個以上あることも多いので、文が億単位で生成されることも多々あります。intで表せない(今のプログラムでは、あらかじめ何個の文ができるか計算してから文を生成しています。)場合や、文字列を格納する場所が多くなりすぎてメモリが足りなくなり、生成できません。 この文字列生成は、上記の6個ように総当りで文字列が生成できれば、どの文が最初に生成されても構いません。できれば１文出来るごとにそれを使った違う処理に移り、返ってきたらその文を捨ててまた新たな文を生成できると嬉しいです。 どうぞ宜しくお願いします。
- ベストアンサー
- Java
- Ｃ言語で、再帰呼び出しを使用せずに、文字列"(12 + 3) * (
Ｃ言語で、再帰呼び出しを使用せずに、文字列"(12 + 3) * ( 3 * (4 + 5 ))"を、優先順位が低い順に二分木に入れる関数を作成したいのですが・・・。 char str[15] = ""(12 + 3) * ( 3 * (4 + 5 ))";なら char n[100];に n[0] = '*' n[1] = '+' n[2] = '*' n[3] = 12 n[4] = 3 n[5] = 3 n[6] = '+' n[7] = \0 n[8] = \0 n[9] = \0 n[10] = \0 n[11] = \0 n[12] = \0 n[13] = 4 n[14] = 5 （n[15] 以降は\0が格納されています。） というように入れたいのですが関数からその関数を呼び出す再帰を使わずに作成する方法がわかりません。 再帰を使用しなければかなり処理が複雑になるような気がしますがどなたか詳しい方よろしくお願いします。 言語はＣ言語です。
- ベストアンサー
- C・C++・C#
- 配列から網羅的な文字列を生成するには？
perlの配列を使った、網羅的な文字列生成について質問です。 ある特定の種類の文字のレパートリをつかった、n文字の文字列すべての組み合わせを生成したいと考えています。 例えば文字 A, B, C の三種類をつかった2文字の文字列なら AA,AB,AC,BA,BB,BC,CA,CB,CC 3x3 =9 種類というふうになります。 n=2の場合、 @array = qw(A B C); foreach $moji(@array){ $moji1 = $moji; foreach $moji(@array){ $moji2 = $moji; $mojiretu = $moji1.$moji2; push (@mojiretuset , $mojiretu ); }} print @mojiretuset; とするとforeachをふたつ重ねることで文字の組み合わせすべてを生成できました。 問題なのは、問題なのは、今私がしたいのは文字数nを（ループの）外から指定して（例えば$mojisuu = 6 などとして）n文字の場合の網羅的な文字の組み合わせを生じさせることなのです。 毎回自分でforeachを必要なだけ重ねて書き直す、というのは現実的ではありませんし、n個のforeachの入ったperlのコードを書くコードというのも避けたいのです。 文字数を自由に後から設定して、特定の配列から網羅的な組み合わせを生じさせるにはどのようなコードを書けばよいでしょうか？
- ベストアンサー
- Perl
- 組み合わせと順列 アルゴリズム
こんにちは 組み合わせと順列についてです。 順序関係のある要素で構成される集合から一定の数をとり、順列を辞書順で生成する方法がわかりません。 うまく説明できないので、例を示します。 たとえば２６文字のアルファベットから４文字を選んで辞書順に生成するプログラムはどのようにやればいいのでしょうか？ このアルファベットの例だと abcd abce abcf ・・・ abcz abdc abde ・・・ zyxw のようになると思います。 要素と長さが決まっている場合で順列を生成する部分は大丈夫です。（C++ STLのnext_permutationにあたる部分) 一応自分なりに考えたやり方は２６進数４桁のように考えて、それを１ずつ増やし、全体で２回以上使われていないかを調べる と思ったんですが、あまりスマートじゃないし要素がとびとびのアルファベットのときなどに応用が利かないと思いました。 指摘していただければ補足しますので、よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 順列の列挙の方法
順列の列挙の方法といっても辞書式順序のやつではありません。別の制約です。 グレイコードというのをご存知でしょうか。例えばビット列のグレイコードは次のようになります。 0:000 1:001 2:011 3:010 4:110 5:111 6:101 7:100 これがどんな制約を満たしているかと言うと、 1、となりのビット列に変換するには1ビット反転すれば良い。 2、すべてのビット列がちょうど1回現れる。 この2つです。グレイコードの正確な定義はさておき、とりあえず今はこれと言うことにします。 この順序でビット列を列挙する関数をC言語で書くと次のような感じになります。 f(int n) { if(n==-1)return; f(n-1); 第nビットを反転； 出力； f(n-1); } さて順列の話ですが、次のような制約を満たす順序で順列を列挙するアルゴリズムは どんな感じになるのでしょうか。 1、となりの順列に変換するには1回スワップ(2つの要素を入れ換える)すれば良い。 2、すべての順列がちょうど1回現れる。 この条件を満たすような順列の列はたくさんあると思いますが、 できるだけ法則性のあるやつ、というかプログラムに書きやすいやつを お願いします。 ビット列のアルゴリズムをちょこっと変えれば出来るかなーと思っていたのですが 数学的センスが無いせいか、苦戦しています。数学的センスのある方、ぜひご教示ねがいます。
- ベストアンサー
- 数学・算数
- ユニークな文字列を順次, 生成する関数
C++において, 適当な文字列を元に, ユニークな文字列を順次, 生成する関数を作りたいと思っています. (LISPで云う, 関数gensym()と似た役割を持つ関数です.) 例えば, "hoge"というstringを元に, "hoge0", "hoge1", "hoge4", "hoge8", "hoge100", ...., といったように, stringが互いに重複しないように, 適当な数字を連結した文字列を順次生成したいのです. 以下のように, 私なりの方法を考えてみたのですが, これだと, 今まで生成したstringを保存するhoge_setが必要になります. 何かより良い(シンプル, 効率的な)方法がありましたら, 教えていただけますでしょうか? よろしくお願い致します. (乱数を用いた方法) 1. 元となるstring型の変数nameを, "hoge" で初期化. 既に作成したstring文字列を保存する, set < string > hoge_setを宣言. 2. 乱数を生成し, それをnameにappendしたものを, string型の変数name2に代入. 3. 同じ文字列が存在したら, 2. に戻る. 同じ文字列が存在しなかったら, hoge_setに追加する.
- ベストアンサー
- C・C++・C#
- 【C#】文字列の最後に改行を入れていく処理
【C#】文字列の最後に改行を入れていく処理 C#初心者です。 ファイルを一行読み込むごとに、行の最後に改行\nを入れ、最後にその文字列を繋げ、出力したいのですが、やり方がわかりません。 結果は abcdefg hijklmn opqrstu のようになってほしいです。 分かる方いらっしゃいましたら教えていただけると幸いです。 宜しくお願いいたします。
- ベストアンサー
- C・C++・C#
- アルファベットを含むランダムな文字列を生成するには？
通常の数字を用いた乱数を発生させるには OrderNo + Int(17 * Second(Time) * Rnd) ：OrderNoはDB上にある注文番号の最終レコード値です という感じで、とりあえず適当にランダムな値を自動で生成させることができるのですが、 アルファベットなどの文字を含む場合のランダムな文字列の生成はどのようにすればよいのでしょうか？ 感じできには、 UkB1PgMJ zK22fw2W N1np8zDb DbetjqKq Cj58pfYm というものです。 例は、小文字の[i][l][o]と大文字の[I][L][O]と数字の[0]を含まないランダムな文字列を８桁で生成しています。 (使用したソフトは、Fapsis氏のPassword Creator TypeB Ver3.5です) 具体的には何か関数で、このような文字列をランダムに発生させるものがあるのでしょうか？
- ベストアンサー
- Microsoft ASP
お礼
FORTRANのコードで例示頂きありがとうございます。これならスムーズに確認することができそうです。
補足
今コードをコピペしてGFORTRANで実行するとなんのエラーもなく５０４０個の組み合わせがPRINTされました。コードの完成度と移行性が素晴らしいです。普段使わない記述があるのに！！ 動作を読んでみます。 （送れるチップの数が残りわずかになりました）