dポイントプレゼントキャンペーン実施中！

配列について、その要素を並べ替えて得られる配列を重複することなく全て得たいです。

締切済

  • 質問者：posi_fixed
  • 質問日時：
  • 回答数：3件

要素数が５つなら５！で120通り、ｎであればｎ！通りの配列をすべて得たい、といった具合です。

自分で組んでみたところ、再帰呼び出しを多用しているせいか要素を8つにした時点でFirefoxだと「このページのスクリプトは処理に時間がかかっているか応答しなくなっています。…」、IEでも似たような警告文が表示されてしまいます。

コードは以下に示すとおりです。

そこでお聞きしたいのは、

　１．「処理に時間が～云々」などの表示をさせずに処理を
　　続けさせるにはどのように書いたらいいか

　２．もっと短くスマートなコードで全走査できないか

の２つです。

１．についてはユーザサイドでなく開発者サイドで、かつalertを使う以外の方法で、警告文を出させないで処理を続けさせるためにはコードをどのようにしたらよいでしょうか。

２．に関しては、私が書いたコードは正直わかりにくいと思いますので、もっとシンプルに全走査できるアルゴリズムがあったら教えてほしいです。

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


<html>
<body>
<script type="text/javascript">
<!--
//Arrayオブジェクトに自身をコピーした配列を返すclone()メソッド追加
Array.prototype.clone = function(){
// 自分自身が配列かをチェック
if(this[0].constructor == Array ){
var ar, n;
//新しい配列を用意する
ar = new Array(this.length);
for(var n=0;n<ar.length;n++){
//再起呼び出しで配列の中身をコピー
ar[n] = this[n].clone();
}
//作成した配列を返す
return ar;
}
return Array.apply(null,this);
}

//★要素を並べ替える前の配列の宣言
var ar = new Array("1","2","3","4","5","6","7","8");

//並べ替え後の配列を格納する配列宣言
var arranged_ar = new Array();

function arArrange(){

//引数は(呼び出した節の、並び替える前の配列内での順番,すでに取り出した節の配列,兄弟の配列)
function createBranch(parentCounter,parentNodes,sameDepthBranches){

var branches = new Array(); //呼び出した節の子ノード格納用の配列宣言
branches = sameDepthBranches.clone(); //呼び出した節の兄弟をコピー
branches.splice(parentCounter,1) //呼び出した節を除いて子ノードの配列作成完了

var pushed_ar = new Array(); //この節以前に登場した節を格納する(最終的に並べ替え終わった配列になる)配列宣言
pushed_ar = parentNodes.clone(); //呼び出し元のpushed_arをコピー

for(var i=0;i<branches.length;i++){
pushed_ar.push(branches[i]); //pushed_arに子ノードを１つ追加

//走査が葉ノードに達したときの処理
if(pushed_ar.length == ar.length){
var length = arranged_ar.length;
arranged_ar[length] = new Array();

for(var j=0;j<pushed_ar.length;j++){
arranged_ar[length].push(pushed_ar[j]); //arranged_arに並び替え後の配列を格納
}
//走査がまだ葉ノードに達していない場合の処理
}else{
createBranch(i,pushed_ar,branches); //自身を再帰呼び出しすることで葉ノードに達するまでループ
}

//子ノード以下の走査が終わった場合の処理
pushed_ar.splice(pushed_ar.length-1,1); //追加した子ノードを削除して次の子ノード追加へ
}
return;
}

//↑で宣言したcreateBranch関数の呼び出し
for(i=0;i<ar.length;i++){
var tempAr = new Array();
tempAr.push(ar[i]);
createBranch(i,tempAr,ar);
}

//結果をresultに格納
var result = "";
for(var i=0;i<arranged_ar.length;i++){
result += i+1 + "：　";
for(var j=0;j<arranged_ar[i].length;j++){
result += arranged_ar[i][j] + ",";
}
result += "<br>";
}

//結果を画面に表示
document.getElementById("result").innerHTML = result;

return;
}
-->
</script>
<input type="button" value="全並べ替えパターン走査" onclick="arArrange();">
<p id="result">ここに結果表示</p>
</body>
</html>

通報する

この質問への回答は締め切られました。

質問の本文を隠す

A 回答 (3件)

No.3

  • 回答者： 15mm
  • 回答日時：

解説の前に補足。


