問題タブ [gray-code]

最近、10 進数を n ビットのグレイ コードに変換するアルゴリズムを書きなさいという質問がありました。

例: 1 ビットを使用する (最も単純な):

2 ビットの使用

3 ビットの使用

2つの連続した組み合わせの差が最大化されるn要素のセットからk要素のすべての組み合わせを取得するアルゴリズムを実装しようとしています(逆グレイコードのようなものです)。言い換えると、要素が連続して 2 回出現することを避け、要素が不必要に区別されないように、組み合わせを順序付けする必要があります。

理想的には、アルゴリズムはすべての組み合わせを事前に計算してメモリに保存するのではなく、必要に応じて組み合わせを提供します。これを広範囲に検索したところ、https://stackoverflow.com/a/127856/1226020などの詳細な回答がいくつか見つかりましたが、これを適用できないようです。また、その回答にリンクされている記事の多くは有料コンテンツです。

私が何を意味するかを説明するには：

[0, 1, 2, 3, 4] のセットから、2 つの要素のすべての組み合わせを見つけます。一番右の要素を不可能になるまでインクリメントし、左に移動して前の桁をインクリメントするなどの単純なアルゴリズムを使用すると、次の結果が得られます。

この結果は、次の Java コードで生成されます。

これは私が望んでいることではありません。なぜなら、連続する各組み合わせが前のものとできるだけ異なるようにしたいからです。現在、要素 "1" は 4 回連続して表示され、その後は表示されません。この特定の例では、1 つの解決策は次のようになります。

私は実際にこの特定の結果を達成することができました組み合わせが生成された後に並べ替えアルゴリズムを適用することによるケースですが、組み合わせのセット全体を一度に生成し、並べ替えてメモリに保持する必要があるため、これはオンデマンドの組み合わせ生成の要件を満たしません。任意の k および n 値でも機能するかどうかはわかりません。そして最後に、並べ替えアルゴリズムは基本的に組み合わせのセットをループして、前の組み合わせと要素を共有しないものを見つけようとするため、これが最も効率的な方法ではないと確信しています。また、各要素の「ヒット カウント」のテーブルを保持し、それを使用して、組み合わせたヒット カウントが最も低い次の組み合わせを常に取得することも検討しました。私のやや経験的な結論は、n > 2k の場合、要素が 2 つの連続する組み合わせで完全に出現するのを回避できるということです。さもないと、

この問題を、サッカー ゲームなどの標準的なラウンド ロビン スキームを使用して k = 2 で達成されるものと比較できますが、k の任意の値に対する解決策が必要です。これはある種のゲームのトーナメントであると想像できます。n 人のプレイヤーが一連のゲームで他のすべてのプレイヤーと対戦し、各ゲームには k 人のプレイヤーが参加します。プレイヤーはできる限り連続して 2 つのゲームをプレイする必要はありませんが、2 つのゲームの出現の間に不必要に長く待つ必要もないようにする必要があります。

生成後の信頼できる並べ替えアルゴリズム、またはできればオンデマンドでこれを解決する方法についての指針は素晴らしいでしょう!

注: 通常、n <= 50、k <= 5 と仮定しましょう

ありがとう

私の課題は、再帰を使用してグレー コードを出力することです。ユーザーは の間にビット値を入れます。したがって、持てる0-8最大量は 256 (2^8) です。strings

基本ケースは完了しましたが、else 部分をどうするかわかりません。

これまでの私のコード:

n 要素セットのすべての k 要素サブセットを反復するアルゴリズムを探しています。これらすべてのサブセットを明示的に生成したくありません。

これを行う簡単なアルゴリズムがあります。つまり、対応するビット ベクトルを辞書順に並べ替えてから、現在のサブセットから次のサブセットに移動します。

それにもかかわらず、各ステップで 2 ビットのみを切り替えるアルゴリズムを探しています。そのようなコードは「グレイコード」と呼ばれていることを読みましたが、問題のアルゴリズムが見つかりませんでした。

これには簡単な実装がありますか？

通信システムには、特別な種類のグレイ コードが必要です。要件は次のとおりです。

1. すべてのグレー コードと同様に、連続する 2 つの値は 1 ビットだけ異なります。
2. 同じビットでの 2 つの遷移は、任意の数の値から少なくとも離れている必要があります。この距離は、最小ラン長の mrl と表記されます。
3. 最後のコードから最初のコードまでの距離は気にしません。コードがロールオーバーするときの mrl に制約はありません。

このようなグレー コードの 1 つの例は、5 ビットおよび mrl = 4 の場合です。

この論文では、さまざまなビット数に対して最適な mrl 値が示されています。しかし、それらの値は「コンピュータの徹底的な検索により」発見されました。

最大6ビットまでの少数のビットでうまく機能するpythonコードがあります。

私の問題は、20 ビットのコードが必要なことです。基本的なアプローチの複雑さは O(n^3) に近いようです。このコードを改善する方法について何か提案はありますか? より良いアプローチはありますか？

グレーコードの働きを理解しようとしています。非負の整数 n (n はビット数) を指定した場合、そのグレイ コード シーケンスを出力する必要があります。以下にいくつかの例を示します

2 ビットのグレイ コード シーケンス

3 ビットのグレイ コード シーケンス

私の理解によると、グレイ コード シーケンスは 0 で始まり、グレイ コードでは 2 つの連続する値が 1 ビットだけ異なります。2[0,1,3,2]のグレイ コードと 3 のグレイ コードがどのようにして生まれたのかはわかりません。[0,1,3,2,6,7,5,4]

3D スキャンを行うための構造化された照明環境を構築しようとしています。

私の知る限り、3D モデルを再構築するためにグレイ コードを使用することを選択した場合、累乗 2(2^x, x = 0 ~ 10) でエンコードされた特定のパターンを実装する必要があります。

つまり、パターンの解像度は少なくとも 1024 x 1024 である必要があります。

DLP プロジェクタが最大 800 x 480 の解像度しかサポートしていない場合はどうなりますか? グレーコードパターンの解像度が高くなりすぎるとモアレパターンが映ります(試してみました)。私は何をすべきか？

私の友人は、1024 x 1024 のパターンを作成し、それらを 800 x 480 に「切り取る」ことを提案しています。

しかし、グレーコードは特定のシーケンスとパターンに従うべきだと思いました。私の友人の提案は、対称ではないいくつかの画像を作成します。

私と同じような経験をした人はいますか？

----------2015.8.4更新質問----------

私のプロジェクターが高解像度のパターンを完全に投影できない場合、たとえば 2^0 から 2^6 までの低解像度のパターンを投影させてもよいのではないかと考えていました。

それとも、グレー コードは厳密に 2^0 から 2^10 までのパターンを要求するのでしょうか? そうでなければ、グレーコードは利用できませんか?

ハミング距離以外はすべて持っています。「int（）は明示的なベースを持つ非文字列を変換できません」というエラーが表示され続けます

ここに私のコードがあります:

出力は次のようになります

助けてください！