辞書式配列の問題をJavaでプログラムを作って解いてみました。(^_^;
ABCDEFの6文字を全て使ってできる順列をABCDEFを1番目として、辞書式に並べる時、次の問いに答えよ。
(1)140番目の文字列を求めよ。
(2)FBCDAEは何番目の文字列か。
●DicPerm01.java
/* * DicPerm01.java * */ import java.util.Arrays; class DicPerm01 { static boolean next_perm(char[] p, int n, int r) { int i, j; char t; if(r <= 0 || n < r) return(false); for(i = r + 1; i <= n-1; i++) for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){ t = p[j]; p[j] = p[j-1]; p[j-1] = t; // swap(p,j,j-1); } for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--); if(i==0) return(false); for(j = n - 1; j > i && p[i-1] >= p[j]; j--); t = p[j]; p[j] = p[i-1]; p[i-1] = t; // swap(p,j,i-1); for(j=n-1; i< j; i++, j--){ t = p[i]; p[i] = p[j]; p[j] = t; // swap(p,i,j); } return(true); } public static void main(String[] args) { final String P="ABCDEF"; final int N=P.length(); final int R=N; char[] p=P.toCharArray(); // 順列生成用 String s=""; //--- (1) ---// long tm=System.nanoTime(); // Timer Start int count=0; Arrays.sort(p); // 念のためのソート do{ count++; s=new String(p); if(count==140) break; }while(next_perm(p,N,R)); System.out.println("(1)"+s); tm=System.nanoTime()-tm; // Timer Stop System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9); //--- (2) ---// tm=System.nanoTime(); // Timer Start count=0; Arrays.sort(p); // 必須のソート do{ count++; s=new String(p); if(s.equals("FBCDAE")) break; }while(next_perm(p,N,R)); System.out.println("(2)"+count+"番目"); tm=System.nanoTime()-tm; // Timer Stop System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9); } }
●実行結果
(1)BAFCED Runtime : 0.001 [sec] (2)633番目 Runtime : 0.002 [sec]
※参考URL
●特定の順列を見つける方法
●辞書式配列の問題を十進BASICで解いてみた。
- 作者: 今井なぎ
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2009/03/07
- メディア: 単行本
- クリック: 36回
- この商品を含むブログ (7件) を見る
- 作者: クロノス・クラウン,柳井政和
- 出版社/メーカー: 秀和システム
- 発売日: 2012/03/14
- メディア: 単行本
- クリック: 6回
- この商品を含むブログ (3件) を見る
- 作者: 河西朝雄
- 出版社/メーカー: 技術評論社
- 発売日: 2001/06
- メディア: 単行本
- 購入: 2人 クリック: 26回
- この商品を含むブログ (6件) を見る