「辞書式」は一般的な辞書式ではなく、配列tに定義された順を「辞書式」とする。
といった文言を書き忘れていました。（わかっていただけた気もしますが）


さて、解説。
全体の方針としては、
「n個の異なる文字を重複することなく１列に並べる場合の数を求めよ」
といったよくありがちな問題の解法、高校数学Ａの「階乗」の概念を使っています。
1文字目はn通り、2文字目は(n-1)通り、・・・

例としてn=4を使い
(1)動作の最終目的
(2)各々の文字が何番目かを表す数字で表現
(3)左から並べる過程の中で、その文字が残った文字の中で（0から数え）何番目か（ここがミソ）
を“右から”（表示崩れの都合上）図にしてみると、
(3)　　(2)　　(1)
0000 0123 abcd　　ここで、図(3)を縦に見てみると、規則性に気づくはずです。
0010 0132 abdc　　左からi個目(1≦i≦n)の数字は
0100 0213 acbd　　(n-i)! 個ずつ、0から(n-i)までの数字を繰り返しています。
0110 0231 acdb
0200 0312 adbc　　辞書式k番目(0≦k<n)のi文字目は、(変数_に代入される)
0210 0321 adcb　　Ａ　K=k%( (n-i+1)! )　kを(n-(i-1))!で割った余りKを利用して
1000 1023 bacd　　 (Kは(i-1)文字目までが同じとなる集団の中で何番目かを表す)
1010 1032 badc　　Ｂ　K÷((n-i)!)　を切捨てた数として表現されます
1100 1203 bcad
1110 1230 bcda　　(3)→(2)の復元の為、何文字目が使われたかを表す配列Aを使う。
1200 1302 bdac　　A[j] : j番目の文字が使用されているか
1210 1320 bdca　　A=[1,0,1,0],_=1の場合、Aの中で(_+1=)2回目に0が現れる場所が
2000 2013 cabd　　_に代入され(2)の数字を表す。
2010 2031 cadb　　(2)→(1)の復元は、t[_]
　　　略

function a(k){n=_n;N=_N/n;//n,Nは処理内で書き換えられるので、バックアップを代入。
//Nは本当は(n-1)!から必要なので、nで割っておく

for(i=0;i<n;i++)A[i]=0;//フラグ用配列初期化
var r=t[_=k/N>>0];A[_]=1;//一文字目。k<Nなので、式Ａ不要。>>0の０ビットシフトで正の数切捨て。
//_番目を使用したのでA[_]をtrueにしておく

for(i=1;i<_n;i++){//二文字目以降
k=k%N;//式Ａ　kそのものを上書きし、後のコードを簡潔化
N/=--n;//N:n! → N:(n-1)! に変更。 次回のループのためにnを小さくしておく
_=k/N>>0;//式Ｂ
for(j=0;j<=_;j++)_+=A[j];//(3)→(2)の復元処理
r+=t[_];A[_]=1;//(2)→(1)の復元をし、rに連結。Aに_番目使用済みと記録
}
return r;}

自分でも読んでて　これで分かるのか？　な感じです。
わからないところ聞いてください。
    • good
    • 0
    • 件
通報する

No.2

  • 回答者： 15mm
  • 回答日時：

＞１．「処理に時間が～云々」などの表示をさせずに処理を


＞　　続けさせるにはどのように書いたらいいか
処理を複数の関数に区切り、setTimeout等である程度ブランクを入れる。といいはず。
ループ回数が多いのは区切りにくいので通用しないかも？

それと、動作が速い表記を使う
new Array()→[]
なんかはすごくよく使う


＞２．もっと短くスマートなコードで全走査できないか
配列には、しないほうがよさそうです。
データの量がnの増加に伴って莫大に増えていく割りに、使われるデータはごく一部です。
きっとメモリも悲鳴を上げています。

私が考えたのは、arranged_ar[k]の形式で呼び出す代わりに、
arranged_ar(k)と表記し、関数によりその場でデータを生成する形です。

因に私の癖でショートコーディング風味になってしまったので、
変数名変わってます＆解説不能です（笑）
アルゴリズムも、これを説明するのか・・・？　って思うぐらいな物ですが、必要とあらば、たぶん、、します。。。できるかなぁ・・・
変数名・関数名は自由に変えてください

