範囲内の数字（すべてを使用することが可能である）の部分を使用して数値の任意のシーケンスを作成することが可能となる0まで2^n-1。すべての番号が一意であるシーケンスを考えてみましょう。
たとえばn = 4、の場合、いくつかのシーケンスは次のとおりです。
4 2 5 7 11 3
15 1 6
6 5 8 2 3 10 12 13 4
質問：シーケンス全体を格納するためにメモリを使用せずにそのようなシーケンスを生成することは可能ですか？
私はF、ビット操作のみを行い、前の数値を使用して次の数値を与える、ある種の関数について考えています。シーケンスの例7 3 5 9：F(7)=3、F(3)=5、F(5)=9。
Fシーケンスを事前に知っている場合、そのような関数を構築するにはどうすればよいですか？
いいえ、一般的ではありません。母関数Fを実装するために、シーケンスSを文字通りメモリで表す必要はありませんが、関数FはシーケンスSを効果的にエンコードするため、メモリが必要です。
（母関数Fは、iがシーケンスの要素であるF（i）がシーケンスの次の要素であるか、iが最後の要素である場合は、それを示す値であるような関数です。）
もちろん、些細な0、1、2、3、…などの一部のシーケンスが小さな関数によって生成される可能性があります。ただし、いくつかのビットbを考慮してください。bビットでエンコードできるさまざまな関数の数は最大2bです（ソースコード、マシンコード、抽象的な数学的表現など、必要なエンコードスキームを使用します）。異なるシーケンスの数は2n！であるため、必要な異なる母関数の数は2 n！です。
従って2 B ≥2 N！ので、ログ≥B 2（2 nは！）。したがって、任意のシーケンスの母関数を2 n保持するのに十分なメモリが必要な場合は、少なくともlog 2（2 n！）ビットが必要です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加