全順列は、時間計算量が O(n!) のアルゴリズムです。2 日前に学生に講義をしていたときに、偶然この問題を思いつき、7 つのアルゴリズムで解くことができました。このうち動的ループはバックトラッキング アルゴリズムに似ており、実装が比較的面倒なので、読者の便宜のために 6 つのタイプをまとめました。すべてのアルゴリズムは JavaScript で記述されており、直接実行できます。
アルゴリズム 1: 交換 (再帰)
完全な置換 (再帰的スワップ) - Mengliao Software < body>
完全置換(再帰的スワップ)
Mengliao Software Studio - Bosun Network Co., Ltd.
2011.05.24
;
アルゴリズム 3: バックトラッキング (再帰) >
コードをコピー
完全な順列(再帰的バックトラック) - Mengliao Software ;
完全順列(再帰的バックトラック)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
< /html>
アルゴリズム 4: バックトラッキング (非再帰)
コードをコピー
コードは次のとおりです:
完全な置換 (非再帰的バックトラック) - Mengliao ソフトウェア<br></head> ;body> <br><p> 2012.03.29</p> <br><script type="text/javascript"> <br>/* <br>完全な配置 (非再帰バックトラッキング) 🎜>1. 位置配列 (position Arrange) を作成し、配置が成功した後、要素の配置に変換します。<br>2. n 番目の位置検索方法は、8 つのクイーン問題に似ています。 。 <br>*/ <br>var count = 0; <br>function show(arr) { <br> document.write("P<sub>" count "</sub>: " arr "<br / >"); <br>} <br>function look(index, n) { <br> var flag = false, m = n; //flag は見つかった位置配置のフラグ、m はどの位置が保存されているかを保存します検索 <br> do { <br> Index[n] ; <br> if (index[n] ==index.length) //利用可能な位置がありません <br> Index[n--] = -1;現在の位置 位置、前の位置に戻ります <br> else if (!(function () { <br> for (var i = 0; i <n i> if (index[i] = =index[n]) true を返します; <br> else <br> n ; <br> } while (!flag && n >= 0) <br> を返します。 🎜>function perm(arr) { <br> varindex = new Array(arr.length); <br> for (var i = 0; i <index.length i>index[i] = - 1; <br> for (i = 0; i シーク(インデックス, i) <br> while (seek(インデックス, インデックス.length - 1); 🎜> var temp = []; <br> for (i = 0; i <index.length i> temp.push(arr[index[i]]); <br> show(temp); <br> } <br>} <br>perm([" e1", "e2", "e3", "e4"]); <br></script> <br> ></html> <br><br><br> <br>アルゴリズム 5: 並べ替え (非再帰)<br><br><br><br><br><br>コードをコピー<br> <br><br> コードは次のとおりです:<br><div class="codebody" id="code76955">
<br><html xmlns="http://www.w3.org/1999/xhtml"> <br><head> <br> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <br> <title>完全な並べ替え (非再帰的並べ替え) - Mengliao ソフトウェア<br></head> ;body> 2012.03.30</p> <br><script type="text/javascript"> <br>/* <br>完全な配置 (非再帰的順序付け) アルゴリズム <br>1.配列、つまり、位置が配置され、配置が成功した後、要素の配置に変換されます。<br>2. 次のアルゴリズムに従って完全な配置を見つけます。<br> P を完全な配置とします。 1 から n (位置番号): p = p1, p2... pn = p1,p2...pj-1,pj,pj 1...pk-1,pk,pk 1...pn <br>(1) 配列の末尾から始めて、右側の最初の位置番号が最も小さいインデックス j を見つけます (j は先頭から計算されます)。つまり、 j = max{i (2) pj の右側の位置番号のうち、pj より大きい位置番号をすべて検索します。その番号内の最小の位置番号のインデックス k = max{i > pj} <br> pj の右側の位置番号は右から左に増加するため、k は pj より大きいすべての位置番号の中で最大のインデックスになります <br>(3) pj と pk を交換します <br>(4) 次に、pj 1 を反転します。 ..pk-1,pk,pk 1...pn で配置 p' = p1,p2...pj- 1,pj,pn...pk 1,pk,pk-1...pj 1 を取得します。 <br>(5)p' は p の次の順列です。 <br><br> 例: <br>24310 は位置番号 0 から 4 の配置の場合、次の配置を見つける手順は次のとおりです。 <br>(1) 配列内で右の数字より小さい最初の数字 2 を右から左に見つけます。<br>(2) この数字の後の数字の中で、より大きい最小の数字 3 を見つけます。 2 より <br>(3) 2 と 3 を交換して 34210 を取得します。<br>(4) 元の 2 (現在の 3) の後のすべての数字を置き換え、つまり 4210 を反転して、<br> を取得します。 (5) 24310 の次の順列は 30124 であることがわかります。 <br>*/ <br>var count = 0; <br>function show(arr) { <br> document.write("P<sub>" count "</sub>: " arr "<br / >"); <br>} <br>function swap(arr, i, j) { <br> var t = arr[i]; <br> arr[i] = arr[j]; <br> arr [j] = t; <br><br>} <br>関数 sort(index) { <br> for (var j =index.length - 2; j >= 0 && Index[j] >index[ j 1]; j--) <br> ; //このループは位置配列の末尾から始まり、左が右より小さい最初の位置を見つけます、つまり j <br> if (j for (var k =index.length - 1;index[k] <index k--> //このループは位置配列の末尾を調べて、大きい j 位置を持つ位置の最小値、つまり k <br> swap(index, j, k); <br> for (j = j 1, k = Index. length - 1; j swap(index, j, k) //このループは j 1 から最後までを反転します <br>} <br>function perm(arr) { <br> varindex = new Array(arr.length); <br> for (var i = 0; i <index.length i>index[i] = i; <br> do { <br> var temp = [ ]); <br>} <br>perm(["e1", "e2", "e4"]); <br></script> <br></body> <br><br><br><br>アルゴリズム 6: モジュロ (非再帰) <br><br><br><br><br><br>コードをコピー<br><br></index.length></index></sub>
</div> コードは次のとおりです: <br><div class="codebody" id="code59201">
<br><html xmlns="http://www.w3.org/1999/xhtml"> <br><head> <br> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <br> <title>完全な置換 (非再帰モジュロ) - Mengliao ソフトウェア<br></head> ;body> <br><p>完全な置換 (非再帰モジュロ)<br /> <br>2 の要素の総数を計算します。すべての n 個の要素、つまり n!; 任意の整数 >=0 から開始して n! 回ループし、インデックス <br> として記録します。 、1 桁の式の最下位ビットを見つけます。つまり、1 を法とするインデックスの値 w を見つけ、結果の最初の要素 (arr[0]) w 位置を挿入し、インデックスを <br>5 まで繰り返します。 2 番目の要素 arr[1] を取得し、バイナリ式の最下位ビット、つまりインデックス モジュロ 2 の値 w を見つけ、2 番目の要素 (arr[1]) を変更します。結果の w 位置を挿入します。インデックスをインデックス 2 に繰り返します。<br>6. 3 番目の要素 arr[2] を取得し、3 項式の最下位ビットを見つけます。つまり、インデックス モジュロ 3 w の値を見つけ、3 番目の要素 (arr[2]) を挿入します。結果の w 位置にインデックスをインデックス 3; <br>7,... <br>8 まで繰り返し、最後の要素 arr[arr.length-1 が取得される] まで、この時点で順列が得られます。 <br>9. インデックスループが完了すると、すべての順列が取得されます。 <br><br>例: <br>4 つの要素 ["a"、"b"、"c"、"d"] の完全な配置を見つけます。ループ 4!= 合計 24 回、任意の位置から開始できます> ;= 整数インデックス 0 によってループが開始され、ループがインデックス 23 に達した後に終了するまで、毎回 1 が累積されます。 <br> インデックス = 13 (または 13 24, 13 2*24, 13 3*24...) と仮定します。 )、合計 4 つの要素があるため、4 回反復後の結果の置換プロセスは次のようになります: <br>最初の反復、13/1、商 = 13、剰余 = 0、したがって、最初の要素が0 番目の位置 (つまり、添字は 0)、get ["a"]; <br>2 番目の反復、13/2、商=6、剰余=1 なので、2 番目の要素が最初の位置に挿入されます (つまり、つまり、添字は 1) で、[ "a", "b"] が得られます。<br>3 回目の反復、6/3、商 = 2、剰余 = 0 なので、3 番目の要素が 0 番目の位置に挿入されます。 (つまり、添字は 0)、[" c", "a", "b"] を取得します。<br>4 回目の反復、2/4、商 = 0、剰余 = 2、つまり 4 番目の要素が 2 番目の位置に挿入されます (つまり、添字は 2 です)。 Get ["c", "a", "d", "b"]; >function show(arr) { <br> document.write("P<sub>" count "</sub>: " arr "<br />"); <br>function perm( arr) { <br> var result = new Array(arr.length) ; <br> var fac = 1; <br> for (var i = 2; i fac * = i; <br> for (インデックス = 0; インデックス <fac> var t = インデックス; <br> for (i = 1; i var w = t % i; <br> for (j = i - 1; j > w; j--) <br> result[j] = result[j - 1]; = arr[i - 1]; <br> t = Math.floor (t / i); <br> } <br>} <br>perm([" e1", "e2", "e3", "e4"]); <br></script> <br></body> <br></html> <br><br><br>上記の 6 つのアルゴリズムの中には、バックトラッキング、ソートなどの位置を配置するものもあります。これは、配置する要素が数字や文字などである必要はなく、さまざまなタイプの要素に適応できるためです。</fac></sub>
</div></index.length></index.length></n></sub>
</div></index.length></index.length></index.length></n></index.length></sub>
</div></arr.length-1></arr.length>
</div></div><div class="nphpQianMsg"><div class="clear"></div></div><div class="nphpQianSheng"><span>声明：</span><div>この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。</div></div></div><div class="nphpSytBox"><span>前の記事：<a class="dBlack" title="jquery は、すべての主流ブラウザと互換性のあるシンプルなドラッグ アンド ドロップ効果の例を実装します (最適化)_jquery" href="https://m.php.cn/ja/faq/16912.html">jquery は、すべての主流ブラウザと互換性のあるシンプルなドラッグ アンド ドロップ効果の例を実装します (最適化)_jquery</a></span><span>次の記事：<a class="dBlack" title="jquery は、すべての主流ブラウザと互換性のあるシンプルなドラッグ アンド ドロップ効果の例を実装します (最適化)_jquery" href="https://m.php.cn/ja/faq/16914.html">jquery は、すべての主流ブラウザと互換性のあるシンプルなドラッグ アンド ドロップ効果の例を実装します (最適化)_jquery</a></span></div><div class="nphpSytBox2"><div class="nphpZbktTitle"><h2>関連記事</h2><em><a href="https://m.php.cn/ja/article.html" class="bBlack"><i>続きを見る</i><b></b></a></em><div class="clear"></div></div><ins class="adsbygoogle"
style="display:block"
data-ad-format="fluid"
data-ad-layout-key="-6t+ed+2i-1n-4w"
data-ad-client="ca-pub-5902227090019525"
data-ad-slot="8966999616"></ins><script> (adsbygoogle = window.adsbygoogle || []).push({});
</script><ul class="nphpXgwzList"><li><b></b><a href="https://m.php.cn/ja/faq/1609.html" title="Bootstrap リスト グループ コンポーネントの詳細な分析" class="aBlack">Bootstrap リスト グループ コンポーネントの詳細な分析</a><div class="clear"></div></li><li><b></b><a href="https://m.php.cn/ja/faq/1640.html" title="JavaScript関数のカリー化の詳細説明" class="aBlack">JavaScript関数のカリー化の詳細説明</a><div class="clear"></div></li><li><b></b><a href="https://m.php.cn/ja/faq/1949.html" title="JS パスワードの生成と強度検出の完全な例 (デモ ソース コードのダウンロード付き)" class="aBlack">JS パスワードの生成と強度検出の完全な例 (デモ ソース コードのダウンロード付き)</a><div class="clear"></div></li><li><b></b><a href="https://m.php.cn/ja/faq/2248.html" title="Angularjs は WeChat UI (weui) を統合します" class="aBlack">Angularjs は WeChat UI (weui) を統合します</a><div class="clear"></div></li><li><b></b><a href="https://m.php.cn/ja/faq/2351.html" title="JavaScript を使用して繁体字中国語と簡体字中国語をすばやく切り替える方法と、簡体字中国語と繁体字中国語の切り替えをサポートする Web サイトのトリック_javascript スキル" class="aBlack">JavaScript を使用して繁体字中国語と簡体字中国語をすばやく切り替える方法と、簡体字中国語と繁体字中国語の切り替えをサポートする Web サイトのトリック_javascript スキル</a><div class="clear"></div></li></ul></div></div><ins class="adsbygoogle"
style="display:block"
data-ad-format="autorelaxed"
data-ad-client="ca-pub-5902227090019525"
data-ad-slot="5027754603"></ins><script> (adsbygoogle = window.adsbygoogle || []).push({});
</script><footer><div class="footer"><div class="footertop"><img src="/static/imghwm/logo.png" alt=""><p>福祉オンライン PHP トレーニング，PHP 学習者の迅速な成長を支援します！</p></div><div class="footermid"><a href="https://m.php.cn/ja/about/us.html">私たちについて</a><a href="https://m.php.cn/ja/about/disclaimer.html">免責事項</a><a href="https://m.php.cn/ja/update/article_0_1.html">Sitemap</a></div><div class="footerbottom"><p> © php.cn All rights reserved
</p></div></div></footer><script>isLogin = 0;</script><script type="text/javascript" src="/static/layui/layui.js"></script><script type="text/javascript" src="/static/js/global.js?4.9.47"></script></div><script src="https://vdse.bdstatic.com//search-video.v1.min.js"></script><link rel='stylesheet' id='_main-css' href='/static/css/viewer.min.css' type='text/css' media='all'/><script type='text/javascript' src='/static/js/viewer.min.js?1'></script><script type='text/javascript' src='/static/js/jquery-viewer.min.js'></script><script>jQuery.fn.wait = function (func, times, interval) {
var _times = times || -1, //100次
_interval = interval || 20, //20毫秒每次
_self = this,
_selector = this.selector, //选择器
_iIntervalID; //定时器id
if( this.length ){ //如果已经获取到了，就直接执行函数
func && func.call(this);
} else {
_iIntervalID = setInterval(function() {
if(!_times) { //是0就退出
clearInterval(_iIntervalID);
}
_times <= 0 || _times--; //如果是正数就 --
_self = $(_selector); //再次选择
if( _self.length ) { //判断是否取到
func && func.call(_self);
clearInterval(_iIntervalID);
}
}, _interval);
}
return this;
}
$("table.syntaxhighlighter").wait(function() {
$('table.syntaxhighlighter').append("<p class='cnblogs_code_footer'><span class='cnblogs_code_footer_icon'></span></p>");
});
$(document).on("click", ".cnblogs_code_footer",function(){
$(this).parents('table.syntaxhighlighter').css('display','inline-table');$(this).hide();
});
$('.nphpQianCont').viewer({navbar:true,title:false,toolbar:false,movable:false,viewed:function(){$('img').click(function(){$('.viewer-close').trigger('click');});}});
</script></body></html> 