設定：n（整数。n<=35ではサクサクの動作を確認）、t（並べ替える文字たち。一文字ずつじゃなくてもＯＫ）
呼び出し：a(k)　で辞書式でk番目のデータ

<script><!--
var i,j,_,_n=n=35,_N=N=1,A=[];
var t=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r',
's','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','J','K','略...'];
while(n)N*=n--;//n!をNに格納
_N=N;n=_n;//バックアップ

function a(k){n=_n;N=_N/n;
for(i=0;i<n;i++)A[i]=0;//フラグ用配列初期化
var r=t[_=k/N>>0];A[_]=1;//一文字目

for(i=1;i<_n;i++){//二文字目以降
k=k%N;
N/=--n;
_=k/N>>0;
for(j=0;j<=_;j++)_+=A[j];
r+=t[_];A[_]=1;
}
return r;}

alert(a(10000))//辞書式で並べた結果の10000番目の文字列を計算。

//辞書式であることが確認されうるでしょう
//alert(a(0)+"\n"+a(1)+"\n"+a(2)+"\n\n"+a(50000)+"\n"+a(50001)+"\n"+a(50002))

//どうしても、というなら配列化。n>8ノンストップは無理。
//var ar=[];
//for(k=0;k<_N;k++)ar[k]=a(k)

//--></script>
    • good
    • 0
    • 件
通報する
この回答へのお礼

回答ありがとうございます。

大変参考になったのですが、お手数ですがコードの説明をしていただけますか？初心者でコードが理解できないので。。。

面倒であれば
var r=t[_=k/N>>0];A[_]=1;//一文字目
の行だけでもかまいません。

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

通報する
お礼日時：2009/06/12 19:34

No.1

  • 回答者： fujillin
  • 回答日時：

こんばんは。


面白そうなのでやってみました。
最初に考えたのは、クローンを作ったりしているとメモリを食いそうなので、定義された配列を順に並び替えるだけで、結果を求められないかということ。

御質問文のコードはほとんど見てないので、考え方は多分違うでしょう。
clac部分は配列a[]の後ろからk個の全ての並び替えを出力するルーチンで、個数k-1で自分自身をcallしています。

init部は配列を初期定義しているだけなので、
　var a = new Array("1","2","3","4","5","6","7");
みたいな1行でもすみます。　ので、若干コンパクトになっているかも。
（変数名を短くしたりしているのもあるので、ちゃんと比較はしていません）

さて、IE6で実験したところ、同様にn=8でアラートがでてしまいました。
resultを文字列で蓄えていると、大変長いものになる（n=8で40320行）ので、直接document.writeで表記すればよいかと試してみました（時間はこの方がかかると思う）が、結果は変わりませんでした。
それではと、出力をやめて、計算のみを行わせてみるとn=8はクリアできましたが、n=9で、やはりアラートが出てしまいました。

残念ながら、私の能力ではこのあたりまでで、あまりお役に立ちそうも無いですが、何かの参考にでもなれば…
<html>
<head>
<script type="text/javascript">
<!--
var a=[], al, result, count;
function init(){
al = parseInt(document.getElementById('val').value);
result = '想定範囲外'; count = 1;
if (al>0 && al<9) {
for (var i=0; i<al; i++) a[i] = i+1;
result = '計算対象配列：' + a.toString() + '<p>';
}
//document.write(result); //←直接出力
calc(al);
document.getElementById('result').innerHTML = result;
alert("calc end");
}

function calc(k){
if (k == 1) {
var s='000000' + (count++);
result += s.substr(s.length-7) + ': ' + a.toString() + '<br />';
//document.write(s.substr(s.length-7) + ': ' + a.toString() + '<br />'); //←直接出力
} else {
for (var n=0; n<k; n++){
calc(k-1);
var tmp = a[al-k];
for (var i=al-k; i<al-1; i++) a[i] = a[i+1];
a[al-1] = tmp;
}}
}
-->
</script>
</head>
<body>
<input type="text" id="val">
<input type="button" value="走査" onclick="init();">
<p />
<div id="result">ここに結果表示</div>
</body>
</html>
    • good
    • 0
    • 件
通報する
この回答へのお礼

回答ありがとうございます。参考にさせていただきます。

通報する
お礼日時：2009/06/12 19:26

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう！

Q質問する（無料）

ページトップページトップ

Q質問する（無料）

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

おすすめ情報