問題タブ [heaps-algorithm]

順列を生成するヒープのアルゴリズムが正しいことを証明する必要があります。その擬似コードは次のとおりです。

(Levitin によるアルゴリズムの設計と分析の概要から引用)

その正しさを証明するために帰納法を使用する必要があることはわかっていますが、その方法が正確にはわかりません。私は数式を証明しましたが、アルゴリズムは証明しませんでした。

証明はこんな感じになると思っていたのですが…

誘導ステップを終了する方法がわかりません。私はここで正しい軌道に乗っていますか？どんな助けでも大歓迎です。

私は、ヒープのアルゴリズムの再帰バージョンの実装に取り​​組んできました。擬似コードへのリンクは次のとおりです: http://en.wikipedia.org/wiki/Heap%27s_algorithm

再帰部分に到達するまで、すべてが順調に進んでいます。まだ交換要素を入れていないことはわかっていますが、そこまでは進んでいません。セグメンテーション違反があったことを示す gcc デバッガーを使用するまで、実行はエラーを表示せずに失敗します。これが私のコードです：

C++ で Heap のアルゴリズムを実装しようとしています。
ただし、並べ替える文字列の長さが 4 になると、アルゴリズムは繰り返しを開始します。コードは次のとおりです。

そして、これが出力です。13行目で繰り返す

みんなありがとう、どんな助けも大歓迎です！

整数の配列のすべての可能な順列を生成するために、ヒープのアルゴリズムを再現しようとしていますが、3 以外の整数については解決できません。ウィキペディアのヒープのアルゴリズム:

私のコード:

私は何を間違っていて、それについて誤解していますか? 入力として [1,2,3] (n=3) でのみ機能し、n=2 や n=4 では機能しないのはなぜですか?

ラン:

返信ありがとうございますが、それは問題ではありません。質問する前にそれを変更しようとしましたが、明確に述べられているようにWikiページを正しく理解していれば（特定の言語/ for-loop-schemeは言及されていませんが）、1から始めることはアルゴリズムの一部だと思います。以下は、いくつかの重複を含む n=4 の出力です。Wiki ページへのリンク: http://en.wikipedia.org/wiki/Heap%27s_algorithm

私は、金曜日の入学願書の実際の順列アルゴリズムに頭を悩ませて (ついに) 一日を費やしました。Heap のアルゴリズムは、私にとって最もシンプルでエレガントに思えました。

ここにその例があります：http://en.wikipedia.org/wiki/Heap%27s_algorithm

最終的な順列配列のログは次のとおりです。

最初の 12 個の順列がうまくいき、その後不思議なことに「,」が追加され、最初の 12 個の順列が繰り返されます。私は困惑しています。

編集：上記は、コメントが役立つと言ったことを考慮して更新されたコードです。まだ順列の半分しか取得していません。

C++ でHeap のアルゴリズムを実装しようとしています。アルゴリズムが機能するのとまったく同じようにコードを書いたと思いますが、間違った結果が得られます。

私はこの仕事をしようとして立ち往生しています。上記のコードのベクトルでは、ばかげた結果が得られます。

123 123 123 123 213 213 321 321 321 231 231 123 123 123 213 213

整数のタプルの順列を繰り返す必要があります。順序は、各ステップで要素のペアを交換して生成する必要があります。

これを行うはずの Heap のアルゴリズムに関するウィキペディアの記事 ( http://en.wikipedia.org/wiki/Heap%27s_algorithm ) を見つけました。擬似コードは次のとおりです。

このためのジェネレーターをPythonで作成しようとしました：

これにより、次の順序で順列が生成されます ([0,1,2,3] の入力の場合)。

これは、1 ペアの交換ではない最後のステップまで問題ないようです。

私は何を間違っていますか？

配列 A の要素のすべての順列を見つけるためのヒープ アルゴリズムを実装しました。

私はJavaが初めてです。問題は、関数 perms(A) の出力 (戻り値) として B を使用したいのですが、この実装では int[n! を初期化する必要があります。+ 1][A.length] 関数を呼び出す前の B 配列。どうすればいいですか？
再帰関数が以前の呼び出しから変数を記憶するのを助けるために、プライベート変数やJavaのようなものはありますか?

ありがとう

C# で Heap's Algorithm の実装を作成しようとしましたが、正しく動作しません。文字列のすべての順列を見つけてリストに追加する汎用実装を作成しようとしています。

私はこのように始めています：

そして、これが私の実装です：

アルゴリズムは正しい数の順列 (この場合は 6) を生成しますが、順列自体は正しくありません。

ウィキペディアのヒープのアルゴリズムの擬似コードの例から逸脱しているとは思いません。このアルゴリズムの再帰的な性質のために、これをデバッグするのに苦労しています (概念化するのはかなり難しいです)。

問題が何であるかについて、誰かが洞察を提供できますか?

^{PS宿題ではなく、ただの楽しみです。